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

`pytools.graph.``compute_sccs`(graph)[source]
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 – A `collections.abc.Mapping` representing a directed graph. The dictionary contains one key representing each node in the graph, and this key maps to a `collections.abc.Iterable` of its successor nodes.

• 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

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

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 a `collections.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
Returns

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

New in version 2020.2.