Find bridges in a Undirected Graph using Tarjan's aglo python implementation

bridges.py

from typing import List
from collections import defaultdict
from math import inf
from enum import Enum, auto


class EdgeTypes(Enum):
    CROSS_EDGE = auto()
    BACK_EDGE = auto()
    TREE_EDGE = auto()
    SELF_EDGE = auto()


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

        self.discovery = defaultdict(lambda: inf)
        self.low = dict()

        self.in_stack = defaultdict(lambda: False)

        self.timer = -1
        self.bridges = list()

    def make_graph(self, _edges) -> None:
        # Assuming undirected graph
        for u, v in _edges:
            self.graph[u].append(v)
            self.graph[v].append(u)

    def get_edge_type(self, edge) -> EdgeTypes:
        u, v = edge

        if u == v:
            return EdgeTypes.SELF_EDGE
        elif self.discovery[v] == inf:
            return EdgeTypes.TREE_EDGE
        elif self.in_stack[v] is True:
            return EdgeTypes.BACK_EDGE
        else:
            return EdgeTypes.CROSS_EDGE

    def dfs(self, u, parent) -> int:
        self.in_stack[u] = True
        self.timer += 1

        self.discovery[u] = self.timer
        low_candidates = [self.discovery[u]]

        for v in self.graph[u]:
            if v == parent:
                continue

            edge_type = self.get_edge_type((u, v))

            if edge_type == EdgeTypes.CROSS_EDGE or edge_type == EdgeTypes.SELF_EDGE:
                continue

            if edge_type == EdgeTypes.TREE_EDGE:
                neighbour_low = self.dfs(v, u)
                low_candidates.append(neighbour_low)

                # Since we ignore the edge to parent so neighbour_low == discovery of u would mean back edge
                if neighbour_low > self.discovery[u]:
                    self.bridges.append([u, v])

            if edge_type == EdgeTypes.BACK_EDGE:
                low_candidates.append(self.discovery[v])

        self.low[u] = min(low_candidates)
        self.in_stack[u] = False
        return self.low[u]

    def get_bridges_in_graph(self) -> List[List[int]]:
        nodes = list(self.graph.keys())

        for node in nodes:
            if self.discovery[node] == inf:
                self.dfs(node, None)

        return self.bridges


if __name__ == '__main__':
    edges = [[0, 1], [1, 2], [2, 0], [1, 3]]
    graph = Graph()
    graph.make_graph(_edges=edges)

    bridges = graph.get_bridges_in_graph()

    for u, v in bridges:
        print(f"Bridge: {u} <-> {v}")