Opened 10 years ago

Last modified 10 years ago

#5669 closed enhancement

[with patch, needs work] New algorithm for Max Clique in Graph class — at Version 1

Reported by: ncohen Owned by: rlm
Priority: minor Milestone: sage-4.1
Component: graph theory Keywords: independant set stable clique
Cc: rlm Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mabshoff)

I recently had to compute a maximum stable set in a graph with 100 vertices and ended up waiting a whole day ( to no good end ) for Sage to compute it. The current algorithm uses the library NetworkX whose algorithm is not nearly as efficient as Cliquer :

http://www.tkk.fi/~pat/cliquer.html

It is based on an algorithm published in 2002, and it gave me a result in less than a millisecond ;-)

Here are the modification I made :

  • I created a spkg file containing the sources of this software for it to be available in SAGE
  • I wrote the interface to use it
  • I modified the Graph class to use this software instead.
  • Added to the function to compute the maximum clique, I added the function Maximum independant set ( which is a similar notion for the complement of a graph, a bit more customary ). As the algorithm provided a function to compute all the maximum cliques, I also added this function

Note: The spkg can be found in http://sage.math.washington.edu/home/mabshoff/SPKG/cliquer-1.2.spkg

Change History (2)

Changed 10 years ago by ncohen

comment:1 Changed 10 years ago by mabshoff

  • Description modified (diff)
  • Summary changed from [with patch, needs review] New algorithm for Max Clique in Graph class to [with patch, needs work] New algorithm for Max Clique in Graph class

Hi,

a couple remarks:

  • do not attach spkgs to trac tickets, but put them up somewhere on the web and post a link. I did that in this case
  • the spkg contains binaries and object files, i.e. you need to run "make clean" on the content of the spkg
  • the patch deletes working code, i.e. it should still be possible to call the NetworkX code even if it sucks
  • your new code has 0% doctest coverage

There is more, but the above should keep you busy for a while :)

Cheers,

Michael

Note: See TracTickets for help on using tickets.