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