Opened 10 years ago

Closed 10 years ago

#6355 closed enhancement (fixed)

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

Reported by: ncohen Owned by: rlm
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: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rlm)

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 10 years ago by rlm

  • Summary changed from [with SPKG, needs review] Cliquer to compute maximum cliques to [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 10 years ago by rlm

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 follow-up: Changed 10 years ago by 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 !!

The address is still the same, though ;-)

Nathann

comment:4 in reply to: ↑ 3 Changed 10 years ago by rlm

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 10 years ago by ncohen

  • Summary changed from [with SPKG, needs work] Cliquer to compute maximum cliques to [with SPKG, needs review] Cliquer to compute maximum cliques

I just updated the SPKG, which now uses Scons !

Nathann

comment:6 Changed 10 years ago by rlm

  • Authors changed from ncohen to Nathann Cohen
  • Reviewers set to Robert Miller
  • Summary changed from [with SPKG, needs review] Cliquer to compute maximum cliques to [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 10 years ago by ncohen

  • Summary changed from [with SPKG, needs work] Cliquer to compute maximum cliques to [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 10 years ago by rlm

  • Summary changed from [with SPKG, needs review] Cliquer to compute maximum cliques to [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 10 years ago by ncohen

  • Summary changed from [with SPKG, needs work] Cliquer to compute maximum cliques to [with SPKG, needs review] Cliquer to compute maximum cliques

done again ! ;-)

comment:10 Changed 10 years ago by rlm

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 10 years ago by ncohen

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

comment:12 Changed 10 years ago by rlm

  • Summary changed from [with SPKG, needs review] Cliquer to compute maximum cliques to [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 10 years ago by ncohen

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

comment:14 Changed 10 years ago by rlm

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

comment:15 Changed 10 years ago by rlm

  • Summary changed from [with SPKG, positive review] Cliquer to compute maximum cliques to [with SPKG, needs work] Cliquer to compute maximum cliques

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

comment:16 Changed 10 years ago by ncohen

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

comment:17 Changed 10 years ago by ncohen

  • Summary changed from [with SPKG, needs work] Cliquer to compute maximum cliques to [with SPKG, needs review] Cliquer to compute maximum cliques

comment:18 Changed 10 years ago by rlm

  • Summary changed from [with SPKG, needs review] Cliquer to compute maximum cliques to [with SPKG, positive review] Cliquer to compute maximum cliques

comment:19 Changed 10 years ago by rlm

  • Description modified (diff)
  • Milestone set to sage-4.1.1

comment:20 Changed 10 years ago by rlm

  • Description modified (diff)

comment:21 Changed 10 years ago by mvngu

  • Merged in set to Sage 4.1.1.alpha1
  • Resolution set to fixed
  • Status changed from new to closed

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 10 years ago by mvngu

  • Summary changed from [with SPKG, positive review] Cliquer to compute maximum cliques to [with spkg, positive review] Cliquer to compute maximum cliques

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

comment:23 Changed 10 years ago by mvngu

  • Merged in Sage 4.1.1.alpha1 deleted
  • Resolution fixed deleted
  • Status changed from closed to reopened

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

comment:24 Changed 10 years ago by mvngu

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 10 years ago by ncohen

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 10 years ago by mvngu

  • Merged in set to Sage 4.1.1.rc1
  • Resolution set to fixed
  • Status changed from reopened to closed

Merged in standard package repository.

Note: See TracTickets for help on using tickets.