Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

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)	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 directed acyclic graph (DAG).
dag_longest_path(G[, weight, default_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.