#13242: Determine if an edge in a graph is a cut-edge (bridge)
------------------------------------------------+---------------------------
Reporter: lkeough | Owner: jason,
ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: days40 | Work issues:
Report Upstream: N/A | Reviewers: David Coudert
Authors: Jeremy Martin, Lauren Keough | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------+---------------------------
Comment (by dcoudert):
Apparently you did something wrong when updating the patch. It contains
only parts of the function (last modifications).
Your proposition for directed graphs can be improved because you don't
need to copy the graph. It is sufficient to remove edge (u,v), and to
later restore it. For instance, you can do:
{{{
self.delete_edge(u,v,label)
if self.is_directed():
# (u,v) is a cut edge if u is not in the connected component
# containing v of self-(u,v),
sol = not u in self.connected_component_containing_vertex(v)
else:
# (u,v) is a cut edge if there is no path from u to v in self-(u,v)
sol = not self.distance(u,v) < self.order()
self.add_edge(u,v,label)
return sol
}}}
In fact, the connected_components_number function uses the
connected_component_containing_vertex function. So it is easier that way.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13242#comment:21>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
