15. Bridges in graph

In [26]:

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 [27]:

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

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

In [28]:

g.graph

g.graph

Out[28]:

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

In [29]:

num_vertices = gp.num_vertices(g.graph)

num_vertices = gp.num_vertices(g.graph)

In [33]:

class bridges:
    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 = []

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

        for neighbour in self.graph[node]:

            # case-1 ignored
            if self.parent[node] == neighbour:
                continue

            if self.visited[neighbour] == False:
                self.parent[neighbour] = node
                self.bridge_util(neighbour)

                # after returning from recursion
                # update the parent
                self.low[node] = min(self.low[node], self.low[neighbour])

                # check for bridge for every edge
                if self.low[neighbour] > self.disc[node]:
                    self.answer.append([node, neighbour])

            # if neighbour is visited and is not equal to
            # back edge is there
            elif self.parent[node] != neighbour:
                # back edge
                self.low[node] = min(self.low[node], self.disc[neighbour])

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

class bridges: 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 = [] def bridge_util(self, node): self.visited[node] = True self.disc[node] = self.time self.low[node] = self.time self.time += 1 for neighbour in self.graph[node]: # case-1 ignored if self.parent[node] == neighbour: continue if self.visited[neighbour] == False: self.parent[neighbour] = node self.bridge_util(neighbour) # after returning from recursion # update the parent self.low[node] = min(self.low[node], self.low[neighbour]) # check for bridge for every edge if self.low[neighbour] > self.disc[node]: self.answer.append([node, neighbour]) # if neighbour is visited and is not equal to # back edge is there elif self.parent[node] != neighbour: # back edge self.low[node] = min(self.low[node], self.disc[neighbour]) def bridge(self): for node in range(self.num_vertices): if self.visited[node] == False: self.bridge_util(node)

In [34]:

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

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

In [35]:

obj.bridge()

obj.bridge()

In [36]:

obj.answer

obj.answer

Out[36]:

[[3, 4], [0, 3]]

In [ ]: