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 like`cp 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: |
---|

### 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.

**Note:**See TracTickets for help on using tickets.

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.