Skip to main content
`Ctrl`+`K`

# 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) | Yields 3-node tuples that represent the v-structures in `G`.
`colliders`(G) | Yields 3-node tuples that represent the colliders in `G`.
`v_structures`(G) | Yields 3-node tuples that represent the v-structures in `G`.