#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:
------------------------------------------------+---------------------------
Changes (by dcoudert):
* status: positive_review => needs_work
Comment:
Hello,
I had some discussions with Nathann, and he said that the following should
be faster:
{{{
self.delete_edge(u,v,label)
ans = self.distance(u,v) < self.order()
self.add_edge(u,v,label)
return ans
}}}
I tried it on large graphs and it is definitively faster (10x to 100x). It
is in fact the same algorithm behind, but the distance function is in
cython, so it's fast.
Sorry for the extra work, but it would be better to replace the lines from
'''# We search for a path from''' till the end with above code.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13242#comment:15>
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.
