Graph Algorithms

pytools.graph.a_star(initial_state, goal_state, neighbor_map, estimate_remaining_cost=None, get_step_cost=<function <lambda>>)

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

pytools.graph.compute_sccs(graph)

Parameters

graph (Mapping[T, Iterable[T]]) –

Return type

List[List[T]]

class pytools.graph.CycleError(node)

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)

Compute a topological order of nodes in a directed graph.

Parameters

• graph (Mapping[T, Iterable[T]]) – 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 (Optional[Callable[[T], Any]]) – 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.

• graph –

• key –

Returns

A list representing a valid topological ordering of the nodes in the directed graph.

Return type

List[T]

Note

• Requires the keys of the mapping graph to be hashable.

• Implements Kahn’s algorithm.

New in version 2020.2.

pytools.graph.compute_transitive_closure(graph)

Compute the transitive closure of a directed graph using Warshall’s

algorithm.

Parameters

• graph (Mapping[T, MutableSet[T]]) – 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.

• graph –

Returns

The transitive closure of the graph, represented using the same data type.

Return type

Mapping[T, MutableSet[T]]

New in version 2020.2.

pytools.graph.contains_cycle(graph)

Determine whether a graph contains a cycle.

Parameters

• graph (Mapping[T, Iterable[T]]) – 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.

• graph –

Returns

A bool indicating whether the graph contains a cycle.

Return type

bool

New in version 2020.2.

pytools.graph.compute_induced_subgraph(graph, subgraph_nodes)

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

graph.

Parameters

• graph (Mapping[T, Set[T]]) – 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.Set of nodes that are connected to the node by outgoing edges.

• subgraph_nodes (Set[T]) – A collections.abc.Set containing a subset of the graph nodes in the graph.

• graph –

• subgraph_nodes –

Returns

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

Return type

Mapping[T, Set[T]]

New in version 2020.2.

Type Variables Used

class pytools.graph.T

Any type.