Graph Algorithms#

pytools.graph.reverse_graph(graph: Mapping[T, Collection[T]]) Dict[T, FrozenSet[T]][source]#

Reverses a graph.

Parameters:

graph – A dict representation of a directed graph, mapping each node to other nodes to which it is connected by edges.

Returns:

A dict representing graph with edges reversed.

pytools.graph.a_star(initial_state: ~pytools.graph.T, goal_state: ~pytools.graph.T, neighbor_map: ~typing.Mapping[~pytools.graph.T, ~typing.Collection[~pytools.graph.T]], estimate_remaining_cost: ~typing.Optional[~typing.Callable[[~pytools.graph.T], float]] = None, get_step_cost: ~typing.Callable[[~typing.Any, ~pytools.graph.T], float] = <function <lambda>>) List[T][source]#

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

pytools.graph.compute_sccs(graph: Mapping[T, Collection[T]]) List[List[T]][source]#
class pytools.graph.CycleError(node: T)[source]#

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[T, Collection[T]], key: Optional[Callable[[T], Any]] = None) List[T][source]#

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.Collection 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

New in version 2020.2.

pytools.graph.compute_transitive_closure(graph: Mapping[T, MutableSet[T]]) Mapping[T, MutableSet[T]][source]#
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[T, Collection[T]]) bool[source]#

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.Collection 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[T, Set[T]], subgraph_nodes: Set[T]) Mapping[T, Set[T]][source]#
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.

pytools.graph.validate_graph(graph: Mapping[T, Collection[T]]) None[source]#

Validates that all successor nodes of each node in graph are keys in graph itself. Raises a ValueError if not.

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.Collection of nodes that are connected to the node by outgoing edges.

Type Variables Used#

class pytools.graph.T#

Any type.