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.
|
Returns all nodes having a path to |
|
Returns all nodes reachable from |
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. |
|
|
Generate the nodes in the unique lexicographical topological sort order. |
Returns True if the graph |
|
|
Returns True if |
|
Returns transitive closure of a graph |
|
Returns the transitive closure of a directed acyclic graph. |
Returns transitive reduction of a directed graph |
|
|
Generates antichains from a directed acyclic graph (DAG). |
|
Returns the longest path in a directed acyclic graph (DAG). |
|
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. |