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)[source]¶ Compute a toplogical 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.Iterable
of nodes that are connected to the node by outgoing edges. Returns
A
list
representing a valid topological ordering of the nodes in the directed graph.
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 – 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)[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.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, subgraph_nodes)[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.