Sage: Ticket #17582: Bandwidth of a graph
https://trac.sagemath.org/ticket/17582
<p>
With this branch, one can compute the bandwidth of a graph.
</p>
<p>
If anybody knows another implementation of that for comparisons, I am interested <code>:-P</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17582
Trac 1.1.6ncohenSun, 04 Jan 2015 17:15:12 GMTstatus changed; branch set
https://trac.sagemath.org/ticket/17582#comment:1
https://trac.sagemath.org/ticket/17582#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>public/17582</em>
</li>
</ul>
TicketgitSun, 04 Jan 2015 17:16:17 GMTcommit set
https://trac.sagemath.org/ticket/17582#comment:2
https://trac.sagemath.org/ticket/17582#comment:2
<ul>
<li><strong>commit</strong>
set to <em>df12b0e059f074b7d39c09434d61b8d74a3dd009</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=df12b0e059f074b7d39c09434d61b8d74a3dd009"><span class="icon"></span>df12b0e</a></td><td><code>trac #17582: Bandwidth of a graph</code>
</td></tr></table>
TicketncohenSun, 04 Jan 2015 17:39:08 GMTcc changed
https://trac.sagemath.org/ticket/17582#comment:3
https://trac.sagemath.org/ticket/17582#comment:3
<ul>
<li><strong>cc</strong>
<em>dcoudert</em> added; <em>dcouder</em> removed
</li>
</ul>
TicketdcoudertSun, 04 Jan 2015 18:10:34 GMT
https://trac.sagemath.org/ticket/17582#comment:4
https://trac.sagemath.org/ticket/17582#comment:4
<p>
This is impressive!
I haven't tested yet the patch, but I already have few comments:
</p>
<ul><li>With the instruction <code>G = G.relabel(inplace=False) # int-labelled</code> you loose the original labels of the vertices. You should either store the original label to return an ordering with original names, or write in the doc of the method that the ordering is a permutation of the vertices according the original ordering in the graph, or what is best to write.
</li><li>in the <code>if (d is NULL or distances is NULL or ...</code> you should add a <code>return blah blah</code>.
</li></ul><p>
Now I'm trying to figure out the worse case time complexity of your algorithm, and of course if it is exact ;)
</p>
<p>
More later.
</p>
TicketdcoudertSun, 04 Jan 2015 18:14:13 GMT
https://trac.sagemath.org/ticket/17582#comment:5
https://trac.sagemath.org/ticket/17582#comment:5
<p>
Are you aware of this patch <a class="ext-link" href="http://trac.sagemath.org/ticket/13565"><span class="icon"></span>http://trac.sagemath.org/ticket/13565</a>
</p>
TicketgitMon, 05 Jan 2015 04:06:20 GMTcommit changed
https://trac.sagemath.org/ticket/17582#comment:6
https://trac.sagemath.org/ticket/17582#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>df12b0e059f074b7d39c09434d61b8d74a3dd009</em> to <em>19da4149e16a3a32bd68e354f01e0a50e1af3441</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=19da4149e16a3a32bd68e354f01e0a50e1af3441"><span class="icon"></span>19da414</a></td><td><code>trac #17582: Review</code>
</td></tr></table>
TicketncohenMon, 05 Jan 2015 04:14:05 GMT
https://trac.sagemath.org/ticket/17582#comment:7
https://trac.sagemath.org/ticket/17582#comment:7
<p>
Yo !
</p>
<blockquote class="citation">
<ul><li>With the instruction <code>G = G.relabel(inplace=False) # int-labelled</code> you loose the original labels of the vertices.
</li></ul></blockquote>
<p>
Fixed.
</p>
<blockquote class="citation">
<ul><li>in the <code>if (d is NULL or distances is NULL or ...</code> you should add a <code>return blah blah</code>.
</li></ul></blockquote>
<p>
Fixed.
</p>
<blockquote class="citation">
<p>
Are you aware of patch <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/13565" title="enhancement: Add get_bandwidth to matrix/matrix2.pyx (needs_work)">#13565</a>
</p>
</blockquote>
<p>
Yes I saw it while coding. Actually I wanted to add a "bandwidth" function to the matrix code, just to make my "assert" cleaner at the end of this branch, but I did not know in which of matrix0.pyx, matrix1.pyx or matrix2.pyx it should be stored, and because it was a one-line function I gave that up. By the way, the code at <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/13565" title="enhancement: Add get_bandwidth to matrix/matrix2.pyx (needs_work)">#13565</a> is not very good as it will copy all cells of the matrix (calls to <code>.diagonal()</code>).
</p>
<blockquote class="citation">
<p>
Now I'm trying to figure out the worse case time complexity of your algorithm, and of course if it is exact ;)
</p>
</blockquote>
<p>
Well, at the bottom of it there is only this usual trick of enumerating permutations in a non-recursive way. That parts uses current, i, and left_to_continue. The rest is bandwidth-specific, and is there to cut branches.
</p>
<p>
There may be some doc to add, tell me if it is lacking somewhere. This kind of code is easier to write than to review.
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 05 Jan 2015 22:53:21 GMT
https://trac.sagemath.org/ticket/17582#comment:8
https://trac.sagemath.org/ticket/17582#comment:8
<p>
Some small issues with your code:
</p>
<p>
Empty graph:
</p>
<pre class="wiki">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
</pre><p>
Non connected graph with 2 vertices (the same holds with any non-connected graph):
</p>
<pre class="wiki">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'
</pre><p>
Graph with a single vertex:
</p>
<pre class="wiki">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.
</pre><p>
Also could you add something to let us kill (CRTL+C) computations since it can be very long...
</p>
TicketgitTue, 06 Jan 2015 04:00:14 GMTcommit changed
https://trac.sagemath.org/ticket/17582#comment:9
https://trac.sagemath.org/ticket/17582#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>19da4149e16a3a32bd68e354f01e0a50e1af3441</em> to <em>97f59dc2046e358f9380310883d78cb97e0f78d9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9bc2853c9e56788fa4831dc6dd3198adb1a050a8"><span class="icon"></span>9bc2853</a></td><td><code>trac #17582: Merged with 6.5.beta5</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=97f59dc2046e358f9380310883d78cb97e0f78d9"><span class="icon"></span>97f59dc</a></td><td><code>trac #17582: Review</code>
</td></tr></table>
TicketncohenTue, 06 Jan 2015 04:02:17 GMT
https://trac.sagemath.org/ticket/17582#comment:10
https://trac.sagemath.org/ticket/17582#comment:10
<p>
Yop !
</p>
<blockquote class="citation">
<p>
Empty graph:
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
Non connected graph with 2 vertices (the same holds with any non-connected graph):
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
Graph with a single vertex:
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
Also could you add something to let us kill (CRTL+C) computations since it can be very long...
</p>
</blockquote>
<p>
Done.
</p>
<p>
Nathann
</p>
TicketdcoudertSat, 10 Jan 2015 08:51:06 GMT
https://trac.sagemath.org/ticket/17582#comment:11
https://trac.sagemath.org/ticket/17582#comment:11
<p>
The <code>bandwidth_C</code> method is quite hard to understand. Could you add some more intuition on its principle? It could be useful also for you if you want to modify it in the future and don't remember exactly what you did ;)
</p>
<p>
In this command:
<code>pi = (n-1-i//2) if (i%2) else (i//2) # 0, n-1,1,n-2,2,n-3,3, ... that's an ugly 'if'</code>
Shouldn't you use <code>((n-1-i)//2)</code> ?
</p>
TicketgitSat, 10 Jan 2015 10:23:39 GMTcommit changed
https://trac.sagemath.org/ticket/17582#comment:12
https://trac.sagemath.org/ticket/17582#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>97f59dc2046e358f9380310883d78cb97e0f78d9</em> to <em>49eac6fa5956bd46be27182b5eae887d9632e450</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=49eac6fa5956bd46be27182b5eae887d9632e450"><span class="icon"></span>49eac6f</a></td><td><code>trac #17582: More comments</code>
</td></tr></table>
TicketncohenSat, 10 Jan 2015 10:31:54 GMT
https://trac.sagemath.org/ticket/17582#comment:13
https://trac.sagemath.org/ticket/17582#comment:13
<p>
Hello !
</p>
<blockquote class="citation">
<p>
The <code>bandwidth_C</code> method is quite hard to understand. Could you add some more intuition on its principle?
</p>
</blockquote>
<p>
I added some technical comments in the code, but I do not know how to provide more 'intuition'. Have you looked at the module's documentation ? Did you find it clear, or is there something that I did not explain sufficiently ?
</p>
<blockquote class="citation">
<p>
It could be useful also for you if you want to modify it in the future and don't remember exactly what you did ;)
</p>
</blockquote>
<p>
Don't worry about that. I rewrite the same piece of code, over and over, in different patches to never forget it. You will find it at the bottom of <a class="closed ticket" href="https://trac.sagemath.org/ticket/17309" title="enhancement: SubHypergraphSearch (closed: fixed)">#17309</a>, or in the <code>SubgraphSearch</code> routine. And probably in others too, but I forgot where <code>^^;</code>
</p>
<blockquote class="citation">
<p>
In this command:
<code>pi = (n-1-i//2) if (i%2) else (i//2) # 0, n-1,1,n-2,2,n-3,3, ... that's an ugly 'if'</code>
Shouldn't you use <code>((n-1-i)//2)</code> ?
</p>
</blockquote>
<p>
No, I think that it is correct. As i<n we would have that (n-1-i)<em>2<n/2 and also that i</em>2<n/2, so that pi<n/2 in general. And pi should be a permutation: 0, n-1,1,n-1,2, ...
</p>
<p>
Tell me if it is easier to understand with the new code comments.
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 11 Jan 2015 09:36:02 GMTreviewer set
https://trac.sagemath.org/ticket/17582#comment:14
https://trac.sagemath.org/ticket/17582#comment:14
<ul>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
This is much better now. I have some more comments:
</p>
<ul><li>This method is for undirected and unweighted graphs. You could mention it somewhere and either test input at the beginning of the method, or by default consider the underlying undirected graph
</li><li>Why are you always returning the adjacency matrix? this could be an optional parameter. In fact, you could have a small method that given a graph and an ordering returns the adjacency matrix to avoid code duplication. Such method could be useful for graphs in general.
</li><li>You never use types <code>uint16_t</code> and <code>uint64_t</code>
</li></ul><p>
Otherwise, the method works very well, passes all tests, and the html doc looks good to me.
</p>
TicketncohenSun, 11 Jan 2015 10:09:10 GMT
https://trac.sagemath.org/ticket/17582#comment:15
https://trac.sagemath.org/ticket/17582#comment:15
<p>
Yo !
</p>
<blockquote class="citation">
<ul><li>This method is for undirected and unweighted graphs. You could mention it somewhere and either test input at the beginning of the method, or by default consider the underlying undirected graph
</li></ul></blockquote>
<p>
I added tests and exceptions, as well as changed the document's title.
</p>
<blockquote class="citation">
<ul><li>Why are you always returning the adjacency matrix? this could be an optional parameter. In fact, you could have a small method that given a graph and an ordering returns the adjacency matrix to avoid code duplication. Such method could be useful for graphs in general.
</li></ul></blockquote>
<p>
I added a 'vertices' argument to <code>adjacency_matrix</code>.
</p>
<blockquote class="citation">
<ul><li>You never use types <code>uint16_t</code> and <code>uint64_t</code>
</li></ul></blockquote>
<p>
I made <code>index_t</code> be equal to <code>uint16_t</code> (no problem unless you want the bandwidth of a graph with n>65536) and removed the other imports.
</p>
<p>
Nathann
</p>
TicketgitSun, 11 Jan 2015 10:09:38 GMTcommit changed
https://trac.sagemath.org/ticket/17582#comment:16
https://trac.sagemath.org/ticket/17582#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>49eac6fa5956bd46be27182b5eae887d9632e450</em> to <em>627f6391b361cbe0d3ea397b543df48606b6b771</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=627f6391b361cbe0d3ea397b543df48606b6b771"><span class="icon"></span>627f639</a></td><td><code>trac #17582: Review</code>
</td></tr></table>
TicketdcoudertSun, 11 Jan 2015 10:21:34 GMTstatus changed
https://trac.sagemath.org/ticket/17582#comment:17
https://trac.sagemath.org/ticket/17582#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Excellent. For me the patch is good to go, so I set positive review.
</p>
TicketncohenSun, 11 Jan 2015 10:22:34 GMT
https://trac.sagemath.org/ticket/17582#comment:18
https://trac.sagemath.org/ticket/17582#comment:18
<p>
Thanks !
</p>
<p>
Nathann
</p>
TicketvbraunMon, 12 Jan 2015 18:11:29 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17582#comment:19
https://trac.sagemath.org/ticket/17582#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/17582</em> to <em>627f6391b361cbe0d3ea397b543df48606b6b771</em>
</li>
</ul>
Ticket