# Graph Algorithms

pytools.graph.a_star(initial_state, goal_state, neighbor_map, estimate_remaining_cost=None, get_step_cost=<function <lambda>>)

  With the default cost and heuristic, this amounts to Dijkstra’s algorithm.

pytools.graph.compute_sccs(graph: Mapping[pytools.graph.T, Iterable[pytools.graph.T]]) → List[List[pytools.graph.T]]

class pytools.graph.CycleError(node)

  Raised when a topological ordering cannot be computed due to a cycle.

  Attr node

    Node in a directed graph that is part of a cycle.

pytools.graph.compute_topological_order(graph: Mapping[pytools.graph.T, Iterable[pytools.graph.T]], key: Optional[Callable[[pytools.graph.T], Any]] = None) → List[pytools.graph.T]

  Compute a topological order of nodes in a directed graph.

  Parameters

    - graph – A `collections.abc.Mapping` representing a directed graph. The dictionary contains one key representing each node in the graph, and this key maps to a `collections.abc.Iterable` of its successor nodes.

    - key – A custom key function may be supplied to determine the order in break-even cases. Expects a function of one argument that is used to extract a comparison key from each node of the graph.

  Returns

    A `list` representing a valid topological ordering of the nodes in the directed graph.

  Note

  - Requires the keys of the mapping graph to be hashable.

  - Implements Kahn’s algorithm.

  New in version 2020.2.

pytools.graph.compute_transitive_closure(graph: Mapping[pytools.graph.T, MutableSet[pytools.graph.T]]) → Mapping[pytools.graph.T, MutableSet[pytools.graph.T]]
  Compute the transitive closure of a directed graph using Warshall’s

    algorithm.

  Parameters

    graph – A `collections.abc.Mapping` representing a directed graph. The dictionary contains one key representing each node in the graph, and this key maps to a `collections.abc.MutableSet` of nodes that are connected to the node by outgoing edges. This graph may contain cycles. This object must be picklable. Every graph node must be included as a key in the graph.

  Returns

    The transitive closure of the graph, represented using the same data type.

  New in version 2020.2.

pytools.graph.contains_cycle(graph: Mapping[pytools.graph.T, Iterable[pytools.graph.T]]) → bool

  Determine whether a graph contains a cycle.

  Parameters

    graph – A `collections.abc.Mapping` representing a directed graph. The dictionary contains one key representing each node in the graph, and this key maps to a `collections.abc.Iterable` of nodes that are connected to the node by outgoing edges.

  Returns

    A `bool` indicating whether the graph contains a cycle.

  New in version 2020.2.

pytools.graph.compute_induced_subgraph(graph: Mapping[pytools.graph.T, Set[pytools.graph.T]], subgraph_nodes: Set[pytools.graph.T]) → Mapping[pytools.graph.T, Set[pytools.graph.T]]
  Compute the induced subgraph formed by a subset of the vertices in a

    graph.

  Parameters

    - graph – A `collections.abc.Mapping` representing a directed graph. The dictionary contains one key representing each node in the graph, and this key maps to a `collections.abc.Set` of nodes that are connected to the node by outgoing edges.

    - subgraph_nodes – A `collections.abc.Set` containing a subset of the graph nodes in the graph.

  Returns

    A `dict` representing the induced subgraph formed by the subset of the vertices included in subgraph_nodes.

  New in version 2020.2.

## Type Variables Used

class pytools.graph.T

  Any type.