#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):
Replying to [comment:7 lkeough]:
> Thanks, I will move this to graph.py if that is the correct place?
Well, you can let it in generic_graph since it has also some interest for
connectivity in digraphs.
> I tried this code for K_3 with a leaf (G =
Graph([[0,1],[0,2],[1,2],[0,3]]) ) and if I ask if the leaf is a cut-edge
it returns False, but it should be True. I haven't been able to figure
out why this isn't working - any ideas? It seems to work with the slower
code.
My fault (last test in the return).
This new version is much better. It allows multiple formats of input,
solves the pending edge problem, cope with multi-edges. It remains to add
examples and tests.
{{{
def is_edge_cut(self, u, v=None, label=None):
"""
Returns True if (u,v) is a cut edge, False otherwise.
INPUT: The following forms are accepted
- G.is_edge_cut( 1, 2 )
- G.is_edge_cut( (1, 2) )
- G.is_edge_cut( 1, 2, 'label' )
- G.is_edge_cut( (1, 2, 'label') )
"""
if label is None:
if v is None:
try:
u, v, label = u
except:
u, v = u
label = None
if not self.has_edge(u,v):
raise ValueError, 'edge not in graph'
# If edge (u,v) is a pending edge, it is also a cut edge
if self.degree(u) == 1 or self.degree(v) == 1:
return True
elif self.allows_multiple_edges():
# If we have two or more edges between u and v, it is not a cut
edge
if len([(uu,vv) for uu,vv,ll in self.edges_incident(u) if uu == v
or vv == v]) > 1:
return False
# We search for a path from u to v not using edge (u,v). If no such
path is
# found, edge (u,v) is a cut edge
visited = dict([(uu,False) for uu in self.vertex_iterator()])
visited[u] = True
s = set(self.neighbors(u))
s.remove(v)
while (len(s) > 0) and not visited[v]:
w = s.pop()
visited[w] = True
for x in self.neighbor_iterator(w):
if not visited[x]:
s.add(x)
return not visited[v]
}}}
Last, I don't know if the function should be named is_edge_cut or
is_cut_edge
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13242#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 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.
