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 |