In [42]:

    

class Graph(object):
    def __init__(self, num_vertices):
        self.time = 0
        self.visited = set()
        self.processed = {}
        self.time_entered = {}
        self.time_exited = {}
        self.reachable_ancestor = {}
        self.vertices = range(num_vertices)
        self.parent = {vertex:None for vertex in self.vertices}
        self.edge = {vertex:[] for vertex in self.vertices}
        
    def add_edge(self, v1, v2):
        # for now assume undirected
        self.edge[v1].append(v2)
        self.edge[v2].append(v1)

def findArticulationVertices(G, node):
    G.time += 1
    G.time_entered[node] = G.time    
    G.visited.add(node)
    G.processed[node] = False
    G.reachable_ancestor[node] = node;
    
    for neighbor in G.edge[node]:
        if neighbor not in G.visited:
            G.parent[neighbor] = node
            findArticulationVertices(G, neighbor)
        elif not G.processed[neighbor] and G.parent[neighbor] != node:
            # we've been here before, but haven't finished processing,
            # so this must be a back edge
            if G.time_entered[neighbor] < G.time_entered[G.reachable_ancestor[node]]:
                # if there's a way to get here before the parent's reachable_ancestor,
                # update the parent's reachable_ancestor
                G.reachable_ancestor[node] = neighbor
    
    # process late here
    if G.parent[node] != None:
        if G.reachable_ancestor[node] == G.parent[node] and G.parent[G.parent[node]] != None:
            print "parent articulation vertex", G.parent[node]
        elif G.reachable_ancestor[node] == node:
            print "bridge articulation vertex: ", node, G.parent[node]
        
        if G.time_entered[G.reachable_ancestor[node]] < G.time_entered[G.reachable_ancestor[G.parent[node]]]:
            G.reachable_ancestor[G.parent[node]] = G.reachable_ancestor[node]
            
    G.time += 1
    G.time_exited[node] = G.time
    G.processed[node] = True
    
    
def test1():
    G = Graph(9)
    
    # (0) -(1) -(4)-(5)-(8)
    #  |     |       |   |
    # (2) - (3)     (6)-(7)
    
    G.add_edge(0, 1)
    G.add_edge(0, 2)
    G.add_edge(2, 3)
    G.add_edge(1, 3)
    
    G.add_edge(1, 5)
    
    G.add_edge(5, 8)
    G.add_edge(5, 6)
    G.add_edge(6, 7)
    G.add_edge(7, 8)
    return G

def test2():
    G = Graph(5)
    G.add_edge(1, 0);
    G.add_edge(0, 2);
    G.add_edge(2, 1);
    G.add_edge(0, 3);
    G.add_edge(3, 4);
    return G

def test3():
    G = Graph(4);
    G.add_edge(0, 1);
    G.add_edge(1, 2);
    G.add_edge(2, 3);
    return G 

if __name__ == "__main__":
    G = test3()
    findArticulationVertices(G, 0)


    

    




parent articulation vertex 2
parent articulation vertex 1