Opened 6 years ago
Closed 6 years ago
#16246 closed enhancement (fixed)
Add functions calculating all spanning trees, all bridges in a graph
Reported by:  jdickinson  Owned by:  

Priority:  minor  Milestone:  sage6.3 
Component:  graph theory  Keywords:  bridge, spanning tree 
Cc:  lipshitz, ncohen  Merged in:  
Authors:  Jennet Dickinson  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  e9f67fc (Commits)  Commit:  e9f67fca64c10c5cf61df3f422c4e825e533c32f 
Dependencies:  #16307  Stopgaps: 
Description (last modified by )
This patch adds
1) a function that finds all spanning trees in a graph. (adapted from "Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees" R. C. Read and R. E. Tarjan, 1975)
2) a function that finds all bridges in a graph recursively, that is used in calculating the spanning trees (adapted from the solution to 4.1.36 in Sedgewick's _Algorithms_ 4th ed.)
For example:
sage: G = Graph([(1,2),(1,2),(1,3),(1,3),(2,3),(1,4)]) sage: G.spanning_trees() [Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices, Graph on 4 vertices] sage: len(G.spanning_trees()) == G.spanning_trees_count() True sage: G.bridges() [(1, 4, None)]
These functions will assist in the calculation of the Jones polynomial of a knot.
Change History (22)
comment:1 Changed 6 years ago by
 Priority changed from major to minor
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Cc ncohen added
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
 Created changed from 04/26/14 21:48:37 to 04/26/14 21:48:37
 Description modified (diff)
 Modified changed from 04/27/14 12:46:36 to 04/27/14 12:46:36
comment:6 Changed 6 years ago by
 Branch set to u/jdickinson/ticket/16246
comment:7 Changed 6 years ago by
 Commit set to ee677a9dfd6b36ed6008bcbef95950132002511b
 Status changed from new to needs_review
New commits:
ee677a9  Add bridges and spanning trees functions for graphs

comment:8 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello !
1) Please work on the documentation of your function. You can compare it to the other graph functions and see that they are not quite up to the standard.
2) Please define your auxiliary functions INSIDE of the functions you define, and not inside of the Graph/DiGraph class
3) The file generic_graph.py applies to both graphs and digraphs. Is your code meant to handle digraphs ?
4) I can write bridges
with the following 5 lines
def bridges(g): r""" EXAMPLES:: sage: g = 2*graphs.PetersenGraph() sage: g.add_edge(1,10) sage: g.is_connected() True sage: bridges(g) [(1, 10, None)] """ gs = g.strong_orientation() bridges = [] for scc in gs.strongly_connected_components(): bridges.extend(gs.edge_boundary(scc)) return bridges
please provide comparisons of speed with your implementation.
5) Please think hard of what the following line from your code does
[x for x in self.edges() if x not in self.bridges()])
Nathann
comment:9 Changed 6 years ago by
(just updated the code above, there was an useless waste of time)
comment:10 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:11 Changed 6 years ago by
 Commit changed from ee677a9dfd6b36ed6008bcbef95950132002511b to ee9beee106dbc7c650dbd418ca4ec0090c01cc67
Branch pushed to git repo; I updated commit sha1. New commits:
17a1a97  Fixed bug preventing G.strong_orientation() from working on G a multigraph, added a small multigraph to doctests

72ed2dc  Merge branch 'u/jdickinson/ticket/16307' of git://trac.sagemath.org/sage into ticket/16246

9bbee16  Remove bridges and spanning_trees from generic_graph.py

ff10942  Add updated bridges and spanning_trees to graph.py

ee9beee  Minor docstring updates

comment:12 Changed 6 years ago by
 Dependencies set to #16307
 Modified changed from 05/09/14 23:45:57 to 05/09/14 23:45:57
comment:13 Changed 6 years ago by
Hello! Thanks for the feedback. We have been working on addressing your suggestions
1) Improved documentation coming soon
2) Auxiliary functions have been moved inside the functions we define
3) Our code isn't meant to handle digraphs – have moved everything from generic_graph.py to graph.py
4) Have replaced our bridges code with yours – it runs faster and avoids the problem of hitting a max recursion depth
5) Updated spanning_trees no longer includes this line
Jennet
comment:14 Changed 6 years ago by
 Branch changed from u/jdickinson/ticket/16246 to u/lipshitz/ticket/16246
 Modified changed from 05/09/14 23:48:36 to 05/09/14 23:48:36
comment:15 Changed 6 years ago by
 Commit changed from ee9beee106dbc7c650dbd418ca4ec0090c01cc67 to fed01e4c6927ed713a852f85797166e9cd6ecfdf
Right ! Please set the ticket's status back to needs_review
once it is ready again !
Nathann
New commits:
fed01e4  Slightly expand docstrings for bridges() and spanning_trees()

comment:16 Changed 6 years ago by
Hellooooooooooo again !
I spent some time over your code, and did some modifications to it. They all appear in u/ncohen/16246 for you to look at them.
Some remarks which are fixed there :
1) We try to keep the first line of a function's doc short. Less than a line describing the behaviour, and nothing else. Then you can be as verbose as you want.
2) This :
len(G.edges()) == len(part_G.edges())
Builds the list of edges just to compute its length. Use G.size()
.
3) This
 X = G.edges()  for y in part_G.edges():  X.remove(y)
