Module dag

source code

Algorithms for directed acyclic graphs (DAGs).

Author: Aric Hagberg (hagberg@lanl.gov) Dan Schult(dschult@colgate.edu)

Functions

[hide private]

is_directed_acyclic_graph(G)
Return True if the graph G is a directed acyclic graph (DAG).

source code

topological_sort(G)
Return a list of nodes of the digraph G in topological sort order.

source code

topological_sort_recursive(G)
Return a list of nodes of the digraph G in topological sort order.

source code

_test_suite()

source code

Variables

[hide private]

___revision__ = ''

Function Details

[hide private]

is_directed_acyclic_graph(G)

source code

Return True if the graph G is a directed acyclic graph (DAG).

Otherwise return False.

topological_sort(G)

source code

Return a list of nodes of the digraph G in topological sort order.

A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order.

If G is not a directed acyclic graph no topological sort exists and the Python keyword None is returned.

This algorithm is based on a description and proof at http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm

topological_sort_recursive(G)

source code

Return a list of nodes of the digraph G in topological sort order.

This is a recursive version of topological sort.