#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):
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.
Some simple tests.
{{{
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)
}}}
Testing with 32 nodes => the patch is working for 31 vertices only !
{{{
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.
}}}
The patch contains some test regarding memory requirement
{{{
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*).
}}}
But the test is not always working, perhaps because I'm on a 32 bits
computer...
{{{
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
}}}
I also have a segfault when running on an empty graph. A simple test is
certainly missing.
{{{
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
}}}
Hope it helps fixing the problems.
Best,
David.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11754#comment:6>
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.
