1 """ Graph search classes
2
3 The search algorithms are implemented as an abstract class with
4 visitor functions that are called at points during the algorithm.
5 By designing different visitor functions the search algorithms
6 can produce shortest path lenghts, forests of search trees, etc.
7
8 The simplest way to access the search algorithms is by using
9 predefined visitor classes and search functions.
10 See the module networkx.search.
11
12 These algorithms are based on Program 18.10 "Generalized graph search",
13 page 128, Algorithms in C, Part 5, Graph Algorithms by Robert Sedgewick
14
15 Reference::
16
17 @Book{sedgewick-2001-algorithms-5,
18 author = {Robert Sedgewick},
19 title = {Algorithms in C, Part 5: Graph Algorithms},
20 publisher = {Addison Wesley Professional},
21 year = {2001},
22 edition = {3rd},
23 }
24
25 """
26 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
27 __date__ = "$Date: 2005-06-15 08:17:35 -0600 (Wed, 15 Jun 2005) $"
28 __credits__ = """"""
29 __revision__ = "$Revision: 1025 $"
30
31
32
33
34
35
36
37 import networkx
38
39
40
42 """
43 Generic graph traversal (search) class.
44
45 Users should generally use the search functions defined below.
46 e.g. to get a list of all nodes of G in breadth first search (BFS)
47 order from v use
48
49 vertex_list=bfs_preorder(G,v)
50
51 To search the graph G from v do the following:
52
53 S=Search(G,queue=DFS)
54 S.search(v=v)
55
56 Depending on the type of queue you will get a different traversal type.
57
58 You may use any of the following queues from the Queues class:
59 Name Queue Traversal
60 ----- ------ ----------
61 DFS LIFO Depth First Search
62 BFS FIFO Breadth First Search
63 Random Random Random search
64
65 The generic search produces no data and thus is of limited utility.
66 Visitor callback functions are called at points along the search
67 which may be used to store shortest path data
68
69 """
71 self.seen={}
72 self.tree={}
73 self.fringe=queue()
74 self.G=G
75
77 """
78 Search the graph.
79
80 The search method is deteremined by the initialization of the
81 search object.
82
83 The optional v= argument can be a single vertex a list or None.
84
85 v=v: search the component of G reachable from v
86 v=vlist: search the component of G reachable from v
87 v=None: search the entire graph G even if it isn't connected
88
89 Call visitor functions along the way.
90
91 """
92
93 nodes=[]
94 if v is None:
95 nodes=self.G.nodes()
96 elif isinstance(v, list):
97 nodes=v
98 else:
99 nodes=[v]
100
101
102 for v in nodes:
103 if not self.seen.has_key(v):
104 self.start_tree(v)
105 e=(v,v)
106 self.__search_connected(e)
107 self.end_tree(v)
108
110 """
111 Private method to this class.
112
113 Search a single connected component starting at the edge e.
114 To start from a vertex v, use e=(v,v).
115 Call the visitor functions along the way.
116
117 """
118 (v,w)=e
119 self.seen.setdefault(w)
120 self.firstseen_vertex(w)
121 self.fringe.append(e)
122 self.firstseen_edge(e)
123 while(len(self.fringe)>0):
124 e=self.fringe.pop()
125 (v,w)=e
126 self.lastseen_edge(e)
127 self.lastseen_vertex(w)
128 self.tree.setdefault(w,v)
129 for n in self.G.neighbors(w):
130 if not self.seen.has_key(n):
131 self.seen.setdefault(n)
132 self.firstseen_vertex(n)
133 self.fringe.append((w,n))
134 self.firstseen_edge((w,n))
135 elif not self.tree.has_key(n):
136 self.fringe.update((w,n))
137 self.firstseen_edge((w,n))
138
139
141 """Visitor function called at the search start
142 of each connected component.
143 """
144 pass
145
147 """Visitor function called the first time a vertex is encountered."""
148 pass
149
151 """Visitor function called the last time a vertex is encountered."""
152 pass
153
155 """Visitor function called at the search end
156 of each connected component.
157 """
158 pass
159
161 """Visitor function called the first time an edge is encountered."""
162 pass
163
165 """Visitor function called the last time an edge is encountered."""
166 pass
167
168
170 """ Preorder visitor
171 Builds a list of nodes in preorder of search.
172 Returns a list of lists if the graph is not connected.
173 """
177
179 """Visitor function called at the search start
180 of each connected component.
181 """
182 self.vlist=[]
183
185 """Visitor function called the first time a vertex is encountered."""
186 self.vlist.append(v)
187
189 """Visitor function called at the search end
190 of each connected component.
191 """
192 self.forest.append(self.vlist)
193
194
195 -class Postorder(Search):
196 """ Postorder visitor
197 Builds a list of nodes in postorder of search.
198 Returns a list of lists if the graph is not connected.
199 """
200 - def __init__(self, G, queue=networkx.queues.DFS, **kwds):
201 self.forest=[]
202 super(Postorder,self).__init__(G, queue=queue)
203
204
205 - def start_tree(self,v):
206 """Visitor function called at the search start
207 of each connected component.
208 """
209 self.vlist=[]
210
211 - def lastseen_vertex(self,v):
212 """Visitor function called the last time a vertex is encountered."""
213 self.vlist.append(v)
214
215 - def end_tree(self,v):
216 """Visitor function called at the search end
217 of each connected component.
218 """
219 self.forest.append(self.vlist)
220
221
223 """ Predeceessor visitor
224 Builds a dict of nodes with sucessor vertex list as data.
225 path method returns path lengths from source to target.
226 """
230
231
233 """Visitor function called the first time a vertex is encountered."""
234 self.data[v]=[]
235
237 """Visitor function called the last time an edge is encountered."""
238 (u,v)=e
239 if not u==v:
240 self.data[v].append(u)
241
242
243 - def path(self, target):
244 """Gets one shortest path to target out of predecessor hash.
245 There might be more than one
246 """
247 path=[]
248 if self.data.has_key(target):
249 while not self.data[target]==[]:
250 path.append(target)
251 target=self.data[target][0]
252 path.reverse()
253 return path
254 else:
255 return []
256
257
259 """ Successor visitor
260 Builds a dict of nodes with sucessor vertex list as data.
261 """
265
267 """Visitor function called the first time a vertex is encountered."""
268 self.data.setdefault(v,[])
269
271 """Visitor function called the last time an edge is encountered."""
272 (u,v)=e
273 if not u==v:
274 self.data[u].append(v)
275
277 """ Path length visitor.
278 Returns dictionary of path lengths from vertex v.
279 Useful especially in BFS (gives shortest paths).
280 """
284
286 """Visitor function called the first time an edge is encountered."""
287 (u,v)=e
288 if u==v:
289 self.length[u]=0
290 else:
291 level=self.length[u]
292 self.length[v]=level+1
293
294
296 """
297 Forest visitor: build a forest of trees as a list of networkx DiGraphs.
298 """
302
304 """Visitor function called at the search start
305 of each connected component.
306 """
307 self.T=networkx.DiGraph()
308 self.T.add_node(v)
309
311 """Visitor function called the last time an edge is encountered."""
312 (u,v)=e
313 if not u==v:
314 self.T.add_edge(u,v)
315
317 """Visitor function called at the search end
318 of each connected component.
319 """
320 self.forest.append(self.T)
321
323 import doctest
324 suite = doctest.DocFileSuite('tests/search_class.txt',package='networkx')
325 return suite
326
327
328 if __name__ == "__main__":
329 import os
330 import sys
331 import unittest
332 if sys.version_info[:2] < (2, 4):
333 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
334 sys.exit(-1)
335
336 nxbase=sys.path[0]+os.sep+os.pardir
337 sys.path.insert(0,nxbase)
338 unittest.TextTestRunner().run(_test_suite())
339