1
2 """
3 Algorithms for directed acyclic graphs (DAGs).
4 """
5 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
6 ___revision__ = ""
7
8
9
10
11
12
13 import networkx
14
16 """Return True if the graph G is a directed acyclic graph (DAG).
17
18 Otherwise return False.
19
20 """
21 if topological_sort(G) is None:
22 return False
23 else:
24 return True
25
27 """
28 Return a list of nodes of the digraph G in topological sort order.
29
30 A topological sort is a nonunique permutation of the nodes
31 such that an edge from u to v implies that u appears before v in the
32 topological sort order.
33
34 If G is not a directed acyclic graph no topological sort exists
35 and the Python keyword None is returned.
36
37 This algorithm is based on a description and proof at
38 http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm
39
40 See also is_directed_acyclic_graph()
41
42 """
43
44
45 seen={}
46 order_explored=[]
47 explored={}
48
49 if not G.is_directed(): G.successors_iter=G.neighbors_iter
50
51 for v in G.nodes_iter():
52 if v in explored: continue
53
54 fringe=[v]
55 while fringe:
56 w=fringe[-1]
57 if w in explored:
58 fringe.pop()
59 continue
60 seen[w]=1
61
62 new_nodes=[]
63 for n in G.successors_iter(w):
64 if n not in explored:
65 if n in seen: return
66 new_nodes.append(n)
67 if new_nodes:
68 fringe.extend(new_nodes)
69 else:
70 explored[w]=1
71 order_explored.insert(0,w)
72 fringe.pop()
73 return order_explored
74
76 """
77 Return a list of nodes of the digraph G in topological sort order.
78
79 This is a recursive version of topological sort.
80
81 """
82
83 def _dfs(G,seen,explored,v):
84 seen[v]=1
85 for w in G.successors(v):
86 if w not in seen:
87 if not _dfs(G,seen,explored,w):
88 return
89 elif w in seen and w not in explored:
90
91 return False
92 explored.insert(0,v)
93 return v
94
95 seen={}
96 explored=[]
97
98 if not G.is_directed(): G.successors=G.neighbors
99
100 for v in G.nodes_iter():
101 if v not in explored:
102 if not _dfs(G,seen,explored,v):
103 return
104 return explored
105
106
108 import doctest
109 suite = doctest.DocFileSuite('tests/dag.txt',package='networkx')
110 return suite
111
112
113 if __name__ == "__main__":
114 import os
115 import sys
116 import unittest
117 if sys.version_info[:2] < (2, 4):
118 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
119 sys.exit(-1)
120
121 nxbase=sys.path[0]+os.sep+os.pardir
122 sys.path.insert(0,nxbase)
123 unittest.TextTestRunner().run(_test_suite())
124