Opened 4 years ago

Closed 4 years ago

#17582 closed enhancement (fixed)

Bandwidth of a graph

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 4 years ago by ncohen

  • Branch set to public/17582
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to df12b0e059f074b7d39c09434d61b8d74a3dd009

Branch pushed to git repo; I updated commit sha1. New commits:

df12b0etrac #17582: Bandwidth of a graph

comment:3 Changed 4 years ago by ncohen

  • Cc dcoudert added; dcouder removed

comment:4 follow-up: Changed 4 years ago by dcoudert

This is impressive! I haven't tested yet the patch, but I already have few comments:

  • With the instruction G = G.relabel(inplace=False) # int-labelled 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 a return 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 4 years ago by dcoudert

Are you aware of this patch http://trac.sagemath.org/ticket/13565

comment:6 Changed 4 years ago by git

  • Commit changed from df12b0e059f074b7d39c09434d61b8d74a3dd009 to 19da4149e16a3a32bd68e354f01e0a50e1af3441

Branch pushed to git repo; I updated commit sha1. New commits:

19da414trac #17582: Review

comment:7 in reply to: ↑ 4 Changed 4 years ago by ncohen

Yo !

  • With the instruction G = G.relabel(inplace=False) # int-labelled you loose the original labels of the vertices.

Fixed.

  • in the if (d is NULL or distances is NULL or ... you should add a return 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 one-line 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 non-recursive way. That parts uses current, i, and left_to_continue. The rest is bandwidth-specific, 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 follow-up: Changed 4 years ago 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...

comment:9 Changed 4 years ago by git

  • Commit changed from 19da4149e16a3a32bd68e354f01e0a50e1af3441 to 97f59dc2046e358f9380310883d78cb97e0f78d9

Branch pushed to git repo; I updated commit sha1. New commits:

9bc2853trac #17582: Merged with 6.5.beta5
97f59dctrac #17582: Review

comment:10 in reply to: ↑ 8 Changed 4 years ago by ncohen

Yop !

Empty graph:

Done.

Non connected graph with 2 vertices (the same holds with any non-connected 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 follow-up: Changed 4 years ago by dcoudert

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 = (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' Shouldn't you use ((n-1-i)//2) ?

comment:12 Changed 4 years ago by git

  • Commit changed from 97f59dc2046e358f9380310883d78cb97e0f78d9 to 49eac6fa5956bd46be27182b5eae887d9632e450

Branch pushed to git repo; I updated commit sha1. New commits:

49eac6ftrac #17582: More comments

comment:13 in reply to: ↑ 11 Changed 4 years ago by ncohen

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 = (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' Shouldn't you use ((n-1-i)//2) ?

No, I think that it is correct. As i<n we would have that (n-1-i)2<n/2 and also that i2<n/2, so that pi<n/2 in general. And pi should be a permutation: 0, n-1,1,n-1,2, ...

Tell me if it is easier to understand with the new code comments.

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:14 follow-up: Changed 4 years ago by dcoudert

  • 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 and uint64_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 4 years ago by ncohen

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 and uint64_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 4 years ago by git

  • Commit changed from 49eac6fa5956bd46be27182b5eae887d9632e450 to 627f6391b361cbe0d3ea397b543df48606b6b771

Branch pushed to git repo; I updated commit sha1. New commits:

627f639trac #17582: Review

comment:17 Changed 4 years ago by dcoudert

  • 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 4 years ago by ncohen

Thanks !

Nathann

comment:19 Changed 4 years ago by vbraun

  • Branch changed from public/17582 to 627f6391b361cbe0d3ea397b543df48606b6b771
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.