Discover an Eulerian Cycle from a graph.

eulerian_cycle.py

"""Discover an Eulerian Cycle from a graph."""

import argparse
from typing import Dict, List


def construct_graph_from_adjacency(
    graph_file_path: str,
) -> Dict[str, List[str]]:
    """Construct a graph from an adjacency list in `graph_file_path`.

    This function parses a file that represents a graph in an adjacency format,
    such that each line is an (are) edge(s) formatted as `A -> B,C` which
    indicates that there is an edge from node `A` to node `B` and an edge from
    node `A` to node `C`. If there is only one edge the line can be formatted
    as `C -> D`.

    This function returns a dictionary with the keys as nodes and the values as
    a list of nodes where there is an edge from the key to the node in the
    list. For example, a graph with edges `A -> B,C`, `B -> C`, and `D -> A`
    would be represented as:
    `{
        'A': ['B', 'C'],
        'B': ['C'],
        'D': ['A'],
    }`

    Parameters
    ----------
    graph_file_path: str
        The path to the file that contains the graph specification.

    Returns
    -------
    graph: Dict[str, List[str]]
        A dictionary that contains the node relations.
    """
    with open(graph_file_path) as graph_fh:
        graph = {}
        for line in graph_fh:
            edge = line.strip().split(' -> ')
            graph[edge[0]] = edge[1].split(',')
    return graph


def find_eulerian_cycle(
    graph: Dict[str, List[str]],
    node: str,
) -> List[str]:
    """Recursively identify an Eulerian Cycle.

    An Eulerian Cycle is a cycle that traverses each edge exactly once (and by
    definition of being a cycle, returns to the node from which it starts).
    This function will find the Eulerian cycle in `graph` (if present).

    Parameters
    ----------
    graph: Dict[str, List[str]]
        The graph structure generated using `construct_graph_from_adjacency`
        that holds the node relations.
    node: str
        The current node to search for in the cycle.


    Returns
    -------
    cycle: List[str]
        A list of nodes representing the Eulerian cycle. If the first and last
        elements don't match, then an Eulerian cycle isn't possible for this
        graph.
    """
    cycle = [node]
    while graph[node]:
        cycle = cycle[:1] + find_eulerian_cycle(
            graph,
            graph[node].pop(),
        ) + cycle[1:]
    return cycle


if __name__ == '__main__':
    PARSER = argparse.ArgumentParser('Eulerian Cycle')
    PARSER.add_argument(
        'graph_adjacency_path',
        help='Path to the graph adjacency file',
    )
    ARGS = PARSER.parse_args()

    GRAPH = construct_graph_from_adjacency(ARGS.graph_adjacency_path)
    INITIAL_NODE = list(GRAPH.keys())[0]
    EULERIAN_CYCLE = find_eulerian_cycle(GRAPH, INITIAL_NODE)

    if EULERIAN_CYCLE[0] == EULERIAN_CYCLE[-1]:
        print('The Eulerian Cycle is:', ' -> '.join(EULERIAN_CYCLE))
    else:
        print('There is no Eulerian Cycle.')

It is interesting that there is a linear time algorithm to identify the Eulerian Cycle, however, if you change the definition sightly to "pass through every vertex exactly once" (instead of each edge) then it becomes NP-Complete. Passing through each vertex exactly once is called a Hamiltonian Cycle.

Additionally, according to Dirac's theory every graph with n >= 3 and m >= n / 2 where n is the number of vertices and m is the minimum degree of the vertices has a Hamiltonian Cycle. This can obviously be computed in linear time. See also: Ore's theorem.