#16246: Add functions calculating all spanning trees, all bridges in a graph
-------------------------------------+-------------------------------------
Reporter: jdickinson | Owner:
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.3
Component: graph theory | Resolution:
Keywords: bridge, spanning | Merged in:
tree | Reviewers:
Authors: Jennet Dickinson | Work issues:
Report Upstream: N/A | Commit:
Branch: | fed01e4c6927ed713a852f85797166e9cd6ecfdf
u/lipshitz/ticket/16246 | Stopgaps:
Dependencies: #16307 |
-------------------------------------+-------------------------------------
Comment (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
--
Ticket URL: <http://trac.sagemath.org/ticket/16246#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
