#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):
* cc: dcoudert (added)
* reviewer: => David Coudert
* status: needs_review => needs_work
Comment:
Since this function is working for undirected graphs only, it should not
be in generic_graph.py.
The following function should be way faster and avoids a copy of the
graph.
{{{
def is_edge_cut(self,e):
if not self.has_edge(e):
raise ValueError, 'edge not in graph'
eu = e[0]
ev = e[1]
visited = dict([(u,False) for u in self.vertex_iterator()])
visited[eu] = True
s = set(self.neighbors(eu))
s.remove(ev)
while (len(s) > 0) and not visited[ev]:
w = s.pop()
visited[w] = True
for x in self.neighbor_iterator(w):
if not visited[x]:
s.add(x)
return (not visited[ev]) and (self.degree(ev)>1)
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13242#comment:5>
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.
