1 """
2 Search algorithms.
3
4 See also networkx.path.
5
6 """
7 __authors__ = """Eben Kenah (ekenah@t7.lanl.gov)\nAric Hagberg (hagberg@lanl.gov)"""
8 __date__ = ""
9 __revision__ = ""
10
11
12
13
14
15
16
17 import networkx
19 """
20 Return list of nodes connected to source in DFS preorder.
21 Traverse the graph G with depth-first-search from source.
22 Non-recursive algorithm.
23 """
24 if source is None:
25 nlist=G.nodes()
26 else:
27 nlist=[source]
28
29 if reverse_graph==True:
30 try:
31 neighbors=G.in_neighbors
32 except:
33 neighbors=G.neighbors
34 else:
35 neighbors=G.neighbors
36
37 seen={}
38 pre=[]
39 for source in nlist:
40 if source in seen: continue
41 lifo=[source]
42 while lifo:
43 v = lifo.pop()
44 if v in seen: continue
45 pre.append(v)
46 seen[v]=True
47 lifo.extend([w for w in G.neighbors(v) if w not in seen])
48 return pre
49
50
51 -def dfs_postorder(G,source=None,reverse_graph=False):
52 """
53 Return list of nodes connected to source in DFS preorder.
54 Traverse the graph G with depth-first-search from source.
55 Non-recursive algorithm.
56 """
57 if source is None:
58 nlist=G.nodes()
59 else:
60 nlist=[source]
61
62 if reverse_graph==True:
63 try:
64 neighbors=G.in_neighbors
65 except:
66 neighbors=G.neighbors
67 else:
68 neighbors=G.neighbors
69
70 seen={}
71 post=[]
72 for source in nlist:
73 if source in seen: continue
74 queue=[source]
75 while queue:
76 v=queue[-1]
77 if v not in seen:
78 seen[v]=True
79 done=1
80 for w in neighbors(v):
81 if w not in seen:
82 queue.append(w)
83 done=0
84 break
85 if done==1:
86 post.append(v)
87 queue.pop()
88 return post
89
90
91 -def dfs_tree(G,source=None,reverse_graph=False):
92 """Return directed graph (tree) of depth-first-search with root at source.
93 If the graph is disconnected, return a disconnected graph (forest).
94 """
95 succ=dfs_successor(G,source=source,reverse_graph=reverse_graph)
96 return networkx.DiGraph(succ)
97
99 """
100 Return predecessors of depth-first-search with root at source.
101 """
102 if source is None:
103 nlist=G.nodes()
104 else:
105 nlist=[source]
106
107 if reverse_graph==True:
108 try:
109 neighbors=G.in_neighbors
110 except:
111 neighbors=G.neighbors
112 else:
113 neighbors=G.neighbors
114
115 seen={}
116 pred={}
117 for source in nlist:
118 if source in seen: continue
119 queue=[source]
120 pred[source]=[]
121 while queue:
122 v=queue[-1]
123 if v not in seen:
124 seen[v]=True
125 done=1
126 for w in neighbors(v):
127 if w not in seen:
128 queue.append(w)
129 pred[w]=[v]
130 done=0
131 break
132 if done==1:
133 queue.pop()
134 return pred
135
136
138 """
139 Return succesors of depth-first-search with root at source.
140 """
141
142 if source is None:
143 nlist=G.nodes()
144 else:
145 nlist=[source]
146
147 if reverse_graph==True:
148 try:
149 neighbors=G.in_neighbors
150 except:
151 neighbors=G.neighbors
152 else:
153 neighbors=G.neighbors
154
155 seen={}
156 succ={}
157 for source in nlist:
158 if source in seen: continue
159 queue=[source]
160 while queue:
161 v=queue[-1]
162 if v not in seen:
163 seen[v]=True
164 succ[v]=[]
165 done=1
166 for w in neighbors(v):
167 if w not in seen:
168 queue.append(w)
169 succ[v].append(w)
170 done=0
171 break
172 if done==1:
173 queue.pop()
174 return succ
175
176
178 import doctest
179 suite = doctest.DocFileSuite('tests/search.txt',package='networkx')
180 return suite
181
182
183 if __name__ == "__main__":
184 import os
185 import sys
186 import unittest
187 if sys.version_info[:2] < (2, 4):
188 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
189 sys.exit(-1)
190
191 nxbase=sys.path[0]+os.sep+os.pardir
192 sys.path.insert(0,nxbase)
193 unittest.TextTestRunner().run(_test_suite())
194