Discover an Eulerian Path from a Graph.

eulerian_path.py

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

import argparse
from collections import Counter
from typing import Dict, List, Optional


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(',')

    # Add any sink nodes (nodes with no outgoing edges) to the graph
    graph.update({
        neighbor: []
        for neighbors in graph.values()
        for neighbor in neighbors if neighbor not in graph
    })
    return graph


def calc_in_degrees(graph: Dict[str, List[str]]) -> Dict[str, int]:
    """Calculate the in-degrees for the nodes in `graph`.

    Parameters
    ----------
    graph: Dict[str, List[str]]
        A dictionary that contains node relations, where the node in the key
        has an out going edge to all of the nodes in its corresponding value.

    Returns
    -------
    in_degrees: Dict[str, int]
        A dictionary that contains the in-degrees for the nodes in `graph`.
        Where the key is the node and the value is the number of incoming
        edges it has.
    """
    return Counter(
        (n for neighbors in graph.values() for n in neighbors),
    )


def find_initial_node(
    graph: Dict[str, List[str]],
    in_degrees: Dict[str, int],
) -> Optional[str]:
    """Find a suitable initial node to start the Eulerian Path.

    The trick to finding an Eulerian path is starting at the correct node. One
    must start at a node that has more out going edges than incoming edges in
    order to complete the path.

    Parameters
    ----------
    graph: Dict[str, List[str]]
        A dictionary that contains node relations, where the node in the key
        has an out going edge to all of the nodes in its corresponding value.
    in_degreees: Dict[str, int]
        A dictionary that contains the in-degrees for the nodes in `graph`.
        Where the key is the node and the value is the number of incoming
        edges it has.

    Returns
    -------
    initial_node: Optional[str]
        Returns `None` if a node does not meet the criteria to be an initial
        node. Otherwise, it returns an initial node to start the search from.
    """
    initial_node = None
    for node, in_degree in in_degrees.items():
        neighbors = graph.get(node)
        if neighbors is None:
            out_degree = 0
        else:
            out_degree = len(neighbors)
        if in_degree < out_degree:
            initial_node = node
            break
    return initial_node


def find_eulerian_path(
    graph: Dict[str, List[str]],
    in_degrees: Dict[str, int],
    node: str,
) -> List[str]:
    """Recursively identify an Eulerian Path.

    An Eulerian Path is a path that traverses each edge exactly once. This
    function will find an Eulerian Path in `graph` (if present).

    Parameters
    ----------
    graph: Dict[str, List[str]]
        The graph structure generated using `construct_graph_from_adjacency`
        that holds the node relations.
    in_degrees: Dict[str, int]
        The indegrees for each node in `graph` generated using
        `calc_in_degrees`.
    node: str
        The node that is currently being searched.

    Returns
    -------
    path: List[str]
        A list of nodes representing the Eulerian Path.
    """
    path = [node]
    while graph[node]:
        path = path[:1] + find_eulerian_path(
            graph,
            in_degrees,
            graph[node].pop(),
        ) + path[1:]
    return path


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)
    IN_DEGREES = calc_in_degrees(GRAPH)
    INITIAL_NODE = find_initial_node(GRAPH, IN_DEGREES)
    if INITIAL_NODE is not None:
        EULERIAN_PATH = find_eulerian_path(GRAPH, IN_DEGREES, INITIAL_NODE)

    if any(not neighbors for neighbors in GRAPH.values()):
        print('The Eulerian Path is:', ' -> '.join(EULERIAN_PATH))
    else:
        print('There is no Eulerian Path.')