Opened 13 years ago

Closed 13 years ago

#6355 closed enhancement (fixed)

[with spkg, positive review] Cliquer to compute maximum cliques

Reported by: Nathann Cohen Owned by: Robert Miller
Priority: major Milestone: sage-4.1.1
Component: graph theory Keywords: Clique max, Cliquer
Cc: Merged in: Sage 4.1.1.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Robert Miller)

Hello everybody ! I hope this is the last step for this patch to compute the maximum cliques in a graph. Here is the SPKG file with the source code of Cliquer. As for planarity or other modules, the original source code of cliquer is copied, but in this case it is copied in local/lib/cliquer-1.2, I was told planarity was to be an exception to the rule.

You can download the SPKG file at this address : http://www-sop.inria.fr/members/Nathann.Cohen/cliquer-1.2.spkg

The vote to include this SPKG can be found here: http://groups.google.com/group/sage-devel/browse_thread/thread/b24e7c1603b5f988

There is also an accompanying patch, at #5793.

Change History (26)

comment:1 Changed 13 years ago by Robert Miller

Summary: [with SPKG, needs review] Cliquer to compute maximum cliques[with SPKG, needs work] Cliquer to compute maximum cliques

This ticket, plus #5793 and #5669, are all a total mess, IMHO. There are two separate spkg's linked, here and on #5669, and there are two different sets of patches (11803.patch is separately 229.4KB and 6.0KB) at #5793 and #5669.

  1. Patch names need to be of the form trac_####-description.patch.
  2. I don't even know which spkg to review.
  3. #5793 and #5669 are total duplicates.

My recommendation is to close the other two tickets as duplicates, indicate which spkg to review here, properly format the correct patches to be applied, and post everything here. There's just too much confusion right now.

Nathann -- I would really like to see cliquer included in Sage, so if you need any help getting this in, please don't hesitate to contact me directly.

comment:2 Changed 13 years ago by Robert Miller

As far as I could tell at Sage Days 16, the next step required for cliquer is: Someone needs to implement a build system for Cliquer, either using autotools or SCons. Given how simple cliquer is, SCons is probably the way to go, since this would be something like the one liner Library('cliquer', ['foo.c', 'bar.c']).

comment:3 Changed 13 years ago by Nathann Cohen

I updated the SPKG file for cliquer.. This new one builds a shared library and I do not call any .c file in the cython code anymore !!

The address is still the same, though ;-)

Nathann

comment:4 in reply to:  3 Changed 13 years ago by Robert Miller

Replying to ncohen:

I updated the SPKG file for cliquer.. This new one builds a shared library and I do not call any .c file in the cython code anymore !!

True, this builds a shared library, but it doesn't seem very portable. The problem is that the code you've written probably works only on systems very similar to yours. For example, when I try building on OS X (32- or 64-bit), I get:

ld: unknown option: -soname
collect2: ld returned 1 exit status
cp: cannot stat `libcliquer.so': No such file or directory

real	0m2.000s
user	0m0.465s
sys	0m0.190s
sage: An error occurred while installing cliquer-1.2

You need to use SCons or some form of autotools as I suggested above, for this to ever be a viable SPKG.

comment:5 Changed 13 years ago by Nathann Cohen

Summary: [with SPKG, needs work] Cliquer to compute maximum cliques[with SPKG, needs review] Cliquer to compute maximum cliques

I just updated the SPKG, which now uses Scons !

Nathann

comment:6 Changed 13 years ago by Robert Miller

Authors: ncohenNathann Cohen
Reviewers: Robert Miller
Summary: [with SPKG, needs review] Cliquer to compute maximum cliques[with SPKG, needs work] Cliquer to compute maximum cliques

Nathann,

This is great work! However, you are still hard-coding some Linux-isms in spkg-install:

scons && cp Build/libcliquer.so "$SAGE_LOCAL/lib/"

Unfortunately, on OS X, it is libcliquer.dylib that is built by SCons. Why don't you copy Build/* over, to include all cases? You should also delete the commented part from spkg-install. While I'm reviewing, you need a Mercurial repository in the base directory of the spkg, and the License section of SPKG.txt needs to be clarified (i.e. GPLv2+).

Keep up the good work!

comment:7 Changed 13 years ago by Nathann Cohen

Summary: [with SPKG, needs work] Cliquer to compute maximum cliques[with SPKG, needs review] Cliquer to compute maximum cliques

All has been done according to your wishes ;-)

The spkg has been updated !

comment:8 Changed 13 years ago by Robert Miller

Summary: [with SPKG, needs review] Cliquer to compute maximum cliques[with SPKG, needs work] Cliquer to compute maximum cliques
  1. You need to check in your changes to the repo!
  1. You should add a line to spkg-install which copies header files to the right place, something like cp src/*.h "$SAGE_LOCAL/include/cliquer/"
  1. This is all I can think of, so after this it's a lot of testing on different platforms.

comment:9 Changed 13 years ago by Nathann Cohen

Summary: [with SPKG, needs work] Cliquer to compute maximum cliques[with SPKG, needs review] Cliquer to compute maximum cliques

done again ! ;-)

comment:10 Changed 13 years ago by Robert Miller

Change cliquer-1.2 to cliquer (twice) in spkg-install, so that we don't need to keep upgrading code in the Sage library when Cliquer upgrades.

After that, I think that this is ready to go! It builds successfully on 32-bit and 64-bit OS X and on sage.math.

comment:11 Changed 13 years ago by Nathann Cohen

Done. I have to change the patch though, as the directory changed.

comment:12 Changed 13 years ago by Robert Miller

Summary: [with SPKG, needs review] Cliquer to compute maximum cliques[with SPKG, positive review] Cliquer to compute maximum cliques

The spkg looks great! Nice work.

NOTE: This will be little useful without also merging #5793, when it is ready.

Nathann, shall we continue at #5793?

comment:13 Changed 13 years ago by Nathann Cohen

A small problem with the creation of a directory, and changes commited to the hg repository.

comment:14 Changed 13 years ago by Robert Miller

Ah, you beat me to posting the same fix! :-)

comment:15 Changed 13 years ago by Robert Miller

Summary: [with SPKG, positive review] Cliquer to compute maximum cliques[with SPKG, needs work] Cliquer to compute maximum cliques

However, there is now a cliquer-1.2.spkg inside the spkg!!!

comment:16 Changed 13 years ago by Nathann Cohen

It comes from a tar command run in the wrong directory.... fixed ;-)

comment:17 Changed 13 years ago by Nathann Cohen

Summary: [with SPKG, needs work] Cliquer to compute maximum cliques[with SPKG, needs review] Cliquer to compute maximum cliques

comment:18 Changed 13 years ago by Robert Miller

Summary: [with SPKG, needs review] Cliquer to compute maximum cliques[with SPKG, positive review] Cliquer to compute maximum cliques

comment:19 Changed 13 years ago by Robert Miller

Description: modified (diff)
Milestone: sage-4.1.1

comment:20 Changed 13 years ago by Robert Miller

Description: modified (diff)

comment:21 Changed 13 years ago by Minh Van Nguyen

Merged in: Sage 4.1.1.alpha1
Resolution: fixed
Status: newclosed

The SPKG at

http://www-sop.inria.fr/members/Nathann.Cohen/cliquer-1.2.spkg

doesn't conform to the naming convention for SPKG's. I've renamed it as cliquer-1.2.p0.spkg and uploaded the renamed SPKG up at

http://sage.math.washington.edu/home/mvngu/patch/cliquer-1.2.p0.spkg

As far as I understand, this new SPKG doesn't depend on #5793. So I'm merging the SPKG into the standard SPKG repository.

comment:22 Changed 13 years ago by Minh Van Nguyen

Summary: [with SPKG, positive review] Cliquer to compute maximum cliques[with spkg, positive review] Cliquer to compute maximum cliques

See #6626 for a follow-up to this ticket.

comment:23 Changed 13 years ago by Minh Van Nguyen

Merged in: Sage 4.1.1.alpha1
Resolution: fixed
Status: closedreopened

I'm reopening this ticket until #6626 is fixed.

comment:24 Changed 13 years ago by Minh Van Nguyen

Are there any code or doctests to test the functionalities provided by this package? Any package that is merged in the standard package repository must be doctested by code in the Sage library.

comment:25 Changed 13 years ago by Nathann Cohen

The code/doctest related to cliquer is to be found in #5793 : almost all the functions of the Graph class related to cliques use it, and if I make no mistake I documented all of them ;-)

comment:26 Changed 13 years ago by Minh Van Nguyen

Merged in: Sage 4.1.1.rc1
Resolution: fixed
Status: reopenedclosed

Merged in standard package repository.

Note: See TracTickets for help on using tickets.