Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#5669 closed enhancement (duplicate)

New algorithm for Max Clique in Graph class

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

Attachments (1)

11803.patch (6.0 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (9)

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

comment:2 Changed 10 years ago by jason

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

comment:3 Changed 10 years ago by mabshoff

  • Milestone set to sage-4.0

comment:4 Changed 10 years ago by rlm

  • Cc rlm added

comment:5 Changed 10 years ago by rlm

  • Resolution set to duplicate
  • Status changed from new to closed

Duplication of #6355.

comment:6 Changed 10 years ago by jason

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.

comment:7 follow-up: Changed 10 years ago by ncohen

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 http://trac.sagemath.org/sage_trac/ticket/5793 ?

Thanks !

Nathann

comment:8 in reply to: ↑ 7 Changed 10 years ago by rlm

  • Summary changed from [with patch, needs work] New algorithm for Max Clique in Graph class to New algorithm for Max Clique in Graph class

Replying to ncohen:

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 http://trac.sagemath.org/sage_trac/ticket/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.

Note: See TracTickets for help on using tickets.