Revision history [back]

We say that a 3-cycle is separating if its removal disconnects the graph. This function determines whether such a cycle exists.

def has_separating_3cycle(G):
    """
   Check if the graph admits a separating 3-cycle.
    """
    for S in Subsets(G.vertices(), 3):
        if G.subgraph(S).is_isomorphic(graphs.CompleteGraph(3)):
            H = G.copy()
            H.delete_vertices(list(S))
            if not H.is_connected():
                return True
    return False

I wrote the following function, but when I tested it on some graphs, it works reasonably well for graphs of around 50 vertices. However, is there a better way to write it for faster performance? I need to process around 25,000 graphs.

We say that a 3-cycle is separating if its removal disconnects the graph. This function determines whether such a cycle exists.

def has_separating_3cycle(G):
    """
   Check if the graph admits a separating 3-cycle.
    """
    for S in Subsets(G.vertices(), 3):
        if G.subgraph(S).is_isomorphic(graphs.CompleteGraph(3)):
            H = G.copy()
            H.delete_vertices(list(S))
            if not H.is_connected():
                return True
    return False

I wrote the following function, but when I tested it on some graphs, it works reasonably well for graphs of around 50 vertices. However, is there a better way to write it for faster performance? I need to process around 25,000 graphs.

We say that a 3-cycle is separating if its removal disconnects the graph. This function determines whether such a cycle exists.

def has_separating_3cycle(G):
    """
   Check if the graph admits a separating 3-cycle.
    """
    for S in Subsets(G.vertices(), 3):
        if G.subgraph(S).is_isomorphic(graphs.CompleteGraph(3)):
            H = G.copy()
            H.delete_vertices(list(S))
            if not H.is_connected():
                return True
    return False

I wrote the following function, but when I tested it on some graphs, it works reasonably well for graphs of around 50 vertices. However, is there a better way to write it for faster performance? I need to process around 25,000 graphs.