#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 lkeough):
Replying to [comment:8 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.
Sounds good, I do believe your code works on digraphs as well.
>
> > 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.
Thanks! I'm new to Sage developing so this might take me a bit, but I'll
work on it today.
> {{{
> 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
I've always referred to this as either cut-edge or bridge (and it seems
Wikipedia does too, for what that is worth).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13242#comment:9>
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.
