Sage: Ticket #5793: [with patch, positive review] New algorithm for Max Clique in Graph class using Cython
https://trac.sagemath.org/ticket/5793
<p>
This depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/5793
Trac 1.1.6mabshoffThu, 16 Apr 2009 05:47:05 GMTsummary changed; milestone set
https://trac.sagemath.org/ticket/5793#comment:1
https://trac.sagemath.org/ticket/5793#comment:1
<ul>
<li><strong>milestone</strong>
set to <em>sage-3.4.2</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
Hi,
</p>
<p>
the patch as is will not go into Sage since you are putting the sources for cliquer-1.2 into the Sage library tree where they do not belong.
</p>
<p>
I have not looked at the cython interface, but my guess would be that we need to change cliquer-1.2 to create a library. Please split the cython interface work (the code you wrote minus the cliquer-1.2 source code) and the cliquer-1.2.spkg work. The Cython code should remain here while spkg should go to <a class="closed ticket" href="https://trac.sagemath.org/ticket/5669" title="enhancement: New algorithm for Max Clique in Graph class (closed: duplicate)">#5669</a>.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketncohenThu, 18 Jun 2009 13:07:41 GMT
https://trac.sagemath.org/ticket/5793#comment:2
https://trac.sagemath.org/ticket/5793#comment:2
<p>
A new patch using the SPKG you can find at :
<a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/6355"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/6355</a>
</p>
TicketrlmFri, 19 Jun 2009 22:35:43 GMTcc set
https://trac.sagemath.org/ticket/5793#comment:3
https://trac.sagemath.org/ticket/5793#comment:3
<ul>
<li><strong>cc</strong>
<em>rlm</em> added
</li>
</ul>
TicketrlmMon, 22 Jun 2009 22:35:04 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/5793#comment:4
https://trac.sagemath.org/ticket/5793#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>duplicate</em>
</li>
</ul>
<p>
Duplication of <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a>.
</p>
TicketjasonWed, 01 Jul 2009 05:40:44 GMT
https://trac.sagemath.org/ticket/5793#comment:5
https://trac.sagemath.org/ticket/5793#comment:5
<p>
To get this going again, here are some specific suggestions for patch 12427.patch and the associated spkg:
</p>
<ul><li>copy the header files to somewhere in $SAGE_LOCAL/include (maybe $SAGE_LOCAL/include/cliquer/*.h
</li></ul><ul><li>Make a cliquer.pxd file that declares the necessary functions and structs from the header files. Make sure that you are only doing cdef externs from the header files, not the .c files like the patch is currently doing. Don't include the path; just do <code>cdef extern from "cliquer/graph.h":</code> since the header is in the include path. This cliquer.pxd file can go into sage/graphs.
</li></ul><ul><li>Make a cliquer.pyx in sage/graphs that contains the definitions of max_clique, all_max_clique, and clique_number. Document and add doctests to these functions.
</li></ul><ul><li>Delete the lines
<pre class="wiki">from sage.graphs.graph import Graph
#from distutils.core import setup
#from distutils.extension import Extension
from Cython.Distutils import build_ext
</pre></li></ul><ul><li>In module_list.py, add a <code>libraries = ['cliquer']</code> option (see the surrounding declarations for examples of this).
</li></ul><ul><li>Compile the cliquer sources into a shared library, named libcliquer.so, using the instructions in the <a class="missing wiki">HowTo?</a> William posted. Place this shared library into $SAGE_LOCAL/lib.
</li></ul><ul><li>In the graphs.py, I don't think you need to do <code>from sage.graphs.cliquer import clique_number</code>. Since the module will be in that directory, I think it would be sufficient to do <code>from cliquer import clique_number</code>.
</li></ul>
TicketjasonWed, 01 Jul 2009 05:45:26 GMTstatus changed; resolution deleted
https://trac.sagemath.org/ticket/5793#comment:6
https://trac.sagemath.org/ticket/5793#comment:6
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>reopened</em>
</li>
<li><strong>resolution</strong>
<em>duplicate</em> deleted
</li>
</ul>
<p>
rlm: this ticket has what looks like the most current patch, whereas <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a> does not have a patch. I'm reopening this ticket so that the "active" patch is not closed (but I am not opposed to moving this patch to <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a> to consolidate things!). I feel a bit silly commenting on a patch here when the ticket is closed, but the patch clearly has not been moved/merged/etc.
</p>
TicketjasonWed, 01 Jul 2009 05:50:44 GMT
https://trac.sagemath.org/ticket/5793#comment:7
https://trac.sagemath.org/ticket/5793#comment:7
<p>
Suggestions 1 and 6 in my comment above apply to the spkg, not the patch.
</p>
TicketrobertwbWed, 01 Jul 2009 06:01:41 GMT
https://trac.sagemath.org/ticket/5793#comment:8
https://trac.sagemath.org/ticket/5793#comment:8
<p>
Whence the "../../../../local/lib/cliquer-1.2/cliquer.h" if there's no spkg. Also, I belive local/include is in the include path, so no need to have this long path. (And include files belong in local/include, not local/lib.) I would probably drop the 1.2 suffix so we don't have to update the link paths every time the version gets bumped.
</p>
TicketjasonWed, 01 Jul 2009 06:47:44 GMT
https://trac.sagemath.org/ticket/5793#comment:9
https://trac.sagemath.org/ticket/5793#comment:9
<p>
that's what I meant by point 2 (just do <code>cdef extern from "cliquer/graph.h"</code>) and point 1 (put the headers in $SAGE_LOCAL/include/cliquer/*.h)
</p>
TicketncohenTue, 07 Jul 2009 13:14:48 GMT
https://trac.sagemath.org/ticket/5793#comment:10
https://trac.sagemath.org/ticket/5793#comment:10
<p>
Here is a new patch ( number 12428 ) using a shared library !!! I hope you will appreciate it as it took me some time to figure out the inner behavior of Sage ;-)
</p>
<p>
The new spkg is available on <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/6355"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/6355</a>
</p>
<p>
Nathann
</p>
TicketncohenFri, 17 Jul 2009 19:01:59 GMT
https://trac.sagemath.org/ticket/5793#comment:11
https://trac.sagemath.org/ticket/5793#comment:11
<p>
My version is working, but I am a bit lost with all the patches... How can I produce a patch containing all the modifications I made since the begining ( since I cloned the original branch, actually ) ?
</p>
<p>
Thanks !!!
</p>
TicketrlmFri, 17 Jul 2009 19:05:30 GMT
https://trac.sagemath.org/ticket/5793#comment:12
https://trac.sagemath.org/ticket/5793#comment:12
<p>
One option is to clone the branch using <code>hg_sage.clone</code>, but to give it the revision number corresponding to the last patch not part of your changes (the base). Then you can copy the affected files over, and it is as if you have done all the work, but you have not checked anything in.
</p>
TicketncohenFri, 17 Jul 2009 19:26:05 GMT
https://trac.sagemath.org/ticket/5793#comment:13
https://trac.sagemath.org/ticket/5793#comment:13
<p>
New patch "cliquer.patch" containing all the modifications for cliquer since the beginning. And with the good directory's name ;-)
</p>
TicketncohenFri, 17 Jul 2009 19:26:48 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer.patch</em>
</li>
</ul>
<p>
Cliquer, from the beginning to the end, with the good directory's name !
</p>
TicketrlmSat, 18 Jul 2009 17:48:51 GMT
https://trac.sagemath.org/ticket/5793#comment:14
https://trac.sagemath.org/ticket/5793#comment:14
<p>
Nathann,
</p>
<p>
I have deleted the previous patches to avoid confusion.
</p>
<p>
When addressing the following issues, please post another patch to be applied on top of the first (this makes review easier).
</p>
<ol><li><code>algorithm=='networkx'</code> is never tested, and if it were, it would fail, due to the <code>cliques</code> parameter
</li></ol><ol start="2"><li>Why are you using <code>cliquer.pxi</code> instead of <code>cliquer.pxd</code>? If it were <code>pxd</code> instead, then other Cython files could <code>cimport</code> the same data types.
</li></ol><ol start="3"><li>It should go:
<pre class="wiki">if algorithm=='networkx':
...
elif algorithm=='cliquer':
...
else:
raise NotImplementedError("Only 'networkx' and 'cliquer' are supported.")
</pre></li></ol><p>
Also you need to change one instance of <code>'Cliquer'</code> to <code>'cliquer'</code>.
</p>
<ol start="4"><li>In maximum_cliques, "vertex set" should be "vertex sets"
</li></ol>
TicketncohenSun, 19 Jul 2009 19:24:59 GMT
https://trac.sagemath.org/ticket/5793#comment:15
https://trac.sagemath.org/ticket/5793#comment:15
<p>
I hope all is fixed now... Though I just renamed cliquer.pxi to cliquer.pxd without really understanding the difference <sup></sup>;
</p>
<p>
By the way, I am not really sure this possibility to change the algorithm used to compute the cliquer number is that useful... Just take a look at this :
</p>
<p>
sage: g=graphs.RandomGNP(100,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 2.49 s, sys: 0.00 s, total: 2.49 s
Wall time: 2.49 s
9
sage: time g.clique_number()
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
9
sage: g=graphs.RandomGNP(150,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 18.45 s, sys: 0.04 s, total: 18.49 s
Wall time: 18.49 s
10
sage: time g.clique_number()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
10
sage: g=graphs.RandomGNP(200,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 82.33 s, sys: 0.18 s, total: 82.52 s
Wall time: 82.54 s
11
sage: time g.clique_number()
CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s
Wall time: 0.07 s
11
</p>
<p>
Anyway, from the practical point of view, it works now ;-)
</p>
<p>
Nathann
</p>
TicketncohenSun, 19 Jul 2009 19:28:42 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer-2.patch</em>
</li>
</ul>
<p>
Second patch
</p>
TicketncohenMon, 20 Jul 2009 11:24:06 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:16
https://trac.sagemath.org/ticket/5793#comment:16
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
TicketrlmMon, 20 Jul 2009 15:17:59 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:17
https://trac.sagemath.org/ticket/5793#comment:17
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5793#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<p>
By the way, I am not really sure this possibility to change the algorithm used to compute the cliquer number is that useful...
</p>
</blockquote>
<p>
There are plenty of reasons to have two different implementations, and one I can think of right off the top of my head is to compare results for correctness.
</p>
<ol><li>You have removed the input "cliques," which is used by NetworkX. You need to put this back in, and mention that it is ignored unless the algorithm is "networkx."
</li></ol><ol start="2"><li>The <code>include '../ext/cliquer.pxd'</code> line at the beginning of cliquer.pyx is not necessary. "include" is a plain text include, and <code>pxd</code> files are forward declarations, which get automatically included by Cython as long as the other part of the filename is the same.
</li></ol><ol start="3"><li>One thing I should have mentioned last round: the three functions introduced in cliquer.pyx need to be documented, including some nontrivial doctests.
</li></ol><p>
After all this is done, we should be very close to finished!
</p>
TicketncohenMon, 20 Jul 2009 18:04:29 GMT
https://trac.sagemath.org/ticket/5793#comment:18
https://trac.sagemath.org/ticket/5793#comment:18
<p>
Hmmmmmm.... There is a perhaps-not-so-small problem :
</p>
<p>
G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
G.maximum_clique()
2
</p>
<p>
When it is obviously 3...
</p>
<p>
What do we do in this situation ? <sup></sup>;
</p>
TicketrlmMon, 20 Jul 2009 18:20:55 GMT
https://trac.sagemath.org/ticket/5793#comment:19
https://trac.sagemath.org/ticket/5793#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5793#comment:18" title="Comment 18">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What do we do in this situation ? <sup></sup>;
</p>
</blockquote>
<p>
We debug! I'm looking into this now, but I'm not sure what I'll be able to find out...
</p>
<ol start="4"><li>Another thing is that <code>cliquer.pxd</code> needs to be in the same directory as <code>cliquer.pyx</code>.
</li></ol>
TicketncohenMon, 20 Jul 2009 18:23:02 GMT
https://trac.sagemath.org/ticket/5793#comment:20
https://trac.sagemath.org/ticket/5793#comment:20
<p>
it does not come from cliquer itself, which is a relief. I ran cliquer on the command lineand on this file :
p edges 4 5
e 1 2
e 1 3
e 1 4
e 2 3
e 2 4
</p>
<p>
~/cliquer-1.2$ ./cl example
Reading graph from example...OK
Searching for a single maximum weight clique...
</p>
<blockquote>
<p>
2/4 (max 2) 0.00 s (0.00 s/round)
3/4 (max 3) 0.00 s (0.00 s/round)
4/4 (max 3) 0.00 s (0.00 s/round)
</p>
</blockquote>
<p>
size=3, weight=3: 1 2 4
~/cliquer-1.2$
</p>
TicketncohenMon, 20 Jul 2009 18:26:22 GMT
https://trac.sagemath.org/ticket/5793#comment:21
https://trac.sagemath.org/ticket/5793#comment:21
<p>
It works when I replace :
</p>
<p>
buf=' e %d %d' %(u,v)
</p>
<p>
by
</p>
<p>
buf=' e %d %d' %(u+1,v+1)
</p>
<p>
in cliquer.pyx. I thought it may come from the difference between 0....n-1 and 1...n and it seems correct. I am running other tests with NetworkX to check.
</p>
TicketrlmMon, 20 Jul 2009 18:26:29 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>trac_5793_debug_only.patch</em>
</li>
</ul>
<p>
DO NOT APPLY!
</p>
TicketrlmMon, 20 Jul 2009 18:28:21 GMT
https://trac.sagemath.org/ticket/5793#comment:22
https://trac.sagemath.org/ticket/5793#comment:22
<p>
It seems as if Cliquer is subtracting one from each vertex in the input, and so the input needs to have one added to it. To see this, apply <code>trac_5793_debug_only.patch</code>, and you get:
</p>
<pre class="wiki">sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}); G.maximum_clique()
(0, 1, None)
e 0 1
Unweighted graph has 4 vertices, 0 edges (density 0.00).
0 ->
1 ->
2 ->
3 ->
(0, 2, None)
e 0 2
Unweighted graph has 4 vertices, 0 edges (density 0.00).
0 ->
1 ->
2 ->
3 ->
(0, 3, None)
e 0 3
Unweighted graph has 4 vertices, 0 edges (density 0.00).
0 ->
1 ->
2 ->
3 ->
(1, 2, None)
e 1 2
Unweighted graph has 4 vertices, 1 edges (density 0.17).
0 -> 1
1 -> 0
2 ->
3 ->
(1, 3, None)
e 1 3
Unweighted graph has 4 vertices, 2 edges (density 0.33).
0 -> 1 2
1 -> 0
2 -> 0
3 ->
[0, 2]
</pre><p>
You should probably also expose at least this <code>print_graph</code> function in the official versions.
</p>
TicketrlmMon, 20 Jul 2009 18:29:13 GMT
https://trac.sagemath.org/ticket/5793#comment:23
https://trac.sagemath.org/ticket/5793#comment:23
<p>
Oops, looks like we were duplicating effort! But I'll be online for a while, so this might get positively reviewed today!
</p>
TicketncohenMon, 20 Jul 2009 18:39:17 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:24
https://trac.sagemath.org/ticket/5793#comment:24
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
New patch !!
</p>
TicketncohenMon, 20 Jul 2009 18:39:33 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer-3.patch</em>
</li>
</ul>
TicketrlmMon, 20 Jul 2009 18:56:41 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:25
https://trac.sagemath.org/ticket/5793#comment:25
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
OK, I have a few more requests:
</p>
<ol><li>I think you should expose Cliquer's <code>graph_print</code> function in <code>cliquer.pxd</code>, so other people see it when they try to play around with the interface.
</li></ol><ol start="2"><li>In general, doctests should be indented, so e.g.
<pre class="wiki">EXAMPLES::
sage: C=graphs.PetersenGraph()
sage: max_clique(C)
[7, 9]
"""
</pre></li></ol><p>
should be
</p>
<pre class="wiki">EXAMPLES::
sage: C=graphs.PetersenGraph()
sage: max_clique(C)
[7, 9]
"""
</pre><ol start="3"><li>In fact, you should probably check out
</li></ol><p>
<a href="http://www.sagemath.org/doc/developer/conventions.html">http://www.sagemath.org/doc/developer/conventions.html</a>
</p>
<p>
For example, the following belongs in an <code>INPUT:</code> block, and would look much more professional there:
</p>
<pre class="wiki">The parameter 'cliques' is an optional list of cliques that can be input if already computed.
ONLY USED BY NetworkX !!!
</pre><ol start="4"><li>There are several functions in <code>graph.py</code> which compute with cliques, which haven't been exposed to this new interface. For example, <code>G.cliques()</code>. It would be nice to take care of those functions now too, so people don't unnecessarily complain about these functions being slow later. They are all in the same part of the file, which starts with <code>### Cliques</code>.
</li></ol>
TicketrlmMon, 20 Jul 2009 19:21:04 GMT
https://trac.sagemath.org/ticket/5793#comment:26
https://trac.sagemath.org/ticket/5793#comment:26
<ol start="5"><li>There is one other thing to be aware of. You are assuming that the vertex set is *always* {0,...,n-1}. In fact, this will cause some trouble:
<pre class="wiki">sage: C = graphs.CubeGraph(4)
sage: C.maximum_clique()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
...
TypeError: cannot concatenate 'str' and 'int' objects
sage: C.vertices()[0]
'0000'
</pre></li></ol><p>
Here is the idea to get around this, since this problem has come up many times before:
</p>
<pre class="wiki">sage: C = graphs.CubeGraph(4)
sage: G,d = C.relabel(inplace=False, return_map=True)
sage: d_inv = {}
sage: for v in d:
....: d_inv[d[v]] = v
....:
sage: C.vertices()
['0000',
'0001',
'0010',
'0011',
'0100',
'0101',
'0110',
'0111',
'1000',
'1001',
'1010',
'1011',
'1100',
'1101',
'1110',
'1111']
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sage: d
{'0000': 0,
'0001': 1,
'0010': 2,
'0011': 3,
'0100': 4,
'0101': 5,
'0110': 6,
'0111': 7,
'1000': 8,
'1001': 9,
'1010': 10,
'1011': 11,
'1100': 12,
'1101': 13,
'1110': 14,
'1111': 15}
sage: d_inv
{0: '0000',
1: '0001',
2: '0010',
3: '0011',
4: '0100',
5: '0101',
6: '0110',
7: '0111',
8: '1000',
9: '1001',
10: '1010',
11: '1011',
12: '1100',
13: '1101',
14: '1110',
15: '1111'}
</pre>
TicketncohenTue, 21 Jul 2009 08:15:57 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:27
https://trac.sagemath.org/ticket/5793#comment:27
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
Patch number 4 :
</p>
<ul><li>Cliquer now deals with graphs with vertex labels not in 0..n-1
</li><li>Some functions of Graph could use cliquer and now can. ( some functions dealing with MAXIMAL cliques instead of MAXIMUM cliques can not use cliquer, though ! )
</li><li>Some documentations have been rearranged
</li><li>Cliquer's graph_print function is added to cliquer.pxd if needed
</li></ul>
TicketncohenTue, 21 Jul 2009 08:16:27 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer-4.patch</em>
</li>
</ul>
TicketrlmTue, 21 Jul 2009 14:26:25 GMT
https://trac.sagemath.org/ticket/5793#comment:28
https://trac.sagemath.org/ticket/5793#comment:28
<p>
OK, you've done a ton of work on this. There are a few minor details left, but I will take care of them myself, and post a referee patch. This ticket should be ready today.
</p>
<p>
PS -- A maximum clique is just a clique of maximal size, so those functions are also applicable to Cliquer, but I'll update those myself. :)
</p>
TicketncohenTue, 21 Jul 2009 14:36:47 GMT
https://trac.sagemath.org/ticket/5793#comment:29
https://trac.sagemath.org/ticket/5793#comment:29
<p>
Thank you very much !! ;-)
</p>
<p>
Concerning the cliques, I agree when you say that a "A maximum clique is just a clique of maximal size", but a "maximal clique" is a clique such that there is no bigger clique in the graph -- according to the subset inclusion order (all the maximal cliques of a graph need not have the same cardinality) -- and this I what I thought I had read in the descriptions of the others functions.
</p>
<p>
And.... now that this seems to be finished, I only have left to take care of the LP/MIP patch, which seems quite another adventure... ;-)
</p>
<p>
Thanks again !
</p>
TicketrlmTue, 21 Jul 2009 17:18:06 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer-4-rebased-sage.4.1.patch</em>
</li>
</ul>
TicketrlmTue, 21 Jul 2009 18:04:16 GMT
https://trac.sagemath.org/ticket/5793#comment:30
https://trac.sagemath.org/ticket/5793#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5793#comment:29" title="Comment 29">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Concerning the cliques, I agree when you say that a "A maximum clique is just a clique of maximal size", but a "maximal clique" is a clique such that there is no bigger clique in the graph -- according to the subset inclusion order (all the maximal cliques of a graph need not have the same cardinality) -- and this I what I thought I had read in the descriptions of the others functions.
</p>
</blockquote>
<p>
I had realized this some time after writing that comment. Please forgive me.
</p>
TicketrlmTue, 21 Jul 2009 18:56:33 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>cliquer-5-ref.patch</em>
</li>
</ul>
<p>
Editing.
</p>
TicketrlmTue, 21 Jul 2009 18:57:50 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>trac_5793-cliquer-flattened.patch</em>
</li>
</ul>
<p>
Flattened patch based on sage-4.1.
</p>
TicketrlmTue, 21 Jul 2009 18:59:16 GMTsummary changed; reviewer, author set
https://trac.sagemath.org/ticket/5793#comment:31
https://trac.sagemath.org/ticket/5793#comment:31
<ul>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, positive review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
TicketrlmTue, 21 Jul 2009 19:01:01 GMTdescription changed
https://trac.sagemath.org/ticket/5793#comment:32
https://trac.sagemath.org/ticket/5793#comment:32
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/5793?action=diff&version=32">diff</a>)
</li>
</ul>
TicketrlmTue, 21 Jul 2009 19:03:15 GMT
https://trac.sagemath.org/ticket/5793#comment:33
https://trac.sagemath.org/ticket/5793#comment:33
<p>
In the last patch:
</p>
<ol><li>I made all clique related functions start with <code>clique_</code> so that you can do <code>G.clique<tab></code> and see all of them.
</li></ol><ol start="2"><li>Added a few doctests here and there
</li></ol><ol start="3"><li>Deprecated cliques, since it is ambiguous.
</li></ol>
TicketmvnguThu, 23 Jul 2009 04:32:09 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:34
https://trac.sagemath.org/ticket/5793#comment:34
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, positive review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
With the SPKG at <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a> and the patch on this ticket, I got the following doctest failures:
</p>
<pre class="wiki">sage -t -long devel/sage-main/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
**********************************************************************
File "/scratch/mvngu/release/sage-4.1.1.alpha0/devel/sage-main/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 318:
sage: clqs = (HS.complement()).cliques()
Expected nothing
Got:
doctest:1: DeprecationWarning: The function 'cliques' has been deprecated. Use 'cliques_maximal' or 'cliques_maximum'.
**********************************************************************
1 items had failures:
1 of 89 in __main__.example_2
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/mvngu/release/sage-4.1.1.alpha0/tmp/.doctest_refinement_graphs.py
[231.6 s]
<SNIP>
sage -t -long devel/sage-main/sage/graphs/graph_coloring.py
**********************************************************************
File "/scratch/mvngu/release/sage-4.1.1.alpha0/devel/sage-main/sage/graphs/graph_coloring.py", line 208:
sage: chromatic_number(G)
Expected:
3
Got:
doctest:224: DeprecationWarning: The function 'cliques' has been deprecated. Use 'cliques_maximal' or 'cliques_maximum'.
3
**********************************************************************
1 items had failures:
1 of 7 in __main__.example_5
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/mvngu/release/sage-4.1.1.alpha0/tmp/.doctest_graph_coloring.py
[2.3 s]
</pre>
TicketrlmThu, 23 Jul 2009 16:55:43 GMTsummary changed
https://trac.sagemath.org/ticket/5793#comment:35
https://trac.sagemath.org/ticket/5793#comment:35
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
Note: making the <code>refinement_graphs</code> doctest use Cliquer instead of NetworkX shaves about 21 seconds from the doctest time for the file!
</p>
TicketncohenThu, 23 Jul 2009 17:31:22 GMT
https://trac.sagemath.org/ticket/5793#comment:36
https://trac.sagemath.org/ticket/5793#comment:36
<p>
I do not really know how to read patch files, but it seems to me you replaced :
m = max([len(c) for c in G.cliques()])
by
m = max([len(c) for c in G.cliques_maximum()])
</p>
<p>
If right, I have two remarks :
</p>
<ul><li>The syntax of max([len(c) for c in G.cliques()]) makes me think that G.cliques() was meant to return the list of the maximAL cliques, and m is then meant to be the clique number of G. The expression max([len(c) for c in G.cliques_maximum()]) is syntaxically correct, thought as cliques_maximum returns only the maxiMUM cliques we may as well return the length of the first one as they all have the same size.
</li><li>In the end, and if I make no mistake, why about just setting m=G.clique_number() ?
</li></ul><p>
I expect it to be way faster than an enumeration of all the cliques ! ;-)
</p>
TicketrlmThu, 23 Jul 2009 17:37:19 GMTattachment set
https://trac.sagemath.org/ticket/5793
https://trac.sagemath.org/ticket/5793
<ul>
<li><strong>attachment</strong>
set to <em>trac_5793-part-6.patch</em>
</li>
</ul>
<p>
Apply on top of flattened patch
</p>
TicketrlmThu, 23 Jul 2009 17:37:50 GMT
https://trac.sagemath.org/ticket/5793#comment:37
https://trac.sagemath.org/ticket/5793#comment:37
<p>
Nathann,
</p>
<p>
Thanks for spotting that. The patch is updated!
</p>
TicketmvnguFri, 31 Jul 2009 17:50:10 GMTreviewer, summary changed
https://trac.sagemath.org/ticket/5793#comment:38
https://trac.sagemath.org/ticket/5793#comment:38
<ul>
<li><strong>reviewer</strong>
changed from <em>Robert Miller</em> to <em>Robert Miller, Minh Van Nguyen</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] New algorithm for Max Clique in Graph class using Cython</em> to <em>[with patch, positive review] New algorithm for Max Clique in Graph class using Cython</em>
</li>
</ul>
<p>
I applied patches in the following order:
</p>
<ol><li>the SPKG at <a class="closed ticket" href="https://trac.sagemath.org/ticket/6355" title="enhancement: [with spkg, positive review] Cliquer to compute maximum cliques (closed: fixed)">#6355</a>
</li><li><code>trac_5793-cliquer-flattened.patch</code>
</li><li><code>trac_5793-part-6.patch</code>
</li></ol><p>
All doctests passed with Sage 4.1.1.rc0. So positive review.
</p>
TicketmvnguFri, 31 Jul 2009 23:32:09 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/5793#comment:39
https://trac.sagemath.org/ticket/5793#comment:39
<ul>
<li><strong>status</strong>
changed from <em>reopened</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>Sage 4.1.1.rc1</em>
</li>
</ul>
Ticket