1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
class DiGraph:
def __init__(self):
self._nodes = set()
self._edges = []
self._nodes_to = {}
self._nodes_from = {}
def __repr__(self):
out = []
for n in self._nodes:
out.append(str(n))
for a, b in self._edges:
out.append("%s -> %s" % (a, b))
return '\n'.join(out)
def nodes(self):
return self._nodes
def edges(self):
return self._edges
def add_node(self, n):
if n in self._nodes:
return
self._nodes.add(n)
self._nodes_to[n] = []
self._nodes_from[n] = []
def add_edge(self, a, b):
if not a in self._nodes:
self.add_node(a)
if not b in self._nodes:
self.add_node(b)
self._edges.append((a, b))
self._nodes_to[a].append((a, b))
self._nodes_from[b].append((a, b))
def add_uniq_edge(self, a, b):
if (a, b) in self._edges:
return
else:
self.add_edge(a, b)
def del_edge(self, a, b):
self._edges.remove((a, b))
self._nodes_to[a].remove((a, b))
self._nodes_from[b].remove((a, b))
def predecessors_iter(self, n):
if not n in self._nodes_from:
raise StopIteration
for a, _ in self._nodes_from[n]:
yield a
def predecessors(self, n):
return [x for x in self.predecessors_iter(n)]
def successors_iter(self, n):
if not n in self._nodes_to:
raise StopIteration
for _, b in self._nodes_to[n]:
yield b
def successors(self, n):
return [x for x in self.successors_iter(n)]
def leaves_iter(self):
for n in self._nodes:
if len(self._nodes_to[n]) == 0:
yield n
def leaves(self):
return [x for x in self.leaves_iter()]
def roots_iter(self):
for n in self._nodes:
if len(self._nodes_from[n]) == 0:
yield n
def roots(self):
return [x for x in self.roots_iter()]
def find_path(self, a, b, cycles_count=0, done=None):
if done is None:
done = {}
if b in done and done[b] > cycles_count:
return [[]]
if a == b:
return [[a]]
out = []
for n in self.predecessors(b):
done_n = dict(done)
done_n[b] = done_n.get(b, 0) + 1
for path in self.find_path(a, n, cycles_count, done_n):
if path and path[0] == a:
out.append(path + [b])
return out
def node2str(self, n):
return str(n)
def edge2str(self, a, b):
return ""
def dot(self):
out = """
digraph asm_graph {
graph [
splines=polyline,
];
node [
fontsize = "16",
shape = "box"
];
"""
for n in self.nodes():
out += '%s [label="%s"];\n' % (
hash(n) & 0xFFFFFFFFFFFFFFFF, self.node2str(n))
for a, b in self.edges():
out += '%s -> %s [label="%s"]\n' % (hash(a) & 0xFFFFFFFFFFFFFFFF,
hash(b) & 0xFFFFFFFFFFFFFFFF,
self.edge2str(a, b))
out += "}"
return out
|