#11754: Computation of rank-decompositions in Sage
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Coudert | Author: Nathann Cohen
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Comment(by dcoudert):
I just tried the new version of the patch.
It is now OK for empty graphs
{{{
sage: G = Graph()
sage: G.rank_decomposition()
(0, Graph on 0 vertices)
}}}
I don't know what is the expected result for non-connected graphs. I have
the following result:
{{{
sage: G = graphs.RandomGNM(10,1)
sage: G.connected_components_number()
9
sage: G.rank_decomposition()
(1, Graph on 19 vertices)
}}}
Now, concerning large graphs:
* The exception message for N==32 could be slightly improve. The current
message is "
Exception: The rank decomposition cannot be computed on graphs of more
than 32 vertices.", but is it >32 or >=32 ?
* 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^(n+1) is a *LOT*)."
* N == 30: I have a segfault immediatly, that is for the first 30 vertices
graph I'm trying:
{{{
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
}}}
I tried with other 30 vertices graphs: G = graphs.GridGraph([5,6]), G =
graphs.RandomTree(30), G = graphs.CompleteGraph(30), ... and I have
exactly the same segfault.
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.
Best,
D.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11754#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
