networkx.search

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

Source Code for Module networkx.search_class