Directed Acyclic Graphs#

Algorithms for directed acyclic graphs (DAGs).

Note that most of these functions are only guaranteed to work for DAGs. In general, these functions do not check for acyclic-ness, so it is up to the user to check for that.

ancestors(G, source)

Returns all nodes having a path to source in G.

descendants(G, source)

Returns all nodes reachable from source in G.

topological_sort(G)

Returns a generator of nodes in topologically sorted order.

topological_generations(G)

Stratifies a DAG into generations.

all_topological_sorts(G)

Returns a generator of _all_ topological sorts of the directed graph G.

lexicographical_topological_sort(G[, key])

Generate the nodes in the unique lexicographical topological sort order.

is_directed_acyclic_graph(G)

Returns True if the graph G is a directed acyclic graph (DAG) or False if not.

is_aperiodic(G)

Returns True if G is aperiodic.

transitive_closure(G[, reflexive])

Returns transitive closure of a graph

transitive_closure_dag(G[, topo_order])

Returns the transitive closure of a directed acyclic graph.

transitive_reduction(G)

Returns transitive reduction of a directed graph

antichains(G[, topo_order])

Generates antichains from a directed acyclic graph (DAG).

dag_longest_path(G[, weight, ...])

Returns the longest path in a directed acyclic graph (DAG).

dag_longest_path_length(G[, weight, ...])

Returns the longest path length in a DAG

dag_to_branching(G)

Returns a branching representing all (overlapping) paths from root nodes to leaf nodes in the given directed acyclic graph.

compute_v_structures(G)

Iterate through the graph to compute all v-structures.