Directed Acyclic GraphsΒΆ

Algorithms for directed acyclic graphs (DAGs).

ancestors(G, source) Return all nodes having a path to source in G.
descendants(G, source) Return all nodes reachable from source in G.
topological_sort(G) Return a generator of nodes in topologically sorted order.
lexicographical_topological_sort(G[, key]) Return a generator of nodes in lexicographically topologically sorted order.
is_directed_acyclic_graph(G) Return True if the graph G is a directed acyclic graph (DAG) or False if not.
is_aperiodic(G) Return True if G is aperiodic.
transitive_closure(G) Returns transitive closure of a directed graph
transitive_reduction(G) Returns transitive reduction of a directed graph
antichains(G) Generates antichains from a DAG.
dag_longest_path(G[, weight, default_weight]) Returns the longest path in a DAG If G has edges with ‘weight’ attribute the edge data are used as weight values.
dag_longest_path_length(G[, weight, ...]) Returns the longest path length in a DAG