New algorithm for Max Clique in Graph class

[nathanncohen]

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

CC: @rlmill

Component: graph theory

Keywords: independant set stable clique

Issue created by migration from https://trac.sagemath.org/ticket/5669

[nathanncohen]

Attachment: 11803.patch.gz

[sagetrac-mabshoff]

comment:1

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

[jasongrout]

comment:2

Well, to be fair, the new code is half doctested. The new graph functions are doctested, the interface functions are not doctested.

[rlmill]

comment:5

Duplication of #6355.

[jasongrout]

comment:6

ncohen,

If the patch on this ticket is no longer needed, can you delete the "[with patch, needs work]" in the title? If it is still needed, can you either reopen this ticket so the patch is not lost or move the patch to another ticket that is open? It is confusing to have a patch that "needs work" on a closed ticket.

Thanks.

[nathanncohen]

comment:7

Actually, I do not know if I can close this ticket and delete the patch : I do not understand how the patches work.
Each time I create a patch, it contains the differences between the last patch I created and the current version. Hence, as the others patches seem to have been built over this one, can I really delete it or do I need to move it to the current ticket for Cliquer's patch, which is #5793 ?

Thanks !

Nathann

[rlmill]

comment:8

Replying to @nathanncohen:

Actually, I do not know if I can close this ticket and delete the patch

There is no need for any of this -- what you need to do is make sure that all the patches needed by #5793 are actually on ticket #5793. Also, while you are at it, you should probably use more descriptive names than the five-digit numbers you have been using (this also leads to the confusion that the 11803.patch here is only 6.0KB and the one there is 229.4KB). The suggested format is trac_####-description.patch. You also need to indicate at that ticket exactly which patches should go in, and in what order.

Each time I create a patch, it contains the differences between the last patch I created and the current version. Hence, as the others patches seem to have been built over this one, can I really delete it or do I need to move it to the current ticket for Cliquer's patch, which is #5793 ?

There is also the option of using Mercurial queues to flatten patches (i.e. roll several patches into one). That way, you could eventually post just one patch which does everything, and then you could ask someone with admin privileges (such as myself) to delete the other patches, in order to clean things up.