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

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