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