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: sage-6.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 jdickinson)

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 jdickinson

  • Priority changed from major to minor

comment:2 Changed 6 years ago by ncohen

(cc me)

comment:3 Changed 6 years ago by jdickinson

  • Authors changed from jdickinson to Jennet Dickinson
  • Cc ncohen added

comment:4 Changed 6 years ago by jdickinson

  • Description modified (diff)

comment:5 Changed 6 years ago by jdickinson

  • 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 jdickinson

  • Branch set to u/jdickinson/ticket/16246

comment:7 Changed 6 years ago by jdickinson

  • Commit set to ee677a9dfd6b36ed6008bcbef95950132002511b
  • Status changed from new to needs_review

New commits:

ee677a9Add bridges and spanning trees functions for graphs

comment:8 Changed 6 years ago by ncohen

  • 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

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

comment:9 Changed 6 years ago by ncohen

(just updated the code above, there was an useless waste of time)

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 6 years ago by git

  • Commit changed from ee677a9dfd6b36ed6008bcbef95950132002511b to ee9beee106dbc7c650dbd418ca4ec0090c01cc67

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

17a1a97Fixed bug preventing G.strong_orientation() from working on G a multigraph, added a small multigraph to doctests
72ed2dcMerge branch 'u/jdickinson/ticket/16307' of git://trac.sagemath.org/sage into ticket/16246
9bbee16Remove bridges and spanning_trees from generic_graph.py
ff10942Add updated bridges and spanning_trees to graph.py
ee9beeeMinor docstring updates

comment:12 Changed 6 years ago by jdickinson

  • 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 jdickinson

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 lipshitz

  • 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 ncohen

  • 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:

fed01e4Slightly expand docstrings for bridges() and spanning_trees()

comment:16 Changed 6 years ago by ncohen

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

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

comment:17 follow-up: Changed 6 years ago by lipshitz

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 Read-Tarjan 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 Read-Tarjan 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 ncohen

Helloooooooooo !!

About 4: We think the reason that Read-Tarjan 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 Read-Tarjan 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 ncohen

  • 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:

41df4b0trac #16246: Merged with 6.3.beta0
aa6aa93trac #16246: Rewritten all_spanning_trees function
353ac4btrac #16246: Doc improvements

comment:20 Changed 6 years ago by git

  • Commit changed from 353ac4bf109bf08fb6356b247a57aa2e1a5b654f to e9f67fca64c10c5cf61df3f422c4e825e533c32f

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

5a7d479trac #16246: Merged with 6.3.beta1
e9f67fctrac #16246: renaming a variable

comment:21 Changed 6 years ago by jdickinson

  • Status changed from needs_review to positive_review

comment:22 Changed 6 years ago by vbraun

  • Branch changed from u/ncohen/16246 to e9f67fca64c10c5cf61df3f422c4e825e533c32f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.