1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
29 - def __init__(self,name='no-name-for-node'):
30 self.name = name
31 self.afters = []
32 self.befores = []
33 self.zero()
34
35
36
37
38
39 self.color = 0
40
41 self.discover = 0
42 self.finalize = 0
43 self.predecessor = None
47 self.afters.append(s)
48 s.befores.append(self)
50 self.befores.append(s)
51 s.afters.append(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
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
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
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
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
111
112
114 return aa.finalize.__cmp__(bb.finalize)
115
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
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
155
156
157
158
159
160 if __name__ == '__main__':
161 _test_dfs()
162