Source Code for Module networkx.dag

  1  # -*- coding: utf-8 -*- 
  2  """ 
  3  Algorithms for directed acyclic graphs (DAGs). 
  4  """ 
  5  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 
  6  ___revision__ = "" 
  7  #    Copyright (C) 2006 by  
  8  #    Aric Hagberg <hagberg@lanl.gov> 
  9  #    Dan Schult <dschult@colgate.edu> 
 10  #    Pieter Swart <swart@lanl.gov> 
 11  #    Distributed under the terms of the GNU Lesser General Public License 
 12  #    http://www.gnu.org/copyleft/lesser.html 
 13  import networkx 
 14   
 15 -def is_directed_acyclic_graph(G): 
 16      """Return True if the graph G is a directed acyclic graph (DAG). 
 17   
 18      Otherwise return False. 
 19       
 20      """ 
 21      if topological_sort(G) is None: 
 22          return False 
 23      else: 
 24          return True 
 25   
 26 -def topological_sort(G): 
 27      """ 
 28      Return a list of nodes of the digraph G in topological sort order. 
 29   
 30      A topological sort is a nonunique permutation of the nodes 
 31      such that an edge from u to v implies that u appears before v in the 
 32      topological sort order. 
 33   
 34      If G is not a directed acyclic graph no topological sort exists 
 35      and the Python keyword None is returned. 
 36   
 37      This algorithm is based on a description and proof at 
 38      http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm 
 39   
 40      See also is_directed_acyclic_graph() 
 41       
 42      """ 
 43      # nonrecursive version 
 44   
 45      seen={} 
 46      order_explored=[] # provide order and  
 47      explored={}       # fast search without more general priorityDictionary 
 48                        
 49      if not G.is_directed():  G.successors_iter=G.neighbors_iter 
 50   
 51      for v in G.nodes_iter():     # process all vertices in G 
 52          if v in explored: continue 
 53   
 54          fringe=[v]   # nodes yet to look at 
 55          while fringe: 
 56              w=fringe[-1]  # depth first search 
 57              if w in explored: # already looked down this branch 
 58                  fringe.pop() 
 59                  continue 
 60              seen[w]=1     # mark as seen 
 61              # Check successors for cycles and for new nodes 
 62              new_nodes=[] 
 63              for n in G.successors_iter(w):   
 64                  if n not in explored: 
 65                      if n in seen: return #CYCLE !! 
 66                      new_nodes.append(n) 
 67              if new_nodes:   # Add new_nodes to fringe 
 68                  fringe.extend(new_nodes) 
 69              else:           # No new nodes so w is fully explored 
 70                  explored[w]=1 
 71                  order_explored.insert(0,w) # reverse order explored 
 72                  fringe.pop()    # done considering this node 
 73      return order_explored 
 74   
 75 -def topological_sort_recursive(G): 
 76      """ 
 77      Return a list of nodes of the digraph G in topological sort order. 
 78   
 79      This is a recursive version of topological sort. 
 80       
 81      """ 
 82      # function for recursive dfs 
 83      def _dfs(G,seen,explored,v): 
 84          seen[v]=1 
 85          for w in G.successors(v): 
 86              if w not in seen:  
 87                  if not _dfs(G,seen,explored,w): 
 88                      return 
 89              elif w in seen and w not in explored: 
 90                  # cycle Found--- no topological sort 
 91                  return False 
 92          explored.insert(0,v) # inverse order of when explored  
 93          return v 
 94   
 95      seen={} 
 96      explored=[] 
 97   
 98      if not G.is_directed():  G.successors=G.neighbors 
 99       
100      for v in G.nodes_iter():  # process all nodes 
101          if v not in explored: 
102              if not _dfs(G,seen,explored,v):  
103                  return  
104      return explored 
105   
106   
107 -def _test_suite(): 
108      import doctest 
109      suite = doctest.DocFileSuite('tests/dag.txt',package='networkx') 
110      return suite 
111   
112   
113  if __name__ == "__main__": 
114      import os 
115      import sys 
116      import unittest 
117      if sys.version_info[:2] < (2, 4): 
118          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
119          sys.exit(-1) 
120      # directory of networkx package (relative to this) 
121      nxbase=sys.path[0]+os.sep+os.pardir 
122      sys.path.insert(0,nxbase) # prepend to search path 
123      unittest.TextTestRunner().run(_test_suite()) 
124