Graph Algorithms¶
-
pytools.graph.
a_star
(initial_state, goal_state, neighbor_map, estimate_remaining_cost=None, get_step_cost=<function <lambda>>)[source]¶ With the default cost and heuristic, this amounts to Dijkstra’s algorithm.
-
class
pytools.graph.
CycleError
(node)[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, key=None)[source]¶ Compute a topological order of nodes in a directed graph.
- Parameters
graph (Mapping[T, Iterable[T]]) – 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.Iterable
of its successor nodes.key (Optional[Callable[[T], Any]]) – 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.
graph –
key –
- Returns
A
list
representing a valid topological ordering of the nodes in the directed graph.- Return type
List[T]
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)[source]¶ - Compute the transitive closure of a directed graph using Warshall’s
algorithm.
- Parameters
graph (Mapping[T, MutableSet[T]]) – 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.graph –
- Returns
The transitive closure of the graph, represented using the same data type.
- Return type
New in version 2020.2.
-
pytools.graph.
contains_cycle
(graph)[source]¶ Determine whether a graph contains a cycle.
- Parameters
graph (Mapping[T, Iterable[T]]) – 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.Iterable
of nodes that are connected to the node by outgoing edges.graph –
- Returns
A
bool
indicating whether the graph contains a cycle.- Return type
New in version 2020.2.
-
pytools.graph.
compute_induced_subgraph
(graph, subgraph_nodes)[source]¶ - Compute the induced subgraph formed by a subset of the vertices in a
graph.
- Parameters
graph (Mapping[T, Set[T]]) – 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 (Set[T]) – A
collections.abc.Set
containing a subset of the graph nodes in the graph.graph –
subgraph_nodes –
- Returns
A
dict
representing the induced subgraph formed by the subset of the vertices included in subgraph_nodes.- Return type
New in version 2020.2.
Type Variables Used¶
-
class
pytools.graph.
T
¶ Any type.