Graph Algorithms

Note

These functions are mostly geared towards directed graphs (digraphs).

pytools.graph.reverse_graph(graph: GraphT[NodeT]) → GraphT[NodeT]

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: Callable[[NodeT], float] | None = None, get_step_cost: Callable[[Any, NodeT], float] | None = None) → list[NodeT]

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

pytools.graph.compute_sccs(graph: GraphT[NodeT]) → list[list[NodeT]]

exception pytools.graph.CycleError(node: Hashable)

Raised when a topological ordering cannot be computed due to a cycle.

node: Hashable

Node in a directed graph that is part of a cycle.

pytools.graph.compute_topological_order(graph: GraphT[NodeT], key: Callable[[NodeT], optype.CanLt[Any]] | None = None) → list[NodeT]

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]

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

Added in version 2020.2.

pytools.graph.contains_cycle(graph: GraphT[NodeT]) → bool

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]

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

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

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

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

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]

Constructs an undirected graph using edges.

Parameters:

edges – An Iterable of pairs of related NodeT s.

Returns:

A GraphT that is the undirected graph.

pytools.graph.get_reachable_nodes(undirected_graph: GraphT[NodeT], source_node: NodeT, exclude_nodes: Collection[NodeT] | None = None) → frozenset[NodeT]

Returns a frozenset of all nodes in undirected_graph that are reachable from source_node.

If any node from exclude_nodes lies on a path between source_node and some other node \(u\) in undirected_graph and there are no other viable paths, then \(u\) is considered not reachable from source_node.

In the case where source_node is in exclude_nodes, then no node is reachable from source_node, so an empty frozenset is returned.

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 a collections.abc.Collection of its successor nodes. Note that most functions expect that every graph node is included as a key in the graph.