Package mbuild :: Module dfs
[frames] | no frames]

Source Code for Module mbuild.dfs

  1  #!/usr/bin/env python 
  2  # FILE: dfs.py 
  3  # AUTHOR: Mark Charney <mark.charney@intel.com> 
  4  #BEGIN_LEGAL 
  5  # 
  6  #Copyright (c) 2016 Intel Corporation 
  7  # 
  8  #  Licensed under the Apache License, Version 2.0 (the "License"); 
  9  #  you may not use this file except in compliance with the License. 
 10  #  You may obtain a copy of the License at 
 11  # 
 12  #      http://www.apache.org/licenses/LICENSE-2.0 
 13  # 
 14  #  Unless required by applicable law or agreed to in writing, software 
 15  #  distributed under the License is distributed on an "AS IS" BASIS, 
 16  #  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 17  #  See the License for the specific language governing permissions and 
 18  #  limitations under the License. 
 19  #   
 20  #END_LEGAL 
 21   
 22  """This file provides a node_t type and a dfs() routine that prints out 
 23  cycles found in a graph represented as a list of node_t objects. 
 24  """ 
 25   
 26  _dfs_verbose = False 
 27   
28 -class node_t(object):
29 - def __init__(self,name='no-name-for-node'):
30 self.name = name 31 self.afters = [] 32 self.befores = [] 33 self.zero() 34 35 # The colors are: 36 # 0 = white (unvisited), 37 # 1=grey (discovered, visiting), 38 # 2=black (finalized) 39 self.color = 0 40 41 self.discover = 0 42 self.finalize = 0 43 self.predecessor = None
44 - def zero(self):
45 self.color = 0
46 - def add_successor(self, s):
47 self.afters.append(s) 48 s.befores.append(self)
49 - def add_ancestor(self, s):
50 self.befores.append(s) 51 s.afters.append(self)
52 - def __str__(self):
53 s = [] 54 s.append("TARGET: %s\n\t" % self.name) 55 s.append("discovered %d finalized %d\n\t" % (self.discover, self.finalize)) 56 s.extend(map(lambda(x): "\t\n%s" % x.name, self.afters)) 57 return ''.join(s)
58 59 60
61 -def _print_cycle(last_visit, grey_loop_closer):
62 pad = '' 63 p = last_visit 64 while 1: 65 print pad, p.name 66 if p == grey_loop_closer: 67 break 68 p = p.predecessor 69 pad += ' '
70
71 -def _visit(n):
72 global _dfs_time 73 n.color = 1 74 n.discover = _dfs_time 75 if _dfs_verbose: 76 print "visiting %s" % str(n) 77 _dfs_time += 1 78 retval = False 79 for a in n.afters: 80 if a.color == 0: 81 a.predecessor = n 82 retval |= _visit(a) 83 elif a.color == 1: 84 # a back-edge 85 print "cycle" 86 _print_cycle(n,a) 87 retval = True 88 n.color = 2 89 n.finalize = _dfs_time 90 _dfs_time += 1 91 return retval
92
93 -def dfs(nodes):
94 """Depth first search a list of node_t objects. Print out cycles. 95 @rtype: bool 96 @return: True if cycles were detected. 97 """ 98 global _dfs_time 99 _dfs_time = 0 100 for t in nodes: 101 t.zero() 102 cycle = False 103 for n in nodes: 104 if n.color == 0: 105 cycle |= _visit(n) 106 return cycle
107 108 ####################################################### 109 110 # stuff for a strongly connected components algorithm -- currently 111 # unused. 112
113 -def _node_cmp(aa,bb):
114 return aa.finalize.__cmp__(bb.finalize)
115
116 -def _visit_transpose(n):
117 global _dfs_time 118 n.color = 1 119 if _dfs_verbose: 120 print "visiting %s" % str(n) 121 for a in n.befores: 122 if a.color == 0: 123 _visit_transpose(a) 124 n.color = 2
125 126
127 -def dfs_transpose(nodes):
128 global _dfs_time 129 _dfs_time = 0 130 for t in nodes: 131 t.zero() 132 nodes.sort(cmp=_node_cmp) 133 for n in nodes: 134 if n.color == 0: 135 _visit_transpose(n) 136 if _dfs_verbose: 137 print "===="
138 139 #################################################### 140
141 -def _test_dfs():
142 node1 = node_t('1') 143 node2 = node_t('2') 144 node3 = node_t('3') 145 node4 = node_t('4') 146 node1.add_successor(node2) 147 node1.add_successor(node3) 148 node3.add_successor(node4) 149 node4.add_successor(node1) 150 151 nodes = [ node1, node2, node3, node4 ] 152 cycle = dfs(nodes) 153 if cycle: 154 print "CYCLE DETECTED"
155 #print "VISIT TRANSPOSE" 156 #dfs_transpose(nodes) 157 158 # print "NODES\n", "\n".join(map(str,nodes)) 159 160 if __name__ == '__main__': 161 _test_dfs() 162