dag
===

>>> import networkx as NX

Topological Sort
----------------

>>> DG=NX.DiGraph()
>>> DG.add_edges_from([(1,2),(1,3),(2,3)])
>>> NX.topological_sort(DG)
[1, 2, 3]
>>> NX.topological_sort_recursive(DG)
[1, 2, 3]
>>> DG.add_edge(3,2)
>>> NX.topological_sort(DG) is None
True
>>> NX.topological_sort_recursive(DG) is None
True
>>> DG.delete_edge(2,3)
>>> NX.topological_sort(DG)
[1, 3, 2]
>>> NX.topological_sort_recursive(DG)
[1, 3, 2]

>>> DG=NX.DiGraph()
>>> DG.add_cycle([1,2,3,4,5])
>>> DG.add_path([11,12,13,14,15])
>>> NX.topological_sort(DG) is None
True
>>> NX.topological_sort_recursive(DG) is None
True
>>> NX.is_directed_acyclic_graph(DG)
False
>>> DG.delete_edge(1,2)
>>> NX.topological_sort_recursive(DG)
[11, 12, 13, 14, 15, 2, 3, 4, 5, 1]
>>> NX.topological_sort(DG)
[11, 12, 13, 14, 15, 2, 3, 4, 5, 1]
>>> NX.is_directed_acyclic_graph(DG)
True

>>> DG=NX.DiGraph()
>>> DG.add_edges_from([(1,i) for i in range(2,5)])
>>> DG.add_edges_from([(2,i) for i in range(5,9)])
>>> DG.add_edges_from([(6,i) for i in range(9,12)])
>>> DG.add_edges_from([(4,i) for i in range(12,15)])
>>> NX.topological_sort_recursive(DG)
[1, 4, 14, 13, 12, 3, 2, 7, 6, 11, 10, 9, 5, 8]
>>> NX.topological_sort(DG)
[1, 2, 8, 5, 6, 9, 10, 11, 7, 3, 4, 12, 13, 14]
>>> DG.add_edge(14,1)
>>> NX.topological_sort(DG) is None
True
>>> NX.topological_sort_recursive(DG) is None
True

>>> G=NX.Graph()
>>> G.add_edge(1,2)
>>> NX.topological_sort(G) is None
True
>>> NX.topological_sort_recursive(G) is None
True