Sage: Ticket #11754: Computation of rank-decompositions in Sage
https://trac.sagemath.org/ticket/11754
<p>
Hello everybody !
</p>
<p>
This patch is an interface between Sage and the software RW, written by Philipp Klaus Krause [1]. It is written in C, and freshly licensed under the GPL2. It is a highly enumerative code that uses a lot of memory, but is still so far the best practical way to obtain optimal decompositions.
</p>
<p>
This patch creates the module sage.graphs.graph_decompositions and the rankwidth-related files. As it requires some documentation, some words are added on what a rank-decomposition is and where the code is coming from. Doing that, I also added sage.graphs.modular_decompositions to the documentation.
</p>
<p>
(As I created a module graph_decompositions, it would make sense to move te modular_decomposition there. It thought it best to do it in a distinct patch, this one being large enough already)
</p>
<p>
Oh. By the way, most of the patch actually contains the copy of the files written by Philipp Klaus Krause.
</p>
<p>
Nathann
</p>
<p>
<a class="ext-link" href="http://pholia.tdi.informatik.uni-frankfurt.de/~philipp/software/rw.shtml"><span class="icon"></span>http://pholia.tdi.informatik.uni-frankfurt.de/~philipp/software/rw.shtml</a>
</p>
<p>
APPLY:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/trac_11754.patch" title="Attachment 'trac_11754.patch' in Ticket #11754">trac_11754.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/trac_11754.patch" title="Download"></a> (merged in sage-5.0.beta6)
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/trac_11754_warning.patch" title="Attachment 'trac_11754_warning.patch' in Ticket #11754">trac_11754_warning.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/trac_11754_warning.patch" title="Download"></a> (merged in sage-5.0.beta6)
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/trac_11754-ifndef.patch" title="Attachment 'trac_11754-ifndef.patch' in Ticket #11754">trac_11754-ifndef.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/trac_11754-ifndef.patch" title="Download"></a> (merged in sage-5.0.beta6)
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/trac_11754-ifndef-rev.patch" title="Attachment 'trac_11754-ifndef-rev.patch' in Ticket #11754">trac_11754-ifndef-rev.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/trac_11754-ifndef-rev.patch" title="Download"></a> (merged in sage-5.0.beta6)
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/11754_manifest.patch" title="Attachment '11754_manifest.patch' in Ticket #11754">11754_manifest.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/11754_manifest.patch" title="Download"></a> (<strong>merged in sage-5.0.beta7</strong>)
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11754
Trac 1.1.6ncohenMon, 29 Aug 2011 07:41:43 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:1
https://trac.sagemath.org/ticket/11754#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketdcoudertSun, 01 Jan 2012 21:52:58 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/11754#comment:2
https://trac.sagemath.org/ticket/11754#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
Nathann,
</p>
<p>
I tried to install the patch with sage-4.8.alpha5 and it's not possible anymore.
Could you update the patch ?
</p>
<p>
Best,
D.
</p>
<pre class="wiki">compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone> hg qimport ~/Soft/sage-patchs/trac_11754.patchadding trac_11754.patch to series file
compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone> hg qpush
applying trac_11754.patch
patching file doc/en/reference/graphs.rst
Hunk #1 FAILED at 46
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/graphs.rst.rej
file sage/graphs/graph_decompositions/__init__.py already exists
1 out of 1 hunks FAILED -- saving rejects to file sage/graphs/graph_decompositions/__init__.py.rej
patching file setup.py
Hunk #1 FAILED at 929
1 out of 1 hunks FAILED -- saving rejects to file setup.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_11754.patch
compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone>
</pre>
TicketncohenSun, 01 Jan 2012 22:47:12 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:3
https://trac.sagemath.org/ticket/11754#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I thought it would be much worse ! Just obvious conflicts with the vertex_separation stuff... Patch updated ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 02 Jan 2012 00:33:33 GMT
https://trac.sagemath.org/ticket/11754#comment:4
https://trac.sagemath.org/ticket/11754#comment:4
<p>
I can now install the patch correctly.
It works on my computer for graphs with 20 nodes and seems OK for 25 nodes (I stopped computation since its quite long), but not for graphs with 30 nodes (see error message bellow). I assume I don't have enough memory on my computer, but the error message is not explicit enough.
Is it possible to test if enough memory is available to run the algorithm as you did for vertex separation and pathwidth ?
Thanks,
David.
</p>
<pre class="wiki">sage: G = graphs.RandomGNM(30,200)
sage: x,H = G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:815)()
RuntimeError: Segmentation fault
</pre>
TicketncohenMon, 02 Jan 2012 10:21:43 GMT
https://trac.sagemath.org/ticket/11754#comment:5
https://trac.sagemath.org/ticket/11754#comment:5
<p>
HMmmmmmm.... In the part of the code I wrote the memory allocations are checked, and it would be bad if it came from the original source code. We try not to put our hands in this kind of code, in order to avoid any troubles when the original source codes get updated (we would have to do all our modifications again on the updated version). What we usually do in these cases is report the bug upstream and wait for them to fix it.
</p>
<p>
The thing is that I was not able to reproduce your bug on my computer. It begins to eat a lot of memory but no segfault, so I do not really know how to debug it <code>^^;</code>
</p>
<p>
Are you testing this code on your mac ? I hope it is not one of those integer initializations again <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 02 Jan 2012 10:47:24 GMT
https://trac.sagemath.org/ticket/11754#comment:6
https://trac.sagemath.org/ticket/11754#comment:6
<p>
The test has been done on a standard PC (32 bits) with 4G of RAM and running linux. Nothing special. The error is almost instantaneous.
</p>
<p>
Some simple tests.
</p>
<pre class="wiki">sage: G = graphs.PetersenGraph()
sage: G.rank_decomposition()
(3, Graph on 19 vertices)
sage: G = graphs.RandomGNM(20,200)
sage: G.rank_decomposition()
(1, Graph on 39 vertices)
</pre><p>
Testing with 32 nodes => the patch is working for 31 vertices only !
</p>
<pre class="wiki">sage: G = graphs.RandomGNM(32,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
Exception Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:677)()
Exception: The rank decomposition cannot be computed on graphs of more than 32 vertices.
</pre><p>
The patch contains some test regarding memory requirement
</p>
<pre class="wiki">sage: G = graphs.RandomGNM(29,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
Exception Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:730)()
Exception: There has been a mistake while converting the Sage graph to a C structure. The memory is probably insufficient (2^(n+1) is a *LOT*).
</pre><p>
But the test is not always working, perhaps because I'm on a 32 bits computer...
</p>
<pre class="wiki">
sage: G = graphs.RandomGNM(30,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:815)()
RuntimeError: Segmentation fault
</pre><p>
I also have a segfault when running on an empty graph. A simple test is certainly missing.
</p>
<pre class="wiki">sage: G= Graph()
sage: G.rank_decomposition()
/path-to-sage/sage-4.8.alpha5/local/lib/libcsage.so(print_backtrace+0x3b)[0x4f7967]
/path-to-sage/sage-4.8.alpha5/local/lib/libcsage.so(sigdie+0x17)[0x4f79a7]
...
...
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
local/bin/sage-sage: line 305: 4884 Segmentation fault (core dumped) sage-ipython "$@" -i
</pre><p>
Hope it helps fixing the problems.
</p>
<p>
Best,
</p>
<p>
David.
</p>
TicketncohenSun, 08 Jan 2012 10:27:29 GMT
https://trac.sagemath.org/ticket/11754#comment:7
https://trac.sagemath.org/ticket/11754#comment:7
<p>
Hellooooooo David !!
</p>
<p>
I just updated the patch so that the case n == 0 is checked. This being said, there is nothing I can do with the segfault you meet as I have not been able to reproduce it. I read my code several times and try to pay attention to those memory errors, all the malloc are checked, etc... I am beginning to think the error may be in the original C code and perhaps it is not too hard to spot by adding "printf("Hello\n");" at some different places until we know where the error is coming from.
After this, I can forward the problem to the author and ask for a patch (and I don't expect this to take too much time either).
</p>
<p>
The thing is that I really can not debug this without being able to reproduce the bug. I tried maaaaaaany times t create a random graph and give it a try but it never happened. Did you tell me that the error occurred right when the function was called ? And do you know if it happens "often" ? How many random graphs do you try before it segfaults ?
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 08 Jan 2012 13:00:26 GMT
https://trac.sagemath.org/ticket/11754#comment:8
https://trac.sagemath.org/ticket/11754#comment:8
<p>
I just tried the new version of the patch.
</p>
<p>
It is now OK for empty graphs
</p>
<pre class="wiki">sage: G = Graph()
sage: G.rank_decomposition()
(0, Graph on 0 vertices)
</pre><p>
I don't know what is the expected result for non-connected graphs. I have the following result:
</p>
<pre class="wiki">sage: G = graphs.RandomGNM(10,1)
sage: G.connected_components_number()
9
sage: G.rank_decomposition()
(1, Graph on 19 vertices)
</pre><p>
Now, concerning large graphs:
</p>
<ul><li>The exception message for N==32 could be slightly improve. The current message is "
</li></ul><p>
Exception: The rank decomposition cannot be computed on graphs of more than 32 vertices.", but is it >32 or >=32 ?
</p>
<ul><li>N == 31 AND N == 29: I got the correct message: "Exception: There has been a mistake while converting the Sage graph to a C structure. The memory is probably insufficient (2<sup>(n+1) is a *LOT*)."
</sup></li></ul><ul><li>N == 30: I have a segfault immediatly, that is for the first 30 vertices graph I'm trying:
<pre class="wiki">sage: G = graphs.RandomGNM(30,500)
sage: G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-blop/sage/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:863)()
RuntimeError: Segmentation fault
</pre></li></ul><p>
I tried with other 30 vertices graphs: G = graphs.<a class="missing wiki">GridGraph?</a>([5,6]), G = graphs.<a class="wiki" href="https://trac.sagemath.org/wiki/RandomTree">RandomTree</a>(30), G = graphs.<a class="missing wiki">CompleteGraph?</a>(30), ... and I have exactly the same segfault.
</p>
<p>
The problem comes from the "if sage_graph_to_matrix(G)" in which you use the " int init_rw_dec(uint_fast8_t n) " function that uses the "int init_rw(uint_fast8_t n)" function.
Most probably, the computation exceeds the type capacity and we get a wrong result.
So, to be on the safe side, I suggest to add a test in the sage_graph_to_matrix function to test if memory allocation is possible.
Or, as you have suggested, you can ask for a patch from the original author.
</p>
<p>
Best,
D.
</p>
TicketncohenSun, 08 Jan 2012 19:17:05 GMT
https://trac.sagemath.org/ticket/11754#comment:9
https://trac.sagemath.org/ticket/11754#comment:9
<p>
Helloooooo !!!
</p>
<p>
Patch updated to make the 32 limit clearer <code>:-)</code>
</p>
<p>
About the segfault : the point is that there is nothing I could "check" to return an exception to avoid the segault unless I know where it comes from. The function you mention contains a total of 5 lines which can produce no segfault, and exclusively consist in memory allocations and checking the memory has been allocated
</p>
<pre class="wiki">int init_rw(uint_fast8_t n)
{
num_vertices = n;
adjacency_matrix = malloc(sizeof(subset_t) * n);
slots = malloc(sizeof(uint_fast8_t) * (1ul << n));
cslots = 0;
return((adjacency_matrix && slots) ? 0 : -1);
}
</pre><p>
If anything goes wrong, the function return -1 instead of 0. And this function (which is defined in the original C code) is called as you said, by a "if" that is precisely there to ensure the memory allocation went smoothly. If it did not, it also returns and error and the function above (rank_decomposition) raises the exception. I mean, there is no memory allocation that I could check and that is not checked already <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 08 Jan 2012 22:09:03 GMT
https://trac.sagemath.org/ticket/11754#comment:10
https://trac.sagemath.org/ticket/11754#comment:10
<p>
I added some printf to track the segfault. It occurs in the calculate_level function for ss=1 and i=17. More precisely, the segfault is with the instruction <em>cslots[1 << i] = 0x0;</em>.
</p>
<pre class="wiki">void calculate_level(uint_fast8_t ss)
{
uint_fast8_t i;
subset_size = ss;
if(subset_size == 0)
slots[0] = 0;
else if(subset_size == 1)
for(i = 0; i < num_vertices; i++)
{
printf("ss=%d, i=%d\n",ss,i);
slots[1 << i] = cut_rank(1 << i);
printf("after cut_rank\n");
cslots[1 << i] = 0x0;
printf("after cslots\n");
}
else
{
subset_t i;
const subset_t end = binomial_coefficient(num_vertices, subset_size);
for(i = 0; i < end; i++)
fill_slot(i);
}
}
</pre><p>
This is definitely a memory allocation problem.
</p>
<p>
D.
</p>
TicketncohenMon, 09 Jan 2012 10:35:06 GMT
https://trac.sagemath.org/ticket/11754#comment:11
https://trac.sagemath.org/ticket/11754#comment:11
<p>
Ahah !! i=17 ! Now that's something ! I prefer when it is something around a power of two, it makes more sense <code>:-)</code>
</p>
<p>
Well, for instance I wondered what the result of
</p>
<pre class="wiki">1 << (uint_fast8) 17
</pre><p>
is in C. Is 1 automatically set to type uint_fast8 ? In this case the result is zero. Is it automatically set to integer ? In this case the result is 2<sup>17. Anyway this should not make much of a difference, as accessing cslots[0] is not big deal -- it is the safest of them all to access !
Oddly the allocation part seems totally safe
</sup></p>
<pre class="wiki">cslots = malloc(sizeof(subset_t) * (1ul << n));
</pre><p>
Nathann
</p>
TicketdcoudertTue, 24 Jan 2012 22:31:46 GMT
https://trac.sagemath.org/ticket/11754#comment:12
https://trac.sagemath.org/ticket/11754#comment:12
<p>
I tried with a fresh install of 5.0.beta1 and I still have the problem with 30 :(
</p>
<p>
D.
</p>
TicketncohenWed, 25 Jan 2012 09:40:51 GMT
https://trac.sagemath.org/ticket/11754#comment:13
https://trac.sagemath.org/ticket/11754#comment:13
<p>
Ok... I gave it another try and really have no idea where this could come from. As the only thing I can guess is that the problem actually come from the original source code, what would you think of merging this patch anyway, with a warning in the documentation (also to ask people experiencing the same bug, if any, to give us information on their hardware), and continue to discuss it with the author ?
</p>
<p>
The way we are going now, this patch will just be forgotten even though it can actually solve the problem except on your architecture for some mysterious reason <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketdcoudertWed, 25 Jan 2012 13:37:55 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:14
https://trac.sagemath.org/ticket/11754#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I agree with this proposal, so I give a positive review.
</p>
<p>
Honestly, I think most of us will never try use the algorithm for N=30 due to very huge computation time ;-)
</p>
<ol class="upperalpha" start="4"><li>
</li></ol>
TicketncohenWed, 25 Jan 2012 13:54:07 GMT
https://trac.sagemath.org/ticket/11754#comment:15
https://trac.sagemath.org/ticket/11754#comment:15
<p>
Argggg !!! A bit too fast !! The warning was not in the patch when I said that ! Could you check this other patch too ? It contains the message I mentionned and also fixes a warning when building the documentation.
</p>
<p>
Sorryyyyyyyyyyyyyyyyyy !!
</p>
<p>
Nathann
</p>
TicketncohenWed, 25 Jan 2012 13:54:20 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754_warning.patch</em>
</li>
</ul>
TicketdcoudertWed, 25 Jan 2012 14:18:44 GMT
https://trac.sagemath.org/ticket/11754#comment:16
https://trac.sagemath.org/ticket/11754#comment:16
<p>
I tried the warning patch as well, and the documentation is properly generated with a clear message (pink warning box).
</p>
<p>
I give a positive review.
</p>
<p>
D.
</p>
TicketncohenWed, 25 Jan 2012 14:20:46 GMT
https://trac.sagemath.org/ticket/11754#comment:17
https://trac.sagemath.org/ticket/11754#comment:17
<p>
Thaaaaaaaaaanks ! <code>:-)</code>
</p>
<p>
I'm trying to write some proof in geometry, and I'm having a lot of fun. Hopefully it is not a final one, but just for my new bosses... It's as clear as a cops-and-robbers proof <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenWed, 25 Jan 2012 14:22:03 GMTdescription changed
https://trac.sagemath.org/ticket/11754#comment:18
https://trac.sagemath.org/ticket/11754#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11754?action=diff&version=18">diff</a>)
</li>
</ul>
<p>
Oops. Forgot to add the list of patches that should be applied to the ticket.
</p>
TicketjdemeyerSun, 29 Jan 2012 14:03:38 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:19
https://trac.sagemath.org/ticket/11754#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The commit message of <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11754/trac_11754.patch" title="Attachment 'trac_11754.patch' in Ticket #11754">trac_11754.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11754/trac_11754.patch" title="Download"></a> should be changed.
</p>
TicketncohenSun, 29 Jan 2012 14:33:24 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:20
https://trac.sagemath.org/ticket/11754#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Ooops <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerSun, 29 Jan 2012 16:40:54 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:21
https://trac.sagemath.org/ticket/11754#comment:21
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I get Cython compilation failures:
</p>
<pre class="wiki">In file included from sage/graphs/graph_decompositions/rankwidth/rw.c:22,
from sage/graphs/graph_decompositions/rankwidth.c:236:
sage/graphs/graph_decompositions/rankwidth/rw.h:28: error: redefinition of typedef 'subset_t'
sage/graphs/graph_decompositions/rankwidth/rw.h:28: error: previous declaration of 'subset_t' was here
</pre>
TicketncohenSun, 29 Jan 2012 16:44:38 GMT
https://trac.sagemath.org/ticket/11754#comment:22
https://trac.sagemath.org/ticket/11754#comment:22
<p>
Weird <code>O_o</code>. I've got no problem on my computer. Are you using beta1, or has something important changed since ?
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 29 Jan 2012 19:48:57 GMT
https://trac.sagemath.org/ticket/11754#comment:23
https://trac.sagemath.org/ticket/11754#comment:23
<p>
I tried on several computers, and I have the same compilation error on one of them (namely musclotte).
</p>
<ul><li>Intel(R) Xeon(R) CPU W5580 @ 3.20GHz
</li><li>64bits
</li><li>gcc (GCC) 4.4.3 20100127 (Red Hat 4.4.3-4)
</li><li>Sage Version 4.8, Release Date: 2012-01-20
</li></ul><p>
Let me know if I can help solving the problem.
</p>
<p>
D.
</p>
TicketjdemeyerSun, 29 Jan 2012 23:37:01 GMT
https://trac.sagemath.org/ticket/11754#comment:24
https://trac.sagemath.org/ticket/11754#comment:24
<p>
Probably it depends on the gcc version. My report was with the default gcc on sage.math, which is gcc-4.2.4.
</p>
TicketncohenSun, 29 Jan 2012 23:41:18 GMT
https://trac.sagemath.org/ticket/11754#comment:25
https://trac.sagemath.org/ticket/11754#comment:25
<p>
Hmmmm... Considering the bug, this is probably the problem. Mine is 4.6.2.
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 30 Jan 2012 00:21:13 GMT
https://trac.sagemath.org/ticket/11754#comment:26
https://trac.sagemath.org/ticket/11754#comment:26
<p>
The other computer on which I don't have compilation error is with gcc (GCC) 4.6.1 20110908 (Red Hat 4.6.1-9).
</p>
<p>
Unfortunately, we cannot rely on gcc version to solve the problem.
</p>
<p>
Nathann, may be you can add a test around the definition of type subset_t to avoid redefinition, something like (not sure of the syntax but I know it can be done)
</p>
<pre class="wiki">
#ifndef _GUARD_SUBSET_T_DEFINITION_
typedef uint_least32_t subset_t;
#define _GUARD_SUBSET_T_DEFINITION_
#endif
</pre><p>
D.
</p>
TicketncohenMon, 30 Jan 2012 12:31:40 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:27
https://trac.sagemath.org/ticket/11754#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hellooooooo !!!
</p>
<p>
Could you please try this new patch ? And could you give the 30-vertices segfault another try too ? <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerMon, 30 Jan 2012 13:58:21 GMT
https://trac.sagemath.org/ticket/11754#comment:28
https://trac.sagemath.org/ticket/11754#comment:28
<p>
Considering <code>rw.c</code> is part of Sage, there is no need for the file <code>COPYING</code>.
</p>
TicketncohenMon, 30 Jan 2012 14:31:48 GMT
https://trac.sagemath.org/ticket/11754#comment:29
https://trac.sagemath.org/ticket/11754#comment:29
<p>
Updated !
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 30 Jan 2012 14:50:01 GMT
https://trac.sagemath.org/ticket/11754#comment:30
https://trac.sagemath.org/ticket/11754#comment:30
<p>
Not good with 30-vertices on my 32bits / sage.5.beta1 / gcc 4.6.1 computer
</p>
<pre class="wiki">sage: G = graphs.RandomTree(30)
sage: G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
/path-to-sage/sage-5.0.beta1/devel/sage-myclone/sage/graphs/<ipython console> in <module>()
/path-to-sage/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
2999
3000 from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001 return rank_decomposition(self, verbose = verbose)
3002
3003 ### Matching
/path-to-sage/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:863)()
RuntimeError: Segmentation fault
</pre><p>
and still compilation errors on the other computer
:(
</p>
TicketncohenMon, 30 Jan 2012 15:06:03 GMT
https://trac.sagemath.org/ticket/11754#comment:31
https://trac.sagemath.org/ticket/11754#comment:31
<p>
Hmmm... Is there any way to use musclotte from outside of the INRIA network. It is pretty hard to debug a code that runs on your computer <code>:-p</code>
</p>
<p>
Nathann
</p>
TicketncohenMon, 30 Jan 2012 15:44:19 GMT
https://trac.sagemath.org/ticket/11754#comment:32
https://trac.sagemath.org/ticket/11754#comment:32
<p>
What about this new patch ? After this, I really have no idea of what to try :-p
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 30 Jan 2012 15:55:23 GMT
https://trac.sagemath.org/ticket/11754#comment:33
https://trac.sagemath.org/ticket/11754#comment:33
<p>
no change :(
I will check the code asap.
D.
</p>
TicketdcoudertTue, 31 Jan 2012 19:32:01 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:34
https://trac.sagemath.org/ticket/11754#comment:34
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Good news, I have identified the cause of my segfault !
</p>
<p>
In function <code>init_rw_dec</code>, with N=30, I have <code>sizeof(subset_t) * (1ul << n) == 0</code> !!!
Consequently, the malloc function returns a pointer.
This is a stupid numerical problem.
We have <code>sizeof(subset_t)==4</code> and <code>(1ul<<30)==1073741824</code>. But at least on my computer, it happens that <code>4294967296==0 mod(2^32)</code>...
</p>
<p>
So you should add a test like this just after the malloc:
</p>
<pre class="wiki">if((sizeof(subset_t) * (1ul << n)==0) && (n>0) && cslots) return(-1);
</pre><p>
A similar test in function <code>init_rw</code> could be safer.
</p>
<p>
No news concerning the compilation error.
</p>
<p>
Best,
D.
</p>
TicketdcoudertWed, 01 Feb 2012 12:24:53 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754_fix_compilation_error_and_a_segfault.patch</em>
</li>
</ul>
<p>
complement patch to fix compilation errors and segfaults
</p>
TicketdcoudertWed, 01 Feb 2012 12:28:02 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:35
https://trac.sagemath.org/ticket/11754#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
This complementary patch solves:
</p>
<ul><li>compilation errors discussed in this ticket on some versions of gcc
</li><li>segfault with N=30 discussed in this ticket.
</li></ul><p>
Applying all attached files, I'm satisfied with this patch. What about you ?
</p>
TicketncohenWed, 01 Feb 2012 16:19:03 GMT
https://trac.sagemath.org/ticket/11754#comment:36
https://trac.sagemath.org/ticket/11754#comment:36
<p>
Hellooooooooooooo !!
</p>
<p>
Well... <code>^^;</code>
</p>
<p>
The problem with this is that we usually avoid touching the source code we add to Sage, so that there is no problem when we have to update it... I've been personally yelled at once or twice for doing just that <code>^^;</code>
</p>
<p>
I can forward the first fix to the author, for it is a bug of his own software, as for the second bug....
</p>
<p>
Well, perhaps "just this" could be ok for Sage (Jeroen, are you still reading what's happening here ) ? <code>:-p</code>
</p>
<p>
Nathann
</p>
TicketdcoudertWed, 01 Feb 2012 19:02:25 GMT
https://trac.sagemath.org/ticket/11754#comment:37
https://trac.sagemath.org/ticket/11754#comment:37
<p>
OK, so please ask the author to perform the proposed modification in the rw.c file.
</p>
<p>
Furthermore, tell the author of rw.h to add at the beginning of the file the #ifndef _SOME_FLAG_ followed by #define _SOME_FLAG_ 1, then the content of the actual rw.h file, and to end the file with the #endif command. This is standard way of writing .h files.
</p>
<p>
Best,
</p>
<p>
D.
</p>
TicketncohenThu, 23 Feb 2012 15:45:37 GMTdescription changed
https://trac.sagemath.org/ticket/11754#comment:38
https://trac.sagemath.org/ticket/11754#comment:38
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11754?action=diff&version=38">diff</a>)
</li>
</ul>
<p>
Ok, in the end it's not really fair that Philipp should change his code to make ours work. I just added this "ifndef" preprocessor instruction in the rw.h file, and I guess it will not be the end of the world to remember if we have to update the code at some point (which I'd probably do myself anyway <code>:-p</code>).
</p>
<p>
Please tell me if it works on your computer, and let's roll <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 23 Feb 2012 15:46:30 GMT
https://trac.sagemath.org/ticket/11754#comment:39
https://trac.sagemath.org/ticket/11754#comment:39
<p>
(I also updated the original source code, just in case)
</p>
<p>
Nathann
</p>
TicketncohenThu, 23 Feb 2012 15:46:51 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754.patch</em>
</li>
</ul>
TicketncohenThu, 23 Feb 2012 15:47:02 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754-ifndef.patch</em>
</li>
</ul>
TicketdcoudertFri, 24 Feb 2012 10:38:50 GMTdescription changed
https://trac.sagemath.org/ticket/11754#comment:40
https://trac.sagemath.org/ticket/11754#comment:40
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11754?action=diff&version=40">diff</a>)
</li>
</ul>
<p>
Nathann,
</p>
<p>
I have added a review patch because 1) the test in rw.h was not correct. We have to define a tag. 2) the test in rw.c was also incorrect due to missing braces.
</p>
<p>
Now compilation is correct on both my 32 bits and 64 bits computers. The execution is correct, in particular it returns the correct error message when memory is insufficient. Tests are OK, and documentation was already OK.
</p>
<p>
For me the patch is now good to go.
</p>
<p>
D.
</p>
TicketncohenFri, 24 Feb 2012 11:34:17 GMT
https://trac.sagemath.org/ticket/11754#comment:41
https://trac.sagemath.org/ticket/11754#comment:41
<p>
Hellooooo !!!
</p>
<blockquote class="citation">
<p>
I have added a review patch because 1) the test in rw.h was not correct. We have to define a tag. 2) the test in rw.c was also incorrect due to missing braces.
</p>
</blockquote>
<p>
Hmm... That should be fixed in *his* code. I will email him about it <code>O_o</code>
</p>
<blockquote class="citation">
<p>
Now compilation is correct on both my 32 bits and 64 bits computers. The execution is correct, in particular it returns the correct error message when memory is insufficient. Tests are OK, and documentation was already OK.
</p>
</blockquote>
<p>
One last mail exchange with him, and I'll be glad to see this patch merged ! <code>:-p</code>
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 24 Feb 2012 13:30:30 GMT
https://trac.sagemath.org/ticket/11754#comment:42
https://trac.sagemath.org/ticket/11754#comment:42
<p>
I did some more tests with sage-5.0.beta5
</p>
<ol><li>on a 32 bits computer with 4Go of RAM, gcc (GCC) 4.6.1 20110908 (Red Hat 4.6.1-9) <br />
<ul><li>I tried first to apply only trac_11754.patch + trac_11754_warning.patch + trac_11754-ifndef.patch
</li></ul></li></ol><ul><li>Install OK, tests, OK, functionality OK, but <strong>problem when n = 30</strong>: the execution starts as if mallocs were OK, but I don't have enough memory for 29 so it cannot work for 30
</li><li></li></ul><table class="wiki">
<tr>Now, changing the ugly (unsafe?) test in init_rw from ``if(n > MAX_VERTICES <td> n && !(sizeof(uint_fast8_t) * (1ul << n)))`` to ``if( ( (n > MAX_VERTICES) </td><td style="text-align: left"> (n>0) ) && !(sizeof(uint_fast8_t) * (1ul << n)) )`` solves the problem and I get the correct error message !
</td></tr></table>
<ol><li>on a 64 bits computer with 64Go of RAM, gcc (GCC) 4.4.3 20100127 (Red Hat 4.4.3-4) <br />
<ul><li>I have an installation error when using only trac_11754.patch + trac_11754_warning.patch + trac_11754-ifndef.patch
</li><li>When patching the ifndef test in rw.h, I solve installation problem, and then every thing seems to work. However, I have no way to control execution with N>=29 due to computation time. So I don't know what's happening when N=30 (I have large enough memory, but computation should be huge).
</li></ul></li></ol><p>
Altogether, I need the revision patch (as I already identified weeks ago) to have the patch properly installing and operating.
</p>
<p>
D.
</p>
TicketdcoudertFri, 24 Feb 2012 13:36:42 GMT
https://trac.sagemath.org/ticket/11754#comment:43
https://trac.sagemath.org/ticket/11754#comment:43
<p>
Wysiwyg problem...
</p>
<p>
So change the test from
</p>
<pre class="wiki">if(n > MAX_VERTICES || n && !(sizeof(uint_fast8_t) * (1ul << n)))
</pre><p>
To
</p>
<pre class="wiki">if( ( (n > MAX_VERTICES) || (n>0) ) && !(sizeof(uint_fast8_t) * (1ul << n)) )
</pre><p>
Honestly, which one is the fastest to read ?
</p>
TicketncohenFri, 24 Feb 2012 20:34:33 GMT
https://trac.sagemath.org/ticket/11754#comment:44
https://trac.sagemath.org/ticket/11754#comment:44
<p>
Ok, the author told me he intended the priority to be different (a parenthesis around "n && !(sizeof(uint_fast8_t) * (1ul << n))", but it makes no difference anyway as we settle the case n=0 differently already.
</p>
<p>
On my machine everything runs fine with all 4 patches applied. If everything is fine on your computer too I think this patch can go. As for a possible updates in 50 years, we will still have this track ticket lying around <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 24 Feb 2012 22:00:14 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754-ifndef-rev.patch</em>
</li>
</ul>
TicketdcoudertFri, 24 Feb 2012 22:10:33 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:45
https://trac.sagemath.org/ticket/11754#comment:45
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
The author is right ;-)
</p>
<p>
The previous version was also working for me because the test was true for N> 31, n <0, and N=30, but it was an accident. With the correct version, we have the same result but it is more expected.
</p>
<p>
I have updated the patch accordingly and its working fine on all my computers: compilation, tests, documentation, functionality, error messages.
</p>
<p>
For me it's good to go so I give positive review.
</p>
<p>
D.
</p>
<p>
PS: I hope the ARM guys will not experience similar problems than for vertex separation...
</p>
TicketncohenFri, 24 Feb 2012 22:14:31 GMT
https://trac.sagemath.org/ticket/11754#comment:46
https://trac.sagemath.org/ticket/11754#comment:46
<p>
Well, at least not "the same ones", as the author uses the correct types. And I'll do that too from now on <code>:-)</code>
</p>
<p>
Thank you for the review, by the way ! This is another of the patches that have been waiting for... ages ! <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerMon, 27 Feb 2012 11:21:03 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11754#comment:47
https://trac.sagemath.org/ticket/11754#comment:47
<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>merged</strong>
set to <em>sage-5.0.beta6</em>
</li>
</ul>
TicketjdemeyerThu, 01 Mar 2012 17:20:33 GMTstatus changed; resolution deleted
https://trac.sagemath.org/ticket/11754#comment:48
https://trac.sagemath.org/ticket/11754#comment:48
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>new</em>
</li>
<li><strong>resolution</strong>
<em>fixed</em> deleted
</li>
</ul>
<p>
Re-opening this as there some problems with the <code>MANIFEST.in</code>. The following need to be added:
</p>
<pre class="wiki">! sage/graphs/graph_decompositions/rankwidth/README
! sage/graphs/graph_decompositions/rankwidth/__init__.py
</pre>
TicketncohenSat, 03 Mar 2012 08:30:42 GMTstatus changed
https://trac.sagemath.org/ticket/11754#comment:49
https://trac.sagemath.org/ticket/11754#comment:49
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Helloooo !!!
</p>
<p>
Is this patch what you need ? <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketncohenSat, 03 Mar 2012 08:31:46 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>trac_11754-RM.patch</em>
</li>
</ul>
TicketncohenSat, 03 Mar 2012 08:32:04 GMTdescription changed
https://trac.sagemath.org/ticket/11754#comment:50
https://trac.sagemath.org/ticket/11754#comment:50
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11754?action=diff&version=50">diff</a>)
</li>
</ul>
TicketjdemeyerSun, 04 Mar 2012 20:50:12 GMTattachment set
https://trac.sagemath.org/ticket/11754
https://trac.sagemath.org/ticket/11754
<ul>
<li><strong>attachment</strong>
set to <em>11754_manifest.patch</em>
</li>
</ul>
TicketjdemeyerSun, 04 Mar 2012 20:50:50 GMTstatus, reviewer, description changed
https://trac.sagemath.org/ticket/11754#comment:51
https://trac.sagemath.org/ticket/11754#comment:51
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>David Coudert</em> to <em>David Coudert, Jeroen Demeyer</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11754?action=diff&version=51">diff</a>)
</li>
</ul>
TicketjdemeyerMon, 05 Mar 2012 13:17:25 GMTstatus, description changed; resolution set
https://trac.sagemath.org/ticket/11754#comment:52
https://trac.sagemath.org/ticket/11754#comment:52
<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>description</strong>
modified (<a href="/ticket/11754?action=diff&version=52">diff</a>)
</li>
</ul>
TicketmhansenFri, 16 Mar 2012 17:49:32 GMT
https://trac.sagemath.org/ticket/11754#comment:53
https://trac.sagemath.org/ticket/11754#comment:53
<p>
I think there is an issue with this code as there is a extension module sage.graphs.graph_decompositions.rankwidth as well as a package (with <span class="underline">init</span>.py) sage/graphs/decompositions/rankwidth/ . I think that should really be fixed as it's ambiguous which should be used.
</p>
TicketjdemeyerSat, 17 Mar 2012 12:49:01 GMT
https://trac.sagemath.org/ticket/11754#comment:54
https://trac.sagemath.org/ticket/11754#comment:54
<p>
To be fixed in a follow-up ticket of course.
</p>
TicketmhansenSat, 17 Mar 2012 17:00:21 GMT
https://trac.sagemath.org/ticket/11754#comment:55
https://trac.sagemath.org/ticket/11754#comment:55
<p>
This is now at <a class="closed ticket" href="https://trac.sagemath.org/ticket/12684" title="defect: Rename sage/graphs/graph_decompositions/rankwidth/ (closed: fixed)">#12684</a>.
</p>
Ticket