Opened 14 years ago
Closed 14 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: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 14 years ago by
Summary: | [with SPKG, needs review] Cliquer to compute maximum cliques → [with SPKG, needs work] Cliquer to compute maximum cliques |
---|
comment:2 Changed 14 years ago by
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: 4 Changed 14 years ago by
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 Changed 14 years ago by
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 14 years ago by
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 14 years ago by
Authors: | ncohen → Nathann 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 14 years ago by
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 14 years ago by
Summary: | [with SPKG, needs review] Cliquer to compute maximum cliques → [with SPKG, needs work] Cliquer to compute maximum cliques |
---|
- You need to check in your changes to the repo!
- You should add a line to
spkg-install
which copies header files to the right place, something likecp src/*.h "$SAGE_LOCAL/include/cliquer/"
- This is all I can think of, so after this it's a lot of testing on different platforms.
comment:9 Changed 14 years ago by
Summary: | [with SPKG, needs work] Cliquer to compute maximum cliques → [with SPKG, needs review] Cliquer to compute maximum cliques |
---|
done again ! ;-)
comment:10 Changed 14 years ago by
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 14 years ago by
Done. I have to change the patch though, as the directory changed.
comment:12 Changed 14 years ago by
Summary: | [with SPKG, needs review] Cliquer to compute maximum cliques → [with SPKG, positive review] Cliquer to compute maximum cliques |
---|
comment:13 Changed 14 years ago by
A small problem with the creation of a directory, and changes commited to the hg repository.
comment:15 Changed 14 years ago by
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 14 years ago by
It comes from a tar command run in the wrong directory.... fixed ;-)
comment:17 Changed 14 years ago by
Summary: | [with SPKG, needs work] Cliquer to compute maximum cliques → [with SPKG, needs review] Cliquer to compute maximum cliques |
---|
comment:18 Changed 14 years ago by
Summary: | [with SPKG, needs review] Cliquer to compute maximum cliques → [with SPKG, positive review] Cliquer to compute maximum cliques |
---|
comment:19 Changed 14 years ago by
Description: | modified (diff) |
---|---|
Milestone: | → sage-4.1.1 |
comment:20 Changed 14 years ago by
Description: | modified (diff) |
---|
comment:21 Changed 14 years ago by
Merged in: | → Sage 4.1.1.alpha1 |
---|---|
Resolution: | → fixed |
Status: | new → 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 14 years ago by
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 14 years ago by
Merged in: | Sage 4.1.1.alpha1 |
---|---|
Resolution: | fixed |
Status: | closed → reopened |
I'm reopening this ticket until #6626 is fixed.
comment:24 Changed 14 years ago by
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 14 years ago by
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 14 years ago by
Merged in: | → Sage 4.1.1.rc1 |
---|---|
Resolution: | → fixed |
Status: | reopened → closed |
Merged in standard package repository.
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.trac_####-description.patch
.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.