Sage: Ticket #13917: IndependentSets class
https://trac.sagemath.org/ticket/13917
<p>
I'm rather disappointed by this patch. Or I'm pleasantly surprised by Python, I don't know. I expected a much better speedup.
</p>
<pre class="wiki">sage: g = graphs.RandomGNP(50,.7)
sage: import networkx
sage: gn = g.networkx_graph()
sage: %timeit list(networkx.find_cliques(gn))
10 loops, best of 3: 48.8 ms per loop
sage: from sage.graphs.independent_sets import IndependentSets
sage: %timeit list(IndependentSets(g,complement=True, maximal = True))
10 loops, best of 3: 20.8 ms per loop
sage: %timeit IndependentSets(g,complement=True, maximal = True).cardinality()
100 loops, best of 3: 19 ms per loop
</pre><p>
Either way, this patch implements a <code>sage.graphs.independent_set</code> module that can list/count (possibly maximal) independent sets. While right now we can only compute the maximal ones.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13917
Trac 1.1.6ncohenSun, 06 Jan 2013 17:21:12 GMTstatus changed
https://trac.sagemath.org/ticket/13917#comment:1
https://trac.sagemath.org/ticket/13917#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketahmoralesTue, 28 May 2013 16:22:01 GMT
https://trac.sagemath.org/ticket/13917#comment:2
https://trac.sagemath.org/ticket/13917#comment:2
<p>
I think this patch is useful. I was looking for something to count independents sets of a given size since they index certain triangulations of polytopes coming from flows on graphs (<a class="closed ticket" href="https://trac.sagemath.org/ticket/14654" title="enhancement: implement flow polytopes (closed: fixed)">#14654</a>).
</p>
TicketahmoralesTue, 28 May 2013 16:23:12 GMTreviewer set
https://trac.sagemath.org/ticket/13917#comment:3
https://trac.sagemath.org/ticket/13917#comment:3
<ul>
<li><strong>reviewer</strong>
set to <em>ahmorales</em>
</li>
</ul>
TicketncohenWed, 29 May 2013 16:08:59 GMTattachment set
https://trac.sagemath.org/ticket/13917
https://trac.sagemath.org/ticket/13917
<ul>
<li><strong>attachment</strong>
set to <em>trac_13917.patch</em>
</li>
</ul>
TicketvdelecroixWed, 29 May 2013 16:11:40 GMTcc set
https://trac.sagemath.org/ticket/13917#comment:4
https://trac.sagemath.org/ticket/13917#comment:4
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
</ul>
TicketvdelecroixWed, 29 May 2013 16:45:56 GMT
https://trac.sagemath.org/ticket/13917#comment:5
https://trac.sagemath.org/ticket/13917#comment:5
<p>
Hi,
</p>
<p>
People from statistical physics are interested in finer quantities than the number of independent configurations (independent sets are related to particule interactions). In their case each configuration is counted with a weight of the form <code>$\prod_{v \in I} \lambda(v)$</code> where <code>$\lambda: V \rightarrow \mathbb{R}_+$</code> is a function on the vertices. Considering the case of $\lambda$ being constant, the code could even return the polynomial <code>$f(\lambda)$</code> whose coefficient for <code>$\lambda^k$</code> is the number of independent set with <code>$k$</code> vertices (or equivalently the list of number of independent set of given size). Perhaps this polynomial has a name in graph theory ?
</p>
<p>
I let the serious comments to the reviewer.
</p>
<p>
Vincent
</p>
TicketvdelecroixSat, 01 Jun 2013 16:20:55 GMTstatus, description changed; work_issues set
https://trac.sagemath.org/ticket/13917#comment:6
https://trac.sagemath.org/ticket/13917#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>design, documentation</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13917?action=diff&version=6">diff</a>)
</li>
</ul>
<p>
0) I found your patch useful!
</p>
<p>
0') I thought that in your timing most of the time was lost in the creation of the list and the for loop... but no: it is not much faster to enumerate all independent set rather than counting them with the method cardinality (I update the example in the description). So, I am as well surprised by <code>Python/Cython</code>.
</p>
<p>
<strong>Todo</strong>
</p>
<p>
1) I am not sure the following is what we want
</p>
<pre class="wiki">sage: I = independent_sets.IndependentSets(graphs.PetersenGraph())
sage: i1 = iter(I); sage: i2 = iter(I)
sage: i1.next()
[0]
sage: i2.next()
[0, 2]
sage: i1.next()
[0, 2, 6]
sage: i2.next()
[0, 2, 8]
</pre><p>
In other words an iterator is an iterator and nothing else. If you want to design the set of independent sets it should be an object different from the iterator. It would be better to have a Python class <code>IndependentSets</code> desinged to modelize the set of independent sets (it should inherit from <code>Parent</code> :P) and a Cython iterator <code>IndependentSetIterator</code>. What do you think?
</p>
<p>
2) Could you provide a method to graph (independent_set_iterator or/and independent_sets)?
</p>
<p>
3) The flag count_only allows to count the number of independent set in only one call to <code>__next__</code> (if you do replace "return []" by "if not self.count_only: return []"). Your solution is a bit hackish and moreover the "for i in self: pass" needs to catch the <code>StopIteration</code>.
</p>
<p>
<strong>Possible improvements</strong>
</p>
<p>
1) With the current implementation it would be easy to provide the number of independent set of each cardinality and to iterate through the set of independent set of given cardinality.
</p>
<p>
<strong>Documentation</strong>
</p>
<p>
1) The complement of an independent set is a dominating set, right (not a clique) ? If so, please change the documentation accordingly.
</p>
<p>
2) wikipedia links might be useful :<a class="ext-link" href="http://en.wikipedia.org/wiki/Independent_set_(graph_theory" title="Independent_set_(graph_theory in WikiPedia"><span class="icon"></span>wikipedia:Independent_set_(graph_theory</a>), :<a class="ext-link" href="http://en.wikipedia.org/wiki/Dominating_set" title="Dominating_set in WikiPedia"><span class="icon"></span>wikipedia:Dominating_set</a>, :<a class="ext-link" href="http://en.wikipedia.org/wiki/Clique_graph" title="Clique_graph in WikiPedia"><span class="icon"></span>wikipedia:Clique_graph</a>
</p>
TicketncohenMon, 03 Jun 2013 14:24:52 GMT
https://trac.sagemath.org/ticket/13917#comment:7
https://trac.sagemath.org/ticket/13917#comment:7
<p>
Yoooooooooooo !!
</p>
<blockquote class="citation">
<p>
0) I found your patch useful!
</p>
</blockquote>
<p>
Cool !
</p>
<blockquote class="citation">
<p>
0') I thought that in your timing most of the time was lost in the creation of the list and the for loop... but no: it is not much faster to enumerate all independent set rather than counting them with the method cardinality (I update the example in the description). So, I am as well surprised by <code>Python/Cython</code>.
</p>
</blockquote>
<p>
Yep <code>O_o</code>
</p>
<blockquote class="citation">
<p>
1) I am not sure the following is what we want
</p>
</blockquote>
<p>
Ok. So what you want is an empty class that does nothing, which calls another class that does all the job ? It cannot be just an independent iterator, for I also want to compute the number of cliques without having to compute all the lists of elements at Python level.
</p>
<blockquote class="citation">
<p>
In other words an iterator is an iterator and nothing else.
</p>
</blockquote>
<p>
Says the dogma.
</p>
<blockquote class="citation">
<p>
If you want to design the set of independent sets it should be an object different from the iterator.
</p>
</blockquote>
<p>
Says the dogma.
</p>
<blockquote class="citation">
<p>
It would be better to have a Python class <code>IndependentSets</code> desinged to modelize the set of independent sets
</p>
</blockquote>
<p>
And what on earth would it do that is not a feature of the iterator ?
</p>
<blockquote class="citation">
<p>
(it should inherit from <code>Parent</code> :P)
</p>
</blockquote>
<p>
Over my dead body.
</p>
<blockquote class="citation">
<p>
and a Cython iterator <code>IndependentSetIterator</code>. What do you think?
</p>
</blockquote>
<p>
I will not create an empty class if I can avoid it.
</p>
<blockquote class="citation">
<p>
2) Could you provide a method to graph (independent_set_iterator or/and independent_sets)?
</p>
</blockquote>
<p>
Actually I avoided it on purpose. I felt like this thing was not interesting for everybody, and that it should belong to a module one would load when needed, rather than add a new function to Graph.... What do you think ? It's not like one wants to enumerate independent sets every other day.
</p>
<blockquote class="citation">
<p>
3) The flag count_only allows to count the number of independent set in only one call to <code>__next__</code> (if you do replace "return []" by "if not self.count_only: return []"). Your solution is a bit hackish and moreover the "for i in self: pass" needs to catch the <code>StopIteration</code>.
</p>
</blockquote>
<p>
I will rewrite this part using $14589 as a dependency. It's a bit stupid to deal with <64 vertices graphs only.
</p>
<blockquote class="citation">
<p>
1) With the current implementation it would be easy to provide the number of independent set of each cardinality and to iterate through the set of independent set of given cardinality.
</p>
</blockquote>
<p>
And it already is :
</p>
<pre class="wiki">n_sets = [0]*g.order()
for s in IndependentSets(g):
n_sets[len(s)] += 1
</pre><p>
What do you want ? Ugly "if" everywhere in the main loop to filter this before returning them ?...
</p>
<blockquote class="citation">
<p>
1) The complement of an independent set is a dominating set, right (not a clique) ? If so, please change the documentation accordingly.
</p>
</blockquote>
<p>
The complement of an independent set is a vertex cover (and very often a dominating set too, unless the graph has isolated vertices), but an independent set of the <complement of the graph> is a clique. Was that the problem ?
</p>
<blockquote class="citation">
<p>
2) wikipedia links might be useful :<a class="ext-link" href="http://en.wikipedia.org/wiki/Independent_set_(graph_theory" title="Independent_set_(graph_theory in WikiPedia"><span class="icon"></span>wikipedia:Independent_set_(graph_theory</a>), :<a class="ext-link" href="http://en.wikipedia.org/wiki/Dominating_set" title="Dominating_set in WikiPedia"><span class="icon"></span>wikipedia:Dominating_set</a>, :<a class="ext-link" href="http://en.wikipedia.org/wiki/Clique_graph" title="Clique_graph in WikiPedia"><span class="icon"></span>wikipedia:Clique_graph</a>
</p>
</blockquote>
<p>
Right, right. I will add them to the next version of this patch.
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 03 Jun 2013 15:07:10 GMT
https://trac.sagemath.org/ticket/13917#comment:8
https://trac.sagemath.org/ticket/13917#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:7" title="Comment 7">ncohen</a>:
</p>
<p>
Hey!
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
(it should inherit from <code>Parent</code> :P)
</p>
</blockquote>
<p>
Over my dead body.
</p>
</blockquote>
<p>
(-: you should love your parents :-)
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
and a Cython iterator <code>IndependentSetIterator</code>. What do you think?
</p>
</blockquote>
<p>
I will not create an empty class if I can avoid it.
</p>
</blockquote>
<p>
And what about
</p>
<pre class="wiki">sage: from sage.graphs.independent_sets import IndependentSets
sage: I = IndependentSets(g,complement=True, maximal = True)
sage: I.next()
[0, 1, 2, 9, 19, 35, 40, 43, 47]
sage: I.cardinality()
4457
sage: I.next()
Traceback (most recent call last):
...
StopIteration:
</pre><p>
Your class is in between:
</p>
<ul><li>an iterator
</li><li>an object that modelises the set of independent sets (the methods <code>cardinality</code> and <code>__contains__</code>)
</li></ul><p>
Doing both purposes at the same time implies many unsatisfactory behaviors. What I suggest is an iterator that iterates and a class that answers to <code>__contains__</code> and <code>cardinality</code>. But this is not satisfactory either because you still have to hack the iterator to get the cardinality.
</p>
<p>
It might be your choice to have a multiple purposes class. If so, specify it in the documentation as : "you can either use the class to iterate (though only once) or compute the cardinality, but do not think that you can do both in a clean way".
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
2) Could you provide a method to graph (independent_set_iterator or/and independent_sets)?
</p>
</blockquote>
<p>
Actually I avoided it on purpose. I felt like this thing was not interesting for everybody, and that it should belong to a module one would load when needed, rather than add a new function to Graph.... What do you think ? It's not like one wants to enumerate independent sets every other day.
</p>
</blockquote>
<p>
I agree!
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
3) The flag count_only allows to count the number of independent set in only one call to <code>__next__</code> (if you do replace "return []" by "if not self.count_only: return []"). Your solution is a bit hackish and moreover the "for i in self: pass" needs to catch the <code>StopIteration</code>.
</p>
</blockquote>
<p>
I will rewrite this part using $14589 as a dependency. It's a bit stupid to deal with <64 vertices graphs only.
</p>
<blockquote class="citation">
<p>
1) With the current implementation it would be easy to provide the number of independent set of each cardinality and to iterate through the set of independent set of given cardinality.
</p>
</blockquote>
<p>
And it already is :
</p>
<pre class="wiki">n_sets = [0]*g.order()
for s in IndependentSets(g):
n_sets[len(s)] += 1
</pre><p>
What do you want ? Ugly "if" everywhere in the main loop to filter this before returning them ?...
</p>
</blockquote>
<p>
No. What I meant is to consider a more general attribute <code>.count</code> of type <code>int[64]</code> which contains the number of independent set of each cardinality. But your solution is satisfactory and you can keep the implementation as it is. Could you add your clever solution to the documentation?
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
1) The complement of an independent set is a dominating set, right (not a clique) ? If so, please change the documentation accordingly.
</p>
</blockquote>
<p>
The complement of an independent set is a vertex cover (and very often a dominating set too, unless the graph has isolated vertices), but an independent set of the <complement of the graph> is a clique. Was that the problem ?
</p>
</blockquote>
<p>
My mistake.
</p>
TicketncohenWed, 05 Jun 2013 13:54:03 GMT
https://trac.sagemath.org/ticket/13917#comment:9
https://trac.sagemath.org/ticket/13917#comment:9
<p>
(new patch that works with >64 vertices, based on top of 14589. And even slower than the first one <code>>_<</code>)
</p>
<p>
Nathann
</p>
TicketncohenWed, 05 Jun 2013 14:54:47 GMTdescription changed
https://trac.sagemath.org/ticket/13917#comment:10
https://trac.sagemath.org/ticket/13917#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13917?action=diff&version=10">diff</a>)
</li>
</ul>
TicketncohenThu, 06 Jun 2013 09:20:24 GMTstatus changed; dependencies set
https://trac.sagemath.org/ticket/13917#comment:11
https://trac.sagemath.org/ticket/13917#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#14589</em>
</li>
</ul>
<p>
Newwwwwwww patch !!!!
</p>
<ul><li>It now deals with graphs of arbitrary size (using the binary matrices from <a class="closed ticket" href="https://trac.sagemath.org/ticket/14589" title="enhancement: binary matrices, dense graphs, and faster is_strongly_regular (closed: fixed)">#14589</a>)
</li></ul><ul><li>I spent quite some time complaining to myself (and to Florent) about creating an empty <code>IndependentSets</code> class which would call an <code>IndependentSetsIterator</code> class. He also agreed with you Vincent, and even though I did not like this problem with double loops either, I still refused to write an empty class.
</li></ul><blockquote>
<p>
Because I hate empty classes.
</p>
</blockquote>
<blockquote>
<p>
Turns out that there is a nice way out, that I stupidly did not notice : instead of writing a <code>.next()</code> method, I moved the code to <code>.__iter__()</code>, and replaced the <code>return</code> by <code>yield</code>. And many global variables are now local to <code>.__iter__()</code>, and everything goes well under the sun <code>:-P</code>
</p>
</blockquote>
<pre class="wiki">sage: g = graphs.PetersenGraph()
sage: from sage.graphs.independent_sets import IndependentSets
sage: IS = IndependentSets(g)
sage: IS2 = [(x,y) for x in IS for y in IS]
sage: len(IS2)
5776
sage: IS.cardinality()**2
5776
</pre><ul><li>I added a comment about the difference in speed between this implementation and NetworkX
</li></ul><ul><li>Annnnnnd I added some links toward Wikipedia.
</li></ul><p>
Tell me if you like it <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 06 Jun 2013 09:20:42 GMTattachment set
https://trac.sagemath.org/ticket/13917
https://trac.sagemath.org/ticket/13917
<ul>
<li><strong>attachment</strong>
set to <em>trac_13917-v2.patch</em>
</li>
</ul>
TicketvdelecroixThu, 06 Jun 2013 19:37:09 GMTattachment set
https://trac.sagemath.org/ticket/13917
https://trac.sagemath.org/ticket/13917
<ul>
<li><strong>attachment</strong>
set to <em>trac_13917-v2-more_doc.patch</em>
</li>
</ul>
TicketvdelecroixThu, 06 Jun 2013 19:37:43 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/13917#comment:12
https://trac.sagemath.org/ticket/13917#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
<em>design, documentation</em> deleted
</li>
</ul>
<p>
You are a clever guy as you found a solution that satisfy both of us!
</p>
<p>
Some new comments
</p>
<p>
0) Nobody would access the documentation in <code>__iter__</code> or <code>__contains__</code>. I modified the documentation accordingly.
</p>
<p>
1) you should move <code>bitset_are_disjoint</code> to <code>sage.misc.bitset</code> as somebody else may want to use it.
</p>
<p>
2) your example to iterate over the independent set of given cardinality is nice to learn Python but not to learn a good algorithm... If I want the independent sets of cardinality 1 of a grid graph 12x12 it will take an hour just to obtain my 144 independent sets.
</p>
<p>
3)
</p>
<pre class="wiki">sage: G = graphs.CubeGraph(5)
sage: I = IndependentSets(G)
sage: [0,1,2,3] in I
BOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!
</pre><p>
4)
</p>
<pre class="wiki">sage: IndependentSets(graphs.EmptyGraph())
REBOOOOOOOOOOOOOOOOOOOOOOOOOOM!!
</pre>
TicketncohenThu, 06 Jun 2013 21:53:53 GMTstatus changed
https://trac.sagemath.org/ticket/13917#comment:13
https://trac.sagemath.org/ticket/13917#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hellooooooooo !!
</p>
<blockquote class="citation">
<p>
0) Nobody would access the documentation in <code>__iter__</code> or <code>__contains__</code>. I modified the documentation accordingly.
</p>
</blockquote>
<p>
Oh. Right.
</p>
<blockquote class="citation">
<p>
1) you should move <code>bitset_are_disjoint</code> to <code>sage.misc.bitset</code> as somebody else may want to use it.
</p>
</blockquote>
<p>
Hmmmm... I did not move it there for the function does not take bitsets as input, but <code>unsigned long *</code> pointers... So I felt that it did not belong there. If you are convinced that it should be there, no problem and I will move it. I really had no idea.
</p>
<blockquote class="citation">
<p>
2) your example to iterate over the independent set of given cardinality is nice to learn Python but not to learn a good algorithm... If I want the independent sets of cardinality 1 of a grid graph 12x12 it will take an hour just to obtain my 144 independent sets.
</p>
</blockquote>
<p>
Hmmm.. <code>-_-</code>
Right.
</p>
<p>
Do you want me to add options to list independent sets with a special filter according to the number of vertices ?
</p>
<blockquote class="citation">
<p>
3)
</p>
<pre class="wiki">sage: G = graphs.CubeGraph(5)
sage: I = IndependentSets(G)
sage: [0,1,2,3] in I
BOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!
</pre><p>
4)
</p>
<pre class="wiki">sage: IndependentSets(graphs.EmptyGraph())
REBOOOOOOOOOOOOOOOOOOOOOOOOOOM!!
</pre></blockquote>
<p>
Oh. I saw your <code>ProgrammerError</code> in the patch, but there is no segfault on my side. When I run your commands, here is what I get :
</p>
<pre class="wiki">sage: from sage.graphs.independent_sets import IndependentSets sage: from sage.graphs.independent_sets
sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.CubeGraph(5)
sage: I = IndependentSets(G)
sage: [0,1,2,3] in I
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-9-a8f48211b650> in <module>()
----> 1 [Integer(0),Integer(1),Integer(2),Integer(3)] in I
/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/independent_sets.so in sage.graphs.independent_sets.IndependentSets.__contains__ (build/cythonized/sage/graphs/independent_sets.c:5633)()
ValueError: An element of the set being tested does not belong to
</pre><p>
Admittedly the error message has to be fixed, but no segfault. <code>O_o</code>
</p>
<p>
The empty graph produces a segfault allright. But of course the empty graph is not really a graph <code>:-P</code>
</p>
<p>
Tell me what you think, and I will write an additional patch. And thank you for your review !
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 07 Jun 2013 06:13:58 GMT
https://trac.sagemath.org/ticket/13917#comment:14
https://trac.sagemath.org/ticket/13917#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:13" title="Comment 13">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
1) you should move <code>bitset_are_disjoint</code> to <code>sage.misc.bitset</code> as somebody else may want to use it.
</p>
</blockquote>
<p>
Hmmmm... I did not move it there for the function does not take bitsets as input, but <code>unsigned long *</code> pointers... So I felt that it did not belong there. If you are convinced that it should be there, no problem and I will move it. I really had no idea.
</p>
</blockquote>
<p>
I see why now. I thought that a bitset was a "unsigned long *" but it is a struct that contains it. is nothing more than an "unsigned long *". I would prefer if you move your function and make it takes bitset_s (= bitset_t *) as input.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
2) your example to iterate over the independent set of given cardinality is nice to learn Python but not to learn a good algorithm... If I want the independent sets of cardinality 1 of a grid graph 12x12 it will take an hour just to obtain my 144 independent sets.
</p>
</blockquote>
<p>
Hmmm.. <code>-_-</code>
Right.
</p>
<p>
Do you want me to add options to list independent sets with a special filter according to the number of vertices ?
</p>
</blockquote>
<p>
I see two solutions:
</p>
<ul><li>You do not want to do the change, then mention, just next to the example, that this is not necessarily a good idea
</li><li>add a special filter according to the number of vertices (it is straightforward to add constants min_num_verts and max_num_verts within your iterator)
</li></ul><blockquote class="citation">
<blockquote class="citation">
<p>
3)
[...]
BOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!
[...]
REBOOOOOOOOOOOOOOOOOOOOOOOOOOM!!
[...]
</p>
</blockquote>
<p>
Oh. I saw your <code>ProgrammerError</code> in the patch, but there is no segfault on my side.
[...]
Admittedly the error message has to be fixed, but no segfault. <code>O_o</code>
</p>
<p>
The empty graph produces a segfault allright. But of course the empty graph is not really a graph <code>:-P</code>
</p>
</blockquote>
<p>
Your computer is better than mine ;-) What sage version are you running ? I will compile the rc1 and see what I get (I was on 5.10.beta4).
</p>
TicketncohenFri, 07 Jun 2013 09:51:21 GMT
https://trac.sagemath.org/ticket/13917#comment:15
https://trac.sagemath.org/ticket/13917#comment:15
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I see why now. I thought that a bitset was a "unsigned long *" but it is a struct that contains it. is nothing more than an "unsigned long *". I would prefer if you move your function and make it takes bitset_s (= bitset_t *) as input.
</p>
</blockquote>
<p>
I really need a function that takes <code>unsigned long *</code> as input, because this is what the binary matrices store. Inside of a bitset structure, there is also a <code>.bits</code> field that is of type <code>unsigned long *</code>, but if I want to convert my <code>unsigned long *</code> to a bitset, then I need either to allocate a new array or to mess with a bitset data structure before calling the new version of the function that would take bitsets as input.
And it looks like a waste of time.
</p>
<p>
I really need a function that takes <code>unsigned long *</code> as input.
</p>
<blockquote class="citation">
<ul><li>You do not want to do the change, then mention, just next to the example, that this is not necessarily a good idea
</li></ul></blockquote>
<p>
I can do it. I don't mind.
</p>
<blockquote class="citation">
<ul><li>add a special filter according to the number of vertices (it is straightforward to add constants min_num_verts and max_num_verts within your iterator)
</li></ul></blockquote>
<p>
I hope that this will not change the speed of the computations, though.
</p>
<blockquote class="citation">
<p>
Your computer is better than mine ;-) What sage version are you running ?
</p>
</blockquote>
<p>
Sage-5.10.rc0. But I don't see why mine would not see a segfault that occurs on yours. Usually, the one who gets the segfaults is right, and the one who does not get it is just lucky. There may be a problem somewhere.
</p>
<blockquote class="citation">
<p>
I will compile the rc1 and see what I get (I was on 5.10.beta4).
</p>
</blockquote>
<p>
Okayyyyyyy.
</p>
<p>
Still waiting for your answer before I write the additional patch.
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 07 Jun 2013 12:20:06 GMT
https://trac.sagemath.org/ticket/13917#comment:16
https://trac.sagemath.org/ticket/13917#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:15" title="Comment 15">ncohen</a>:
</p>
<p>
A stupid comment I was doing myself:
</p>
<p>
The set of independent sets has an acylcic oriented graph structure (two ind. set are neighbors if you pass from one to the other by removing or adding a vertex). What you do in your algorithm is that, by considering an order on the vertices, you can easily build a tree out of this acyclic graph. So, in principle, it would possible to explore the graph with much less backtracking... I wonder if this is along those lines that something clever is done in networkx...
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>You do not want to do the change, then mention, just next to the example, that this is not necessarily a good idea
</li></ul></blockquote>
<p>
I can do it. I don't mind.
</p>
<blockquote class="citation">
<ul><li>add a special filter according to the number of vertices (it is straightforward to add constants min_num_verts and max_num_verts within your iterator)
</li></ul></blockquote>
<p>
I hope that this will not change the speed of the computations, though.
</p>
</blockquote>
<p>
If you have the time to try, please do. I can not imagine that you will see a difference with two test conditions. Otherwise, the first solution is ok.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Your computer is better than mine ;-) What sage version are you running ?
</p>
</blockquote>
<p>
Sage-5.10.rc0. But I don't see why mine would not see a segfault that occurs on yours. Usually, the one who gets the segfaults is right, and the one who does not get it is just lucky. There may be a problem somewhere.
</p>
<blockquote class="citation">
<p>
I will compile the rc1 and see what I get (I was on 5.10.beta4).
</p>
</blockquote>
</blockquote>
<p>
on rc1 it works fine...
</p>
TicketncohenFri, 07 Jun 2013 13:57:50 GMTstatus changed
https://trac.sagemath.org/ticket/13917#comment:17
https://trac.sagemath.org/ticket/13917#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hellooooooooooo !!
</p>
<blockquote class="citation">
<p>
The set of independent sets has an acylcic oriented graph structure (two ind. set are neighbors if you pass from one to the other by removing or adding a vertex). What you do in your algorithm is that, by considering an order on the vertices, you can easily build a tree out of this acyclic graph. So, in principle, it would possible to explore the graph with much less backtracking... I wonder if this is along those lines that something clever is done in networkx...
</p>
</blockquote>
<p>
Hmmmmm... I don't get it <code>O_o</code>
</p>
<p>
If you do nothing but talk of the exploration tree then I do not see how you can beat this implementation : it goes through this tree and only remembers the name of the current node... I don't see it getting much cheaper <code>O_o</code>
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I can do it. I don't mind.
</p>
</blockquote>
</blockquote>
<p>
Hmmm... Turns out that when looking at the code again, it required to store a variable containing the current number of elements in the set, and add +=1 and -=1 in several places... Soooooo if you don't need it I would prefer not to implement this here. I added a message saying that the iterator trick is not computationally smart.
</p>
<blockquote class="citation">
<p>
on rc1 it works fine...
</p>
</blockquote>
<p>
I fixed the segfault on empty graphs, and they are now supported too by this class. This way nothing bad happens when it is called from Graph.cliques_maximal.
</p>
<p>
Patch updated ! <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketncohenFri, 07 Jun 2013 13:58:03 GMTattachment set
https://trac.sagemath.org/ticket/13917
https://trac.sagemath.org/ticket/13917
<ul>
<li><strong>attachment</strong>
set to <em>trac_13917-doctests.patch</em>
</li>
</ul>
TicketncohenFri, 07 Jun 2013 13:58:43 GMTdescription changed
https://trac.sagemath.org/ticket/13917#comment:18
https://trac.sagemath.org/ticket/13917#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13917?action=diff&version=18">diff</a>)
</li>
</ul>
TicketvdelecroixFri, 07 Jun 2013 14:16:19 GMT
https://trac.sagemath.org/ticket/13917#comment:19
https://trac.sagemath.org/ticket/13917#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:17" title="Comment 17">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hellooooooooooo !!
</p>
<blockquote class="citation">
<p>
The set of independent sets has an acylcic oriented graph structure (two ind. set are neighbors if you pass from one to the other by removing or adding a vertex). What you do in your algorithm is that, by considering an order on the vertices, you can easily build a tree out of this acyclic graph. So, in principle, it would possible to explore the graph with much less backtracking... I wonder if this is along those lines that something clever is done in networkx...
</p>
</blockquote>
<p>
Hmmmmm... I don't get it <code>O_o</code>
</p>
<p>
If you do nothing but talk of the exploration tree then I do not see how you can beat this implementation : it goes through this tree and only remembers the name of the current node... I don't see it getting much cheaper <code>O_o</code>
</p>
</blockquote>
<p>
I just read <a class="ext-link" href="ftp://ftp-sop.inria.fr/abs/fcazals/papers/ncliques.pdf"><span class="icon"></span>Cazals Karande 2008</a> and in the algorithm they expose: they deal with smaller and smaller graphs at each step and this is what makes the networkx implementation faster. It starts from the stupid remark: I have a candidate u to add to my ind. set, if I add it then I should remove its neighbors from the graph.
</p>
<p>
Basically, at each step, you store three sets: R (current indep. set), P (vertices away from R), X (vertices away from R but yet used) and you assume that P u X are all neighbors of R. Then for each vertex in P you add it to R, then update P and R, explore from there and then add the vertex to X. When X is empty, then you get an independent set, when P and X are empty you get a maximal independent set.
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
I can do it. I don't mind.
</p>
</blockquote>
</blockquote>
<p>
Hmmm... Turns out that when looking at the code again, it required to store a variable containing the current number of elements in the set, and add +=1 and -=1 in several places... Soooooo if you don't need it I would prefer not to implement this here. I added a message saying that the iterator trick is not computationally smart.
</p>
</blockquote>
<p>
Ok.
</p>
<blockquote class="citation">
<p>
Patch updated ! <code>;-)</code>
</p>
</blockquote>
<p>
Ok
</p>
TicketncohenFri, 09 Aug 2013 12:25:29 GMT
https://trac.sagemath.org/ticket/13917#comment:20
https://trac.sagemath.org/ticket/13917#comment:20
<p>
Ping ? <code>:-P</code>
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/13917#comment:21
https://trac.sagemath.org/ticket/13917#comment:21
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketncohenWed, 18 Dec 2013 10:09:14 GMTdescription changed
https://trac.sagemath.org/ticket/13917#comment:22
https://trac.sagemath.org/ticket/13917#comment:22
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13917?action=diff&version=22">diff</a>)
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/13917#comment:23
https://trac.sagemath.org/ticket/13917#comment:23
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketncohenThu, 13 Mar 2014 11:39:41 GMTdescription changed; commit, branch set
https://trac.sagemath.org/ticket/13917#comment:24
https://trac.sagemath.org/ticket/13917#comment:24
<ul>
<li><strong>commit</strong>
set to <em>1be18a591f289740796242cfe07d7736801301d8</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13917?action=diff&version=24">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/13917</em>
</li>
</ul>
<p>
(now with a git branch)
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cc8d994d4d59309ff45755d55337e1f18cbae7d3"><span class="icon"></span>cc8d994</a></td><td><code>trac #13917: IndependentSets class</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d01cefb56b74b3f5e423bd86735ada4526ce8e35"><span class="icon"></span>d01cefb</a></td><td><code>trac #13917: add more documentation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1be18a591f289740796242cfe07d7736801301d8"><span class="icon"></span>1be18a5</a></td><td><code>trac #13917: doctests</code>
</td></tr></table>
TicketgitThu, 13 Mar 2014 11:52:04 GMTcommit changed
https://trac.sagemath.org/ticket/13917#comment:25
https://trac.sagemath.org/ticket/13917#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>1be18a591f289740796242cfe07d7736801301d8</em> to <em>2e15c7d32b035a865de6ab45b30dc3c87cb19103</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2e15c7d32b035a865de6ab45b30dc3c87cb19103"><span class="icon"></span>2e15c7d</a></td><td><code>trac #13917: A couple of mistakes</code>
</td></tr></table>
TicketvdelecroixThu, 13 Mar 2014 15:05:18 GMTreviewer changed
https://trac.sagemath.org/ticket/13917#comment:26
https://trac.sagemath.org/ticket/13917#comment:26
<ul>
<li><strong>reviewer</strong>
changed from <em>ahmorales</em> to <em>ahmorales, Vincent Delecroix</em>
</li>
</ul>
<ul><li>I do not like line 168 of independent_sets.py and expecially <code>G.__class__(n)</code> It looks offuscated to me... I replaced it with <code>Graph(n)</code>. I am not sure this is the same so please double check.
</li><li>I changed the 0 to a 4 in line 114.
</li><li>Regarding <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:6" title="Comment 6">comment:6</a> of me (Possible improvements), note that <a class="ticket" href="https://trac.sagemath.org/ticket/13917#comment:2" title="Comment 2">comment:2</a> of ahmorales advocates for having the iterator for independent sets of fixed size ! So I added it into a TODO section.
</li></ul><p>
See <code>u/vdelecroix/13917</code> and this is good to go (after your check of point 1 above).
</p>
TicketncohenThu, 13 Mar 2014 16:37:11 GMT
https://trac.sagemath.org/ticket/13917#comment:27
https://trac.sagemath.org/ticket/13917#comment:27
<p>
Helloooooooooooooooooooooo !!!
</p>
<p>
I think that this 0 was meant to be a 10 or something. Anyway thank you for changing it.
</p>
<p>
About <code>G.__class__</code> : no idea why it was written this way. The only point of this is to create a <code>Graph</code> when G is a <code>Graph</code> and a <code>DiGraph</code> when G is a <code>DiGraph</code>, but really, there, it served no purpose at all.
</p>
<p>
About the TODO section. HMmmm... I don't like this much, because to me it is not a "todo" at all. It is just ideas for improvement. It is not something that must be done, it is just ideas.... "Possible improvements" would fit better I think. Well. 'tsup to you <code>:-)</code>
</p>
<p>
I will upload a small commit in a second, because the second <code>check_matching</code> which is defined in the code is not about matchings at all. Annnnd then you can decide what this patch becomes.
</p>
<p>
Have fuuuuuuuun and thank you again <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketgitThu, 13 Mar 2014 16:41:54 GMTcommit changed
https://trac.sagemath.org/ticket/13917#comment:28
https://trac.sagemath.org/ticket/13917#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>2e15c7d32b035a865de6ab45b30dc3c87cb19103</em> to <em>5aeaccffe6193a42f7a06399198f043fb9ab8302</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=86bc3fd20984ad9cfcc1b764ae44ed501e8d9952"><span class="icon"></span>86bc3fd</a></td><td><code>documentation improvement</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=825f8f6f03345c771d9a99e75202ef7d346ea8b5"><span class="icon"></span>825f8f6</a></td><td><code>Todo section</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5aeaccffe6193a42f7a06399198f043fb9ab8302"><span class="icon"></span>5aeaccf</a></td><td><code>trac #13917: A misnamed function</code>
</td></tr></table>
TicketvdelecroixThu, 13 Mar 2014 18:38:32 GMTstatus, commit, branch, reviewer changed
https://trac.sagemath.org/ticket/13917#comment:29
https://trac.sagemath.org/ticket/13917#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>commit</strong>
changed from <em>5aeaccffe6193a42f7a06399198f043fb9ab8302</em> to <em>09052a0520aa205aaa7af9d0e60c8e1c5574bd1b</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/13917</em> to <em>u/vdelecroix/13917</em>
</li>
<li><strong>reviewer</strong>
changed from <em>ahmorales, Vincent Delecroix</em> to <em>Vincent Delecroix</em>
</li>
</ul>
<p>
In my last commit, I removed the TODO and put the comment in the NOTE.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=09052a0520aa205aaa7af9d0e60c8e1c5574bd1b"><span class="icon"></span>09052a0</a></td><td><code>remove the TODO and put the comment in NOTE</code>
</td></tr></table>
TicketncohenThu, 13 Mar 2014 18:54:16 GMT
https://trac.sagemath.org/ticket/13917#comment:30
https://trac.sagemath.org/ticket/13917#comment:30
<p>
Wouhouuuuuu !! :-)
</p>
<p>
Nathann
</p>
TicketvbraunFri, 21 Mar 2014 01:40:55 GMT
https://trac.sagemath.org/ticket/13917#comment:31
https://trac.sagemath.org/ticket/13917#comment:31
<p>
Doctest failure
</p>
<pre class="wiki">sage -t --long src/sage/graphs/graph.py
**********************************************************************
File "src/sage/graphs/graph.py", line 4910, in sage.graphs.graph.Graph.cliques_maximal
Failed example:
C.cliques_maximal()
Expected:
[[0, 4], [4, 1, 2, 3]]
Got:
[[0, 4], [1, 2, 3, 4]]
**********************************************************************
</pre>
TicketncohenMon, 24 Mar 2014 09:29:22 GMTcommit, branch changed
https://trac.sagemath.org/ticket/13917#comment:32
https://trac.sagemath.org/ticket/13917#comment:32
<ul>
<li><strong>commit</strong>
changed from <em>09052a0520aa205aaa7af9d0e60c8e1c5574bd1b</em> to <em>635c88da8c6df73b9fdf94d95c0c4fa2fc7397b7</em>
</li>
<li><strong>branch</strong>
changed from <em>u/vdelecroix/13917</em> to <em>public/13917</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=635c88da8c6df73b9fdf94d95c0c4fa2fc7397b7"><span class="icon"></span>635c88d</a></td><td><code>trac #13917: Broken doctest</code>
</td></tr></table>
TicketvbraunTue, 01 Apr 2014 12:12:36 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/13917#comment:33
https://trac.sagemath.org/ticket/13917#comment:33
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/13917</em> to <em>635c88da8c6df73b9fdf94d95c0c4fa2fc7397b7</em>
</li>
</ul>
Ticket