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

Source Code for Module networkx.search

  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  #    Copyright (C) 2004-2007 by  
 11  #    Aric Hagberg <hagberg@lanl.gov> 
 12  #    Dan Schult <dschult@colgate.edu> 
 13  #    Pieter Swart <swart@lanl.gov> 
 14  #    Distributed under the terms of the GNU Lesser General Public License 
 15  #    http://www.gnu.org/copyleft/lesser.html 
 16   
 17  import networkx 
18 -def dfs_preorder(G,source=None,reverse_graph=False):
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() # process entire graph 26 else: 27 nlist=[source] # only process component with 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={} # nodes seen 38 pre=[] # list of nodes in a DFS preorder 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() # process entire graph 59 else: 60 nlist=[source] # only process component with 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={} # nodes seen 71 post=[] # list of nodes in a DFS postorder 72 for source in nlist: 73 if source in seen: continue 74 queue=[source] # use as LIFO queue 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
98 -def dfs_predecessor(G,source=None,reverse_graph=False):
99 """ 100 Return predecessors of depth-first-search with root at source. 101 """ 102 if source is None: 103 nlist=G.nodes() # process entire graph 104 else: 105 nlist=[source] # only process component with 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={} # nodes seen 116 pred={} 117 for source in nlist: 118 if source in seen: continue 119 queue=[source] # use as LIFO queue 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] # Each node has at most one predecessor 130 done=0 131 break 132 if done==1: 133 queue.pop() 134 return pred
135 136
137 -def dfs_successor(G,source=None,reverse_graph=False):
138 """ 139 Return succesors of depth-first-search with root at source. 140 """ 141 142 if source is None: 143 nlist=G.nodes() # process entire graph 144 else: 145 nlist=[source] # only process component with 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={} # nodes seen 156 succ={} 157 for source in nlist: 158 if source in seen: continue 159 queue=[source] # use as LIFO queue 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
177 -def _test_suite():
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 # directory of networkx package (relative to this) 191 nxbase=sys.path[0]+os.sep+os.pardir 192 sys.path.insert(0,nxbase) # prepend to search path 193 unittest.TextTestRunner().run(_test_suite()) 194