#5669 closed enhancement (duplicate)
New algorithm for Max Clique in Graph class
Reported by: | Nathann Cohen | Owned by: | Robert Miller |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.1 |
Component: | graph theory | Keywords: | independant set stable clique |
Cc: | Robert Miller | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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)
Change History (9)
Changed 14 years ago by
Attachment: | 11803.patch added |
---|
comment:1 Changed 14 years ago by
Description: | modified (diff) |
---|---|
Summary: | [with patch, needs review] New algorithm for Max Clique in Graph class → [with patch, needs work] New algorithm for Max Clique in Graph class |
comment:2 Changed 14 years ago by
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 14 years ago by
Milestone: | → sage-4.0 |
---|
comment:4 Changed 14 years ago by
Cc: | Robert Miller added |
---|
comment:5 Changed 14 years ago by
Resolution: | → duplicate |
---|---|
Status: | new → closed |
Duplication of #6355.
comment:6 Changed 14 years ago by
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: 8 Changed 14 years ago by
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 Changed 14 years ago by
Summary: | [with patch, needs work] New algorithm for Max Clique in Graph class → 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.
Hi,
a couple remarks:
There is more, but the above should keep you busy for a while :)
Cheers,
Michael