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.


Returns a generator of nodes in topologically sorted order.


Stratifies a DAG into generations.


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.


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


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.


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


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


Iterate through the graph to compute all v-structures.