# Graph AlgorithmsÂ¶

Note

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

pytools.graph.reverse_graph(graph: ) [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.

pytools.graph.compute_sccs(graph: ) List[List[NodeT]][source]Â¶
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: , 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

pytools.graph.compute_transitive_closure(graph: Mapping[NodeT, MutableSet[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 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.

pytools.graph.contains_cycle(graph: ) bool[source]Â¶

Determine whether a graph contains a cycle.

Returns:

A `bool` indicating whether the graph contains a cycle.

pytools.graph.compute_induced_subgraph(graph: Mapping[NodeT, Set[NodeT]], subgraph_nodes: Set[NodeT]) [source]Â¶

Compute the induced subgraph formed by a subset of the vertices in a graph.

Parameters:
Returns:

A `dict` representing the induced subgraph formed by the subset of the vertices included in subgraph_nodes.

pytools.graph.as_graphviz_dot(graph: , 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: ) 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: ) bool[source]Â¶

Returns whether all nodes in graph are connected, ignoring the edge direction.

Returns:

A `bool` indicating whether the graph is connected.

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