#11994: Vertex separation and pathwidth in Sage
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Coudert | Author: Nathann Cohen
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
* reviewer: => David Coudert
Comment:
Very nice patch Nathann !
I have some comments / improvements propositions that could be discussed
1) You should first use a mapping function from vertex labels to integer,
and do the reverse mapping at the end. This is to solve the following
problem:
{{{
sage: D=digraphs.DeBruijn(2,3)
sage: D.edges()
[('000', '000', '0'), ('000', '001', '1'), ('001', '010', '0'), ('001',
'011', '1'), ('010', '100', '0'), ('010', '101', '1'), ('011', '110',
'0'), ('011', '111', '1'), ('100', '000', '0'), ('100', '001', '1'),
('101', '010', '0'), ('101', '011', '1'), ('110', '100', '0'), ('110',
'101', '1'), ('111', '110', '0'), ('111', '111', '1')]
sage: vs.vertex_separation(D)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<ipython console> in
<module>()
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-
packages/sage/graphs/graph_decompositions/vertex_separation.so in
sage.graphs.graph_decompositions.vertex_separation.vertex_separation
(sage/graphs/graph_decompositions/vertex_separation.c:1603)()
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-
packages/sage/graphs/graph_decompositions/vertex_separation.so in
sage.graphs.graph_decompositions.vertex_separation.FastDigraph.__cinit__
(sage/graphs/graph_decompositions/vertex_separation.c:687)()
TypeError: an integer is required
sage:
}}}
2) The MemoryError message is not displayed. Your code is:
{{{
raise MemoryError("Memory allocation failed. Is there enough memory around
?")
}}}
and I see
{{{
sage: D=digraphs.RandomDirectedGNP(31,.3)
sage: %time vs.vertex_separation(D)
python(26950) malloc: *** mmap(size=18446744071562067968) failed (error
code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
---------------------------------------------------------------------------
MemoryError Traceback (most recent call
last)
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<ipython console> in
<module>()
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-
packages/IPython/iplib.pyc in ipmagic(self, arg_s)
1180 else:
1181 magic_args = self.var_expand(magic_args,1)
-> 1182 return fn(magic_args)
1183
1184 def ipalias(self,arg_s):
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-
packages/IPython/Magic.pyc in magic_time(self, parameter_s)
1979 if mode=='eval':
1980 st = clk()
-> 1981 out = eval(code,glob)
1982 end = clk()
1983 else:
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<timed eval> in
<module>()
/Applications/Sage-4.7.2-OSX-
64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-
packages/sage/graphs/graph_decompositions/vertex_separation.so in
sage.graphs.graph_decompositions.vertex_separation.vertex_separation
(sage/graphs/graph_decompositions/vertex_separation.c:1680)()
MemoryError:
sage:
}}}
3) small typos in the doc
wll -> will
{{{
88 there. This way, a large number of sets wll never be evaluated and
*a lot* of
}}}
min -> \min
{{{
96 it by `\max (c'(S), \min_{\text{next}})` (where
`min_{\text{next}}` is the
}}}
should translate in english ;-)
{{{
320 print "Reservation de la memoire"
}}}
4) You could rename your function for instance vertex_separation_32, and
then add a frontend function called vertex_separation calling
vertex_separation_32. The goal is to have a more generic function allowing
to add other implementations / methods for the vertex separation...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11994#comment:12>
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.
