Graph Algorithms#
- pytools.graph.reverse_graph(graph: Mapping[T, Collection[T]]) Dict[T, FrozenSet[T]] [source]#
Reverses a graph.
- 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.
- 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 acollections.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
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[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 acollections.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 acollections.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 acollections.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 acollections.abc.Collection
of nodes that are connected to the node by outgoing edges.
Type Variables Used#
- class pytools.graph.T#
Any type.