results in part_G.size()
linear searches in a list X. When you want to test if a pair of things belongs to a set of pairs of things, the data structure you need is a graph. Besides, you only need ONE element of X, so don't compute them all.
4) Call to .bridges
in the recursive function : I don't think this is very effective. Computing all bridges is costly, and if you apply your function to a complete graph it will always be useless. Besides, the first thing you do in a recursive call (right after you removed an edge) is to test whether the graph is connected. Sooo you could use this to detect bridges instead, and wouldn't lose much.
5) Function _edges_to_remove
: when the call to bridges
is removed, you only add edges one by one. And when you only add one edge to part_G
it is easier to detect which edges should be removed. Thus this function can be removed
6) A "SEEALSO" section in the doc is cool. Tells you what you may be interested in finding. I added one in spanning_trees
and another in spanning_trees_count
.
7) No need to repeat "in the graph" when you describe what a function does.
Consequently :
Before
sage: g = Graph(':I`KGgaF?SaP_UGa^') # A random graph sage: %timeit g.spanning_trees() 1 loops, best of 3: 2.21 s per loop
After
sage: g = Graph(':I`KGgaF?SaP_UGa^') sage: %timeit g.spanning_trees() 1 loops, best of 3: 975 ms per loop
The branch containing my commits is now at u/ncohen/16246. If you agree with it, you can :
1) Change this ticket's branch to u/ncohen/16246; or
2) Append my commits to your branch
and then set this ticket to positive_review
. If you don't, let's discuss it as usual :)
Btw : I wanted to rename part_G
to forest
. What do you think ? It's not important or anything, but part_G
does not make much sense to me ...
Nathann
comment:17 followup: ↓ 18 Changed 6 years ago by
Hi Nathann,
Thanks for all of the feedback and improvements! We read your revised code, and agree with everyone you said except perhaps point 4.
About 4: We think the reason that ReadTarjan included this step in their algorithm is the opposite extreme: the case that G is a tree, or almost a tree. According to their analysis, their algorithm runs in O(V+E+ET), where T is the number of spanning trees. (This assumes, of course, that bridges() and so on are implemented efficiently, and that the graphs are stored in a particular way. We think the first half is true for the Sage code, but don't know about the second.)
With your modification, suppose G is a tree. Then it seems the running time is E * O(is_connected()). We don't know how is_connected is implemented. A naive implementation runs in O(V+E) time. Perhaps this can be improved to something like O(V) time.
Upshot: deleting the bridges() stuff adds a quadratic E*V in the algorithm, which can be worse than V+E+ET, in cases that T is small.
In practice, though, you're probably right: probably it's (always? almost always?) faster the way you rewrote the function.
How do you prefer to proceed? The simpler, probably practically faster version you wrote? The possibly theoretically faster ReadTarjan one? An option in the function, allowing the user to decide (defaulting to your version, say)?
Also, feel free to change "part_G" to "forest" if you prefer. ("part_G" stood for "part of the original graph G" or "partial spanning tree".)
Best, Robert and Jennet
comment:18 in reply to: ↑ 17 Changed 6 years ago by
Helloooooooooo !!
About 4: We think the reason that ReadTarjan included this step in their algorithm is the opposite extreme: the case that G is a tree, or almost a tree. According to their analysis, their algorithm runs in O(V+E+ET), where T is the number of spanning trees. (This assumes, of course, that bridges() and so on are implemented efficiently, and that the graphs are stored in a particular way. We think the first half is true for the Sage code, but don't know about the second.)
With your modification, suppose G is a tree. Then it seems the running time is E * O(is_connected()). We don't know how is_connected is implemented. A naive implementation runs in O(V+E) time. Perhaps this can be improved to something like O(V) time.
Hmmmmm... Well, can I shamelessly avoid answering the real question by saying that if the graph is a tree then E=O(V), in which case the asymptotic analysis of the complexity is cool ?
In practice, though, you're probably right: probably it's (always? almost always?) faster the way you rewrote the function.
I believe that removing it really saves something when you have a lot of edges. But I can't prove it with paper and pen.
How do you prefer to proceed? The simpler, probably practically faster version you wrote? The possibly theoretically faster ReadTarjan one? An option in the function, allowing the user to decide (defaulting to your version, say)?
Oh. Well, I prefer the simple and faster version of course. I even prefer "simple" versions when it is just sligthly slower. Really, when it comes to programming you cannot put a lot of faith in complexity analysis. You have to profile code, there is no other way. It is possible that most of the time is taken by something you would not have thought about, something that theory discards as straightforward, which actually isn't. Or just isn't implemented as theory thinks that it should.
Also, feel free to change "part_G" to "forest" if you prefer. ("part_G" stood for "part of the original graph G" or "partial spanning tree".)
I will do this in a second.
Nathann
comment:19 Changed 6 years ago by
 Branch changed from u/lipshitz/ticket/16246 to u/ncohen/16246
 Commit changed from fed01e4c6927ed713a852f85797166e9cd6ecfdf to 353ac4bf109bf08fb6356b247a57aa2e1a5b654f
 Reviewers set to Nathann Cohen
 Status changed from needs_work to needs_review
If you agree with the code, you can set the ticket to needs_review
. The "procedure" is : I reviewed your changes, you reviewed mine, so it is good to go.
Nathann
New commits:
41df4b0  trac #16246: Merged with 6.3.beta0

aa6aa93  trac #16246: Rewritten all_spanning_trees function

353ac4b  trac #16246: Doc improvements

comment:20 Changed 6 years ago by
 Commit changed from 353ac4bf109bf08fb6356b247a57aa2e1a5b654f to e9f67fca64c10c5cf61df3f422c4e825e533c32f
comment:21 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:22 Changed 6 years ago by
 Branch changed from u/ncohen/16246 to e9f67fca64c10c5cf61df3f422c4e825e533c32f
 Resolution set to fixed
 Status changed from positive_review to closed
(cc me)