#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 )
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 12 years ago by
comment:1 Changed 12 years ago by
- 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
comment:2 Changed 12 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 12 years ago by
- Milestone set to sage-4.0
comment:4 Changed 12 years ago by
- Cc rlm added
comment:5 Changed 12 years ago by
- Resolution set to duplicate
- Status changed from new to closed
Duplication of #6355.
comment:6 Changed 12 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 12 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 in reply to: ↑ 7 Changed 12 years ago by
- 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.
Hi,
a couple remarks:
There is more, but the above should keep you busy for a while :)
Cheers,
Michael