Source code for coalib.core.Graphs

from coalib.core.CircularDependencyError import CircularDependencyError


[docs]def traverse_graph(start_nodes, get_successive_nodes, run_on_edge=lambda prev, nxt: None): """ Traverses all edges of a directed, possibly disconnected graph once. Detects cyclic graphs by raising a ``CircularDependencyError``. >>> graph = {1: [2], 2: [3, 4], 5: [3], 3: [6]} >>> def get_successive_nodes(node): ... return graph.get(node, []) >>> edges = set() >>> def append_to_edges(prev, nxt): ... edges.add((prev, nxt)) >>> traverse_graph([1, 5], get_successive_nodes, append_to_edges) >>> sorted(edges) [(1, 2), (2, 3), (2, 4), (3, 6), (5, 3)] You can also use this function to detect cyclic graphs: >>> graph = {1: [2], 2: [3], 3: [1]} >>> traverse_graph([1], get_successive_nodes) Traceback (most recent call last): ... coalib.core.CircularDependencyError.CircularDependencyError: ... :param start_nodes: The nodes where to start traversing the graph. :param get_successive_nodes: A callable that takes in a node and returns an iterable of nodes to traverse next. :param run_on_edge: A callable that is run on each edge during traversing. Takes in two parameters, the previous- and next-node which form an edge. The default is an empty function. :raises CircularDependencyError: Raised when the graph is cyclic. """ path = set() visited_nodes = set() def visit(node): if node not in visited_nodes: visited_nodes.add(node) path.add(node) for subnode in get_successive_nodes(node): run_on_edge(node, subnode) if subnode in path: raise CircularDependencyError([repr(subnode), '...', repr(subnode)]) visit(subnode) path.remove(node) for node in start_nodes: visit(node)