16. Articulation point in graph

In [1]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp

In [2]:

g = Graph()

g.insert_node_directed(1, 0)
g.insert_node_directed(0, 2)
g.insert_node_directed(2, 1)
g.insert_node_directed(0, 3)
g.insert_node_directed(3, 4)

g = Graph() g.insert_node_directed(1, 0) g.insert_node_directed(0, 2) g.insert_node_directed(2, 1) g.insert_node_directed(0, 3) g.insert_node_directed(3, 4)

In [3]:

g.graph

g.graph

Out[3]:

defaultdict(list, {1: [0], 0: [2, 3], 2: [1], 3: [4]})

In [4]:

num_vertices = gp.num_vertices_updated(g.graph)
print(num_vertices)

num_vertices = gp.num_vertices_updated(g.graph) print(num_vertices)

5

In [5]:

class articulation_points:
    def __init__(self, graph, num_vertices):
        self.graph = graph
        self.num_vertices = num_vertices
        self.visited = [False] * self.num_vertices
        self.disc = [float("inf")] * self.num_vertices
        self.low = [float("inf")] * self.num_vertices
        self.time = 0
        self.parent = [-1] * self.num_vertices
        self.answer = []
        # self.ap = [False]*self.num_vertices

    def articulation_point_util(self, node):
        self.visited[node] = True
        self.disc[node] = self.time
        self.low[node] = self.time
        self.time += 1

        child = 0

        for neighbour in self.graph[node]:

            # if node's parent is the same as the
            # current neighbour, skip iteration
            if self.parent[node] == neighbour:
                continue

            if self.visited[neighbour] == False:
                self.parent[neighbour] = node
                child += 1
                self.articulation_point_util(neighbour)

                # update node's low with it's child's or neighbour's low
                # when going back in recursion
                self.low[node] = min(self.low[node], self.low[neighbour])

                # now check if this node is an articulation point or not
                if self.low[neighbour] >= self.disc[node] and self.parent[node] != -1:
                    self.answer.append(node)
                    # self.ap[node] = True

                # case for root
                # if self.parent[node] == -1 and len(self.graph[node]) > 1:
                if self.parent[node] == -1 and child > 1:
                    self.answer.append(node)
                    # self.ap[node] = True

            # the neighbour has been visited
            # and it is not the parent of the current node
            # then there is a back-edge
            elif self.parent[node] != neighbour:
                # update the low of this node with the low disc time of neighbour
                self.low[node] = min(self.low[node], self.disc[neighbour])

    def articulation_point(self):
        for node in range(self.num_vertices):
            if self.visited[node] == False:
                self.articulation_point_util(node)

class articulation_points: def __init__(self, graph, num_vertices): self.graph = graph self.num_vertices = num_vertices self.visited = [False] * self.num_vertices self.disc = [float("inf")] * self.num_vertices self.low = [float("inf")] * self.num_vertices self.time = 0 self.parent = [-1] * self.num_vertices self.answer = [] # self.ap = [False]*self.num_vertices def articulation_point_util(self, node): self.visited[node] = True self.disc[node] = self.time self.low[node] = self.time self.time += 1 child = 0 for neighbour in self.graph[node]: # if node's parent is the same as the # current neighbour, skip iteration if self.parent[node] == neighbour: continue if self.visited[neighbour] == False: self.parent[neighbour] = node child += 1 self.articulation_point_util(neighbour) # update node's low with it's child's or neighbour's low # when going back in recursion self.low[node] = min(self.low[node], self.low[neighbour]) # now check if this node is an articulation point or not if self.low[neighbour] >= self.disc[node] and self.parent[node] != -1: self.answer.append(node) # self.ap[node] = True # case for root # if self.parent[node] == -1 and len(self.graph[node]) > 1: if self.parent[node] == -1 and child > 1: self.answer.append(node) # self.ap[node] = True # the neighbour has been visited # and it is not the parent of the current node # then there is a back-edge elif self.parent[node] != neighbour: # update the low of this node with the low disc time of neighbour self.low[node] = min(self.low[node], self.disc[neighbour]) def articulation_point(self): for node in range(self.num_vertices): if self.visited[node] == False: self.articulation_point_util(node)

In [6]:

obj = articulation_points(g.graph, num_vertices=num_vertices)

obj = articulation_points(g.graph, num_vertices=num_vertices)

In [7]:

obj.articulation_point()

obj.articulation_point()

In [8]:

obj.answer

obj.answer

Out[8]:

[3, 0]