Graph Algorithms¶
Note
These functions are mostly geared towards directed graphs (digraphs).
- pytools.graph.reverse_graph(graph: GraphT[NodeT]) GraphT[NodeT] [source]¶
Reverses a graph graph.
- Returns:
A
dict
representing graph with edges reversed.
- pytools.graph.a_star(initial_state: NodeT, goal_state: NodeT, neighbor_map: GraphT[NodeT], estimate_remaining_cost: Optional[Callable[[NodeT], float]] = None, get_step_cost: Callable[[Any, NodeT], float] = <function <lambda>>) List[NodeT] [source]¶
With the default cost and heuristic, this amounts to Dijkstra’s algorithm.
- exception pytools.graph.CycleError(node: pytools.graph.NodeT)[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: GraphT[NodeT], key: Callable[[NodeT], Any] | None = None) List[NodeT] [source]¶
Compute a topological order of nodes in a directed graph.
- Parameters:
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.
Added in version 2020.2.
- pytools.graph.compute_transitive_closure(graph: Mapping[NodeT, MutableSet[NodeT]]) GraphT[NodeT] [source]¶
Compute the transitive closure of a directed graph using Warshall’s algorithm.
- Parameters:
graph – A
collections.abc.Mapping
representing a directed graph. The mapping 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.
Added in version 2020.2.
- pytools.graph.contains_cycle(graph: GraphT[NodeT]) bool [source]¶
Determine whether a graph contains a cycle.
- Returns:
A
bool
indicating whether the graph contains a cycle.
Added in version 2020.2.
- pytools.graph.compute_induced_subgraph(graph: Mapping[NodeT, Set[NodeT]], subgraph_nodes: Set[NodeT]) GraphT[NodeT] [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 mapping 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.
Added in version 2020.2.
- pytools.graph.as_graphviz_dot(graph: GraphT[NodeT], node_labels: Callable[[NodeT], str] | None = None, edge_labels: Callable[[NodeT, NodeT], str] | None = None) str [source]¶
Create a visualization of the graph graph in the dot language.
- Parameters:
node_labels – An optional function that returns node labels for each node.
edge_labels – An optional function that returns edge labels for each pair of nodes.
- Returns:
A string in the dot language.
- pytools.graph.validate_graph(graph: GraphT[NodeT]) None [source]¶
Validates that all successor nodes of each node in graph are keys in graph itself. Raises a
ValueError
if not.
- pytools.graph.is_connected(graph: GraphT[NodeT]) bool [source]¶
Returns whether all nodes in graph are connected, ignoring the edge direction.
- Returns:
A
bool
indicating whether the graph is connected.
- pytools.graph.undirected_graph_from_edges(edges: Iterable[Tuple[NodeT, NodeT]]) GraphT[NodeT] [source]¶
Constructs an undirected graph using edges.
- pytools.graph.get_reachable_nodes(undirected_graph: GraphT[NodeT], source_node: NodeT) FrozenSet[NodeT] [source]¶
Returns a
frozenset
of all nodes in undirected_graph that are reachable from source_node.
Type Variables Used¶
- class pytools.graph.NodeT¶
Type of a graph node, can be any hashable type.
- class pytools.graph.GraphT¶
A
collections.abc.Mapping
representing a directed graph. The mapping contains one key representing each node in the graph, and this key maps to acollections.abc.Collection
of its successor nodes. Note that most functions expect that every graph node is included as a key in the graph.