Euler Path / Circuit Hierholzer’s Algorithm for directed graph -- Python Implementation

eulers_path.py

# Hierholzer’s Algorithm for directed graph
# Eulers Circuit
# Eulers Path
# Find if a graph has a Euler Path/Circuit -> O(V + E)
# Print the graphs Euler Path/Circuit

# Python Implementation

from collections import defaultdict
from enum import Enum, auto


class PathType(Enum):
    EULERS_CIRCUIT = auto()
    EULERS_PATH = auto()
    NON_EULAIAN = auto()


class Graph:
    def __init__(self):
        self.graph = defaultdict(set)
        self.degree = defaultdict(lambda: 0)
        self.edges = []

    def make_graph(self, edges, is_directed=True) -> None:
        self.edges = edges

        for u, v in self.edges:
            self.degree[u] += 1
            self.degree[v] += 1

            self.graph[u].add(v)

            if is_directed is False:
                self.graph[v].add(u)

    def no_of_odd_degree_nodes(self) -> int:
        return sum(degree for degree in self.degree.values() if degree % 2 != 0)

    def get_type(self) -> PathType:
        # 1. Since we make the graph from edges only,
        # so we are sure that our graph has only 1 component and that is connected.

        # 2. Check how many nodes have non-even degree
        odd_degree_nodes = self.no_of_odd_degree_nodes()
        if odd_degree_nodes == 0:
            return PathType.EULERS_CIRCUIT
        elif odd_degree_nodes == 2:
            return PathType.EULERS_PATH
        else:
            return PathType.NON_EULAIAN

    def get_path(self, path_type: PathType):
        assert self.get_type() == path_type

        path = list()
        visited_edges = {}

        start_node = 0

        # Using backtracking if we choose the wrong node
        def dfs(u):
            nonlocal visited_edges
            nonlocal path

            path.append(u)

            assert len(visited_edges) != len(self.edges)

            for v in self.graph[u]:
                edge = (u, v)
                if edge not in visited_edges:
                    visited_edges[edge] = True
                    dfs(edge[1])

                    # Marking a node unvisited once we backtrack
                    visited_edges[edge] = False

            # Removing the node from path since we are backtracking now
            path.pop(-1)

        try:
            dfs(start_node)
        except AssertionError:
            pass
        else:
            print('Path Not Found !!')

        return path


if __name__ == '__main__':
    edges = [
        (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 6), (6, 4), (4, 2), (2, 0)
    ]
    graph = Graph()
    graph.make_graph(edges=edges, is_directed=True)

    path_type = graph.get_type()
    print(path_type)

    if path_type != PathType.NON_EULAIAN:
        path = graph.get_path(path_type=path_type)
        print(" -> ".join(map(str, path)))