#17582: Bandwidth of a graph
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 19da4149e16a3a32bd68e354f01e0a50e1af3441
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17582 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Some small issues with your code:
Empty graph:
{{{
sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth
sage: G = Graph()
sage: bandwidth(G)
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-3-880a511274ca> in <module>()
----> 1 bandwidth(G)
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/graph_decompositions/bandwidth.so in
sage.graphs.graph_decompositions.bandwidth.bandwidth
(build/cythonized/sage/graphs/graph_decompositions/bandwidth.c:1585)()
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/distances_all_pairs.so in
sage.graphs.distances_all_pairs.all_pairs_shortest_path_BFS
(build/cythonized/sage/graphs/distances_all_pairs.c:6810)()
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/distances_all_pairs.so in
sage.graphs.distances_all_pairs.bitset_init
(build/cythonized/sage/graphs/distances_all_pairs.c:1668)()
ValueError: bitset capacity must be greater than 0
}}}
Non connected graph with 2 vertices (the same holds with any non-connected
graph):
{{{
sage: G = Graph()
sage: G.add_vertices(range(2))
sage: bandwidth(G)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
<ipython-input-6-880a511274ca> in <module>()
----> 1 bandwidth(G)
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/graph_decompositions/bandwidth.so in
sage.graphs.graph_decompositions.bandwidth.bandwidth
(build/cythonized/sage/graphs/graph_decompositions/bandwidth.c:1724)()
TypeError: unsupported operand type(s) for //: 'int' and 'PlusInfinity'
}}}
Graph with a single vertex:
{{{
sage: G = Graph()
sage: G.add_vertices(range(1))
sage: bandwidth(G)
------------------------------------------------------------------------
/path-to-sage/sage/local/lib/libcsage.so(print_backtrace+0x3b)[0xb6b4e3e5]
/hpath-to-sage/sage/local/lib/libcsage.so(sigdie+0x1c)[0xb6b4e59f]
/path-to-
sage/sage/local/lib/libcsage.so(sage_signal_handler+0x20f)[0xb6b4dd28]
[0xb77e2400]
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/distances_all_pairs.so(+0xd17f)[0xb01bb17f]
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/distances_all_pairs.so(+0xe230)[0xb01bc230]
/path-to-
sage/sage/local/lib/libpython2.7.so.1.0(PyCFunction_Call+0x109)[0xb768aa49]
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/graph_decompositions/bandwidth.so(+0x30fb)[0xafae70fb]
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/graph_decompositions/bandwidth.so(+0x2204)[0xafae6204]
/path-to-sage/sage/local/lib/python2.7/site-
packages/sage/graphs/graph_decompositions/bandwidth.so(+0x7043)[0xafaeb043]
/path-to-
sage/sage/local/lib/libpython2.7.so.1.0(PyCFunction_Call+0x109)[0xb768aa49]
/path-to-
sage/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x51b1)[0xb76f56e1]
/path-to-
sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x7c4)[0xb76f6844]
...
/path-to-
sage/sage/local/lib/libpython2.7.so.1.0(PyRun_AnyFileExFlags+0x78)[0xb771e2c8]
/path-to-
sage/sage/local/lib/libpython2.7.so.1.0(Py_Main+0xd1e)[0xb7733b2e]
python(main+0x27)[0x8048577]
/lib/libc.so.6(__libc_start_main+0xf3)[0x4c50e963]
python[0x804859d]
------------------------------------------------------------------------
Attaching gdb to process id 18476.
}}}
Also could you add something to let us kill (CRTL+C) computations since it
can be very long...
--
Ticket URL: <http://trac.sagemath.org/ticket/17582#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 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.
