Determine if an edge in a graph is a cut-edge (bridge)

[sagetrac-lkeough]

is_cut_edge is needed to compute the Tutte polynomial (#1314)

APPLY:

• attachment: 13242_cutedge.patch

CC: @sagetrac-jeremy-l-martin @nathanncohen @dcoudert

Component: graph theory

Keywords: days40

Author: Jeremy Martin, Lauren Keough

Reviewer: David Coudert

Merged: sage-5.3.beta1

Issue created by migration from https://trac.sagemath.org/ticket/13242

[sagetrac-lkeough]

comment:1

I looked for cut-edge/bridge/isthmus in Sage and in trac tickets, but didn't find anything. Let me know if you see anything though!

[sagetrac-lkeough]

comment:2

Apply only trac_13242.patch

[dcoudert]

comment:5

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)

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:6

Above code should be improved to cope with multiple edges.

[sagetrac-lkeough]

comment:7

Thanks, I will move this to graph.py if that is the correct place?

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.

[dcoudert]

comment:8

Replying to @sagetrac-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

[sagetrac-lkeough]

comment:9

Replying to @dcoudert:

Replying to @sagetrac-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).

[sagetrac-jeremy-l-martin]

comment:11

I believe it should be called is_cut_edge, as "edge cut" means a set of edges whose deletion disconnects the graph.

[dcoudert]

comment:12

Install OK, long tests OK, functionality OK.

However I'm unable to test docbuild (working remote today), and I saw a small alignment problem line 4024.

Also, I'm not sure of the behavior of 'EXAMPLES' versus 'TESTS'. Are examples also considered as tests for 'sage -t'? Is anyone able to answer?

[sagetrac-lkeough]

comment:13

Replying to @dcoudert:

Install OK, long tests OK, functionality OK.

However I'm unable to test docbuild (working remote today), and I saw a small alignment problem line 4024.

I tested docbuild and it looks fine. Is your issue at 4024 that """ should be 4 spaces back. I fixed that and uploaded again.

Also, I'm not sure of the behavior of 'EXAMPLES' versus 'TESTS'. Are examples also considered as tests for 'sage -t'? Is anyone able to answer?

I'm at Sage Days 40 and was told that examples are tested, but are different from tests in that they show up if the user asks for documentation.

[dcoudert]

comment:14

For me the patch is now OK so I give positive review.

Enjoy the Sage Days.

[dcoudert]

comment:15

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.

[sagetrac-lkeough]

comment:16

Faster is certainly better so I don't mind. When I replace this and run the tests it fails the very first example - if an edge in K_4 is a cut edge. I messed around in the Sage notebook and it also seems to be a problem there. The algorithm is correct so I'm probably just implementing this wrong. All I did was replace the lines after #We search for a path..

[sagetrac-lkeough]

comment:17

Replying to @sagetrac-lkeough:

Faster is certainly better so I don't mind. When I replace this and run the tests it fails the very first example - if an edge in K_4 is a cut edge. I messed around in the Sage notebook and it also seems to be a problem there. The algorithm is correct so I'm probably just implementing this wrong. All I did was replace the lines after #We search for a path..

I see now..we want return not ans. Because if self.distance(u,v) < self.order() then (u,v) is not a cut-edge.

[sagetrac-lkeough]

comment:18

This no longer works for digraphs. It returns that an edge in a directed cycle is a cut edge because if we remove that edge there is no directed path between those two vertices. There is a connected_components_number function for digraphs, but comparing connected_components_number(G) and connected_components_number(G-e) is probably not the fastest way to make it work for digraphs.

[dcoudert]

comment:19

Another option is:

    self.delete_edge(u,v,label)
    if self.is_directed():
        ans = self.is_connected()
    else:
        ans = self.distance(u,v) < self.order()
    self.add_edge(u,v,label)
    return not ans

the self.is_connected() function would be sufficient, but the distance function is faster for undirected graphs.

Don't forget to explain the behavior for directed graphs in the description of the function.

[sagetrac-lkeough]

comment:20

I need connected_components_number since an edge is a cut-edge if it increases the number of connected components. So you may be trying to figure out if an edge in an already disconnected graph is a cut edge. I used this:

if self.is_directed():
            H = self.copy()
            H.delete_edge(u,v,label)
            sol = self.connected_components_number() == H.connected_components_number()
            return not sol

I ran tests and built the documentation and it looks fine. I'm going to upload a new patch, but I'm willing to change it if this is a terrible algorithm.

[dcoudert]

comment:21

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.

[sagetrac-lkeough]

Use this one.

[sagetrac-lkeough]

comment:22

Attachment: trac_13242.patch.gz

I think I fixed the patch updating problem and used your code for the directed graph.

[dcoudert]

Attachment: trac_13242-rev.patch.gz

[dcoudert]

comment:23

I did some minor edit (removal of useless spaces, alignments, etc.) in the complementary patch trac_13242-rev.patch (you have to apply both files).

If it is OK for you, I will give a positive review to this patch. For me everything is fine (install, tests, docbuild, functionality, etc.).

[sagetrac-lkeough]

comment:25

All these things worked for me as well.

Thanks for all of your help!

[jdemeyer]

comment:27

attachment: trac_13242.patch needs a proper commit message.

[jdemeyer]

comment:28

Attachment: 13242_cutedge.patch.gz

Fixed myself (and put both patches together).

[sagetrac-lkeough]

comment:29

Sorry, had been away from a computer for a few days. Thank you for fixing this!

[jdemeyer]

Merged: sage-5.3.beta1