Package networkx :: Module search_class
[hide private]
[frames] | no frames]

Source Code for Module networkx.search_class

  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  #    Copyright (C) 2004,2005 by  
 31  #    Aric Hagberg <hagberg@lanl.gov> 
 32  #    Dan Schult <dschult@colgate.edu> 
 33  #    Pieter Swart <swart@lanl.gov> 
 34  #    Distributed under the terms of the GNU Lesser General Public License 
 35  #    http://www.gnu.org/copyleft/lesser.html 
 36   
 37  import networkx 
 38  #from networkx import DiGraph 
 39  #from queues import DFS,BFS,RFS 
 40   
41 -class Search(object):
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 """
70 - def __init__(self, G, queue=networkx.queues.DFS):
71 self.seen={} # keep track of nodes seen 72 self.tree={} # keep track of nodes put on search tree 73 self.fringe=queue() # instantiate queue for edges, "the fringe" 74 self.G=G
75
76 - def search(self, v=None):
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 # get starting vertex 93 nodes=[] 94 if v is None: # none, use entire graph 95 nodes=self.G.nodes() 96 elif isinstance(v, list): # check for a list 97 nodes=v 98 else: # assume it is a single value 99 nodes=[v] 100 101 # general search that finds all trees 102 for v in nodes: 103 if not self.seen.has_key(v): 104 self.start_tree(v) 105 e=(v,v) # form self loop as starting edge 106 self.__search_connected(e) # search the component containing v 107 self.end_tree(v)
108
109 - def __search_connected(self, e):
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) # add to seen nodes dict 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() # get edge from the fringe 125 (v,w)=e 126 self.lastseen_edge(e) 127 self.lastseen_vertex(w) 128 self.tree.setdefault(w,v) # and put it on our tree 129 for n in self.G.neighbors(w): # scan adjacency list at 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)) # put unseen edges on fringe 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 # default visitor functions
140 - def start_tree(self,v):
141 """Visitor function called at the search start 142 of each connected component. 143 """ 144 pass
145
146 - def firstseen_vertex(self,v):
147 """Visitor function called the first time a vertex is encountered.""" 148 pass
149
150 - def lastseen_vertex(self,v):
151 """Visitor function called the last time a vertex is encountered.""" 152 pass
153
154 - def end_tree(self,v):
155 """Visitor function called at the search end 156 of each connected component. 157 """ 158 pass
159
160 - def firstseen_edge(self,e):
161 """Visitor function called the first time an edge is encountered.""" 162 pass
163
164 - def lastseen_edge(self,e):
165 """Visitor function called the last time an edge is encountered.""" 166 pass
167 168
169 -class Preorder(Search):
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 """
174 - def __init__(self, G, queue=networkx.queues.DFS, **kwds):
175 self.forest=[] 176 super(Preorder,self).__init__(G, queue=queue)
177
178 - def start_tree(self,v):
179 """Visitor function called at the search start 180 of each connected component. 181 """ 182 self.vlist=[]
183
184 - def firstseen_vertex(self,v):
185 """Visitor function called the first time a vertex is encountered.""" 186 self.vlist.append(v)
187
188 - def end_tree(self,v):
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
222 -class Predecessor(Search):
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 """
227 - def __init__(self, G, queue=networkx.queues.DFS, **kwds):
228 self.data={} 229 super(Predecessor,self).__init__(G, queue=queue)
230 231
232 - def firstseen_vertex(self,v):
233 """Visitor function called the first time a vertex is encountered.""" 234 self.data[v]=[]
235
236 - def lastseen_edge(self,e):
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
258 -class Successor(Search):
259 """ Successor visitor 260 Builds a dict of nodes with sucessor vertex list as data. 261 """
262 - def __init__(self, G, queue=networkx.queues.DFS, **kwds):
263 self.data={} 264 super(Successor,self).__init__(G, queue=queue)
265
266 - def firstseen_vertex(self,v):
267 """Visitor function called the first time a vertex is encountered.""" 268 self.data.setdefault(v,[])
269
270 - def lastseen_edge(self,e):
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
276 -class Length(Search):
277 """ Path length visitor. 278 Returns dictionary of path lengths from vertex v. 279 Useful especially in BFS (gives shortest paths). 280 """
281 - def __init__(self, G, queue=networkx.queues.BFS, **kwds):
282 self.length={} 283 super(Length,self).__init__(G, queue=queue)
284
285 - def lastseen_edge(self,e):
286 """Visitor function called the first time an edge is encountered.""" 287 (u,v)=e 288 if u==v: 289 self.length[u]=0 # at start 290 else: 291 level=self.length[u] # target is one level higher than source 292 self.length[v]=level+1
293 294
295 -class Forest(Search):
296 """ 297 Forest visitor: build a forest of trees as a list of networkx DiGraphs. 298 """
299 - def __init__(self, G, queue=networkx.queues.DFS, **kwds):
300 self.forest=[] 301 super(Forest,self).__init__(G, queue=queue)
302
303 - def start_tree(self,v):
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
310 - def lastseen_edge(self,e):
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
316 - def end_tree(self,v):
317 """Visitor function called at the search end 318 of each connected component. 319 """ 320 self.forest.append(self.T)
321
322 -def _test_suite():
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 # directory of networkx package (relative to this) 336 nxbase=sys.path[0]+os.sep+os.pardir 337 sys.path.insert(0,nxbase) # prepend to search path 338 unittest.TextTestRunner().run(_test_suite()) 339