#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.2
Component: graph theory | Resolution:
Keywords: bridge, spanning | Merged in:
tree | Reviewers:
Authors: Jennet Dickinson | Work issues:
Report Upstream: N/A | Commit:
Branch: | ee677a9dfd6b36ed6008bcbef95950132002511b
u/jdickinson/ticket/16246 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
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()
non_bridges = []
for non_b in gs.strongly_connected_components():
non_bridges.extend(gs.subgraph(non_b).edges())
return [e for e in gs.edges() if e not in non_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
--
Ticket URL: <http://trac.sagemath.org/ticket/16246#comment:8>
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.
