Opened 5 years ago
Closed 5 years ago
#17582 closed enhancement (fixed)
Bandwidth of a graph
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.5 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Nathann Cohen  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  627f639 (Commits)  Commit:  627f6391b361cbe0d3ea397b543df48606b6b771 
Dependencies:  Stopgaps: 
Description
With this branch, one can compute the bandwidth of a graph.
If anybody knows another implementation of that for comparisons, I am interested :P
Nathann
Change History (19)
comment:1 Changed 5 years ago by
 Branch set to public/17582
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit set to df12b0e059f074b7d39c09434d61b8d74a3dd009
comment:3 Changed 5 years ago by
 Cc dcoudert added; dcouder removed
comment:4 followup: ↓ 7 Changed 5 years ago by
This is impressive! I haven't tested yet the patch, but I already have few comments:
 With the instruction
G = G.relabel(inplace=False) # intlabelled
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.  in the
if (d is NULL or distances is NULL or ...
you should add areturn blah blah
.
Now I'm trying to figure out the worse case time complexity of your algorithm, and of course if it is exact ;)
More later.
comment:5 Changed 5 years ago by
Are you aware of this patch http://trac.sagemath.org/ticket/13565
comment:6 Changed 5 years ago by
 Commit changed from df12b0e059f074b7d39c09434d61b8d74a3dd009 to 19da4149e16a3a32bd68e354f01e0a50e1af3441
Branch pushed to git repo; I updated commit sha1. New commits:
19da414  trac #17582: Review

comment:7 in reply to: ↑ 4 Changed 5 years ago by
Yo !
 With the instruction
G = G.relabel(inplace=False) # intlabelled
you loose the original labels of the vertices.
Fixed.
 in the
if (d is NULL or distances is NULL or ...
you should add areturn blah blah
.
Fixed.
Are you aware of patch #13565
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 oneline function I gave that up. By the way, the code at #13565 is not very good as it will copy all cells of the matrix (calls to .diagonal()
).
Now I'm trying to figure out the worse case time complexity of your algorithm, and of course if it is exact ;)
Well, at the bottom of it there is only this usual trick of enumerating permutations in a nonrecursive way. That parts uses current, i, and left_to_continue. The rest is bandwidthspecific, and is there to cut branches.
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.
Nathann
comment:8 followup: ↓ 10 Changed 5 years ago by
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) <ipythoninput3880a511274ca> in <module>() > 1 bandwidth(G) /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_decompositions/bandwidth.so in sage.graphs.graph_decompositions.bandwidth.bandwidth (build/cythonized/sage/graphs/graph_decompositions/bandwidth.c:1585)() /pathtosage/sage/local/lib/python2.7/sitepackages/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)() /pathtosage/sage/local/lib/python2.7/sitepackages/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 nonconnected graph):
sage: G = Graph() sage: G.add_vertices(range(2)) sage: bandwidth(G)  TypeError Traceback (most recent call last) <ipythoninput6880a511274ca> in <module>() > 1 bandwidth(G) /pathtosage/sage/local/lib/python2.7/sitepackages/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)  /pathtosage/sage/local/lib/libcsage.so(print_backtrace+0x3b)[0xb6b4e3e5] /hpathtosage/sage/local/lib/libcsage.so(sigdie+0x1c)[0xb6b4e59f] /pathtosage/sage/local/lib/libcsage.so(sage_signal_handler+0x20f)[0xb6b4dd28] [0xb77e2400] /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/distances_all_pairs.so(+0xd17f)[0xb01bb17f] /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/distances_all_pairs.so(+0xe230)[0xb01bc230] /pathtosage/sage/local/lib/libpython2.7.so.1.0(PyCFunction_Call+0x109)[0xb768aa49] /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_decompositions/bandwidth.so(+0x30fb)[0xafae70fb] /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_decompositions/bandwidth.so(+0x2204)[0xafae6204] /pathtosage/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_decompositions/bandwidth.so(+0x7043)[0xafaeb043] /pathtosage/sage/local/lib/libpython2.7.so.1.0(PyCFunction_Call+0x109)[0xb768aa49] /pathtosage/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x51b1)[0xb76f56e1] /pathtosage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x7c4)[0xb76f6844] ... /pathtosage/sage/local/lib/libpython2.7.so.1.0(PyRun_AnyFileExFlags+0x78)[0xb771e2c8] /pathtosage/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...
comment:9 Changed 5 years ago by
 Commit changed from 19da4149e16a3a32bd68e354f01e0a50e1af3441 to 97f59dc2046e358f9380310883d78cb97e0f78d9
comment:10 in reply to: ↑ 8 Changed 5 years ago by
Yop !
Empty graph:
Done.
Non connected graph with 2 vertices (the same holds with any nonconnected graph):
Done.
Graph with a single vertex:
Done.
Also could you add something to let us kill (CRTL+C) computations since it can be very long...
Done.
Nathann
comment:11 followup: ↓ 13 Changed 5 years ago by
The bandwidth_C
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 ;)
In this command:
pi = (n1i//2) if (i%2) else (i//2) # 0, n1,1,n2,2,n3,3, ... that's an ugly 'if'
Shouldn't you use ((n1i)//2)
?
comment:12 Changed 5 years ago by
 Commit changed from 97f59dc2046e358f9380310883d78cb97e0f78d9 to 49eac6fa5956bd46be27182b5eae887d9632e450
Branch pushed to git repo; I updated commit sha1. New commits:
49eac6f  trac #17582: More comments

comment:13 in reply to: ↑ 11 Changed 5 years ago by
Hello !
The
bandwidth_C
method is quite hard to understand. Could you add some more intuition on its principle?
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 ?
It could be useful also for you if you want to modify it in the future and don't remember exactly what you did ;)
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 #17309, or in the SubgraphSearch
routine. And probably in others too, but I forgot where ^^;
In this command:
pi = (n1i//2) if (i%2) else (i//2) # 0, n1,1,n2,2,n3,3, ... that's an ugly 'if'
Shouldn't you use((n1i)//2)
?
No, I think that it is correct. As i<n we would have that (n1i)2<n/2 and also that i2<n/2, so that pi<n/2 in general. And pi should be a permutation: 0, n1,1,n1,2, ...
Tell me if it is easier to understand with the new code comments.
Nathann
comment:14 followup: ↓ 15 Changed 5 years ago by
 Reviewers set to David Coudert
This is much better now. I have some more comments:
 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
 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.
 You never use types
uint16_t
anduint64_t
Otherwise, the method works very well, passes all tests, and the html doc looks good to me.
comment:15 in reply to: ↑ 14 Changed 5 years ago by
Yo !
 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
I added tests and exceptions, as well as changed the document's title.
 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.
I added a 'vertices' argument to adjacency_matrix
.
 You never use types
uint16_t
anduint64_t
I made index_t
be equal to uint16_t
(no problem unless you want the bandwidth of a graph with n>65536) and removed the other imports.
Nathann
comment:16 Changed 5 years ago by
 Commit changed from 49eac6fa5956bd46be27182b5eae887d9632e450 to 627f6391b361cbe0d3ea397b543df48606b6b771
Branch pushed to git repo; I updated commit sha1. New commits:
627f639  trac #17582: Review

comment:17 Changed 5 years ago by
 Status changed from needs_review to positive_review
Excellent. For me the patch is good to go, so I set positive review.
comment:18 Changed 5 years ago by
Thanks !
Nathann
comment:19 Changed 5 years ago by
 Branch changed from public/17582 to 627f6391b361cbe0d3ea397b543df48606b6b771
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17582: Bandwidth of a graph