#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 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
--
Ticket URL: <http://trac.sagemath.org/ticket/16246#comment:18>
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.
