#18876: Boost Cuthill-McKee, King Ordering
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Cuthill-McKee | Merged in:
ordering, King ordering, | Reviewers:
bandwidth | Work issues:
Authors: Michele Borassi | Commit:
Report Upstream: N/A | 6a5c9d02abb93f12313b039a61ba0a62b6f88788
Branch: | Stopgaps:
u/borassi/boost_cuthill_mckee__king_ordering|
Dependencies: #18811, #18564, |
#18839 |
-------------------------------------+-------------------------------------
Comment (by dcoudert):
Some issues:
- You should return a tuple instead of a list, so `(6, [9, 5, 8, 4, 6, 0,
7, 3, 1, 2])` instead of `[6, [9, 5, 8, 4, 6, 0, 7, 3, 1, 2]]`.
- I don't know how to do, but it would be nice to see
`bandwidth_heuristics` in the html output of the bandwidth module.
- Not working with trivial graphs
{{{
from sage.graphs.graph_decompositions import bandwidth as BW
sage: BW.bandwidth_heuristics(Graph())
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-10-88d2a8f9e7cb> in <module>()
----> 1 BW.bandwidth_heuristics(Graph())
/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in
sage.graphs.base.boost_graph.bandwidth_heuristics
(/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4970)()
366
367
--> 368 cpdef bandwidth_heuristics(g, algorithm = 'cuthill_mckee'):
369 r"""
370 Uses Boost heuristics to approximate the bandwidth of the
input graph.
/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in
sage.graphs.base.boost_graph.bandwidth_heuristics
(/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4815)()
453 cdef int n = g.num_verts()
454 cdef dict pos = {int_to_vertex[result[i]]:i for i in range(n)}
--> 455 cdef int bandwidth = max([abs(pos[u]-pos[v]) for u,v in
g.edges(labels=False)])
456
457 sig_off()
ValueError: max() arg is an empty sequence
}}}
{{{
sage: BW.bandwidth_heuristics(graphs.PathGraph(1))
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-11-bf860ec1a3e2> in <module>()
----> 1 BW.bandwidth_heuristics(graphs.PathGraph(Integer(1)))
/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in
sage.graphs.base.boost_graph.bandwidth_heuristics
(/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4970)()
366
367
--> 368 cpdef bandwidth_heuristics(g, algorithm = 'cuthill_mckee'):
369 r"""
370 Uses Boost heuristics to approximate the bandwidth of the
input graph.
/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in
sage.graphs.base.boost_graph.bandwidth_heuristics
(/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4815)()
453 cdef int n = g.num_verts()
454 cdef dict pos = {int_to_vertex[result[i]]:i for i in range(n)}
--> 455 cdef int bandwidth = max([abs(pos[u]-pos[v]) for u,v in
g.edges(labels=False)])
456
457 sig_off()
ValueError: max() arg is an empty sequence
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18876#comment:4>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
