101 lines
2.0 KiB
Python
101 lines
2.0 KiB
Python
NODES = ["in","p1","p2","p3","p4","p5","p6","p7","p8","p9","p10","p11","p12","p13","out"]
|
|
|
|
SUCCESSORS = {
|
|
"in": {"p1"},
|
|
"p1": {"p2"},
|
|
"p2": {"p3"},
|
|
"p3": {"p4"},
|
|
"p4": {"p5"},
|
|
"p5": {"p6"},
|
|
"p6": {"p7","out"},
|
|
"p7": {"p8"},
|
|
"p8": {"p9"},
|
|
"p9": {"p10","p11"},
|
|
"p10": {"p12"},
|
|
"p11": {"p12"},
|
|
"p12": {"p13"},
|
|
"p13": {"p6"},
|
|
"out": set()
|
|
}
|
|
|
|
USE = {
|
|
"in": set(),
|
|
"p1": set(),
|
|
"p2": set(),
|
|
"p3": set(),
|
|
"p4": {"i","j"},
|
|
"p5": set(),
|
|
"p6": {"s"},
|
|
"p7": {"s"},
|
|
"p8": {"i","j","f"},
|
|
"p9": {"c"},
|
|
"p10": {"j","c"},
|
|
"p11": {"j","c"},
|
|
"p12": {"j","f"},
|
|
"p13": {"s"},
|
|
"out": set()
|
|
}
|
|
|
|
DEF = {
|
|
"in": set(),
|
|
"p1": {"s"},
|
|
"p2": {"i"},
|
|
"p3": {"j"},
|
|
"p4": {"t"},
|
|
"p5": {"f"},
|
|
"p6": set(),
|
|
"p7": {"a"},
|
|
"p8": {"c"},
|
|
"p9": set(),
|
|
"p10": {"j"},
|
|
"p11": {"i"},
|
|
"p12": {"i"},
|
|
"p13": {"s"},
|
|
"out": set()
|
|
}
|
|
|
|
def pretty_print(iteration, nodes, IN, OUT):
|
|
w_v = 6
|
|
w_set = 32
|
|
|
|
def fmt(s):
|
|
return "{" + ", ".join(sorted(s)) + "}"
|
|
|
|
print(f"\nIteration {iteration}")
|
|
print("=" * (w_v + 2*w_set + 7))
|
|
print(f"{'v':<{w_v}} | {'IN':<{w_set}} | {'OUT':<{w_set}}")
|
|
print("-" * (w_v + 2*w_set + 7))
|
|
|
|
for v in nodes:
|
|
print(
|
|
f"{v:<{w_v}} | "
|
|
f"{fmt(IN[v]):<{w_set}} | "
|
|
f"{fmt(OUT[v]):<{w_set}}"
|
|
)
|
|
|
|
print("=" * (w_v + 2*w_set + 7))
|
|
|
|
i = 0
|
|
IN = {v: set() for v in NODES}
|
|
OUT = {v: set() for v in NODES}
|
|
|
|
for v in NODES:
|
|
IN[v] = USE[v]
|
|
pretty_print(i, NODES, IN, OUT)
|
|
|
|
changed = True
|
|
while changed:
|
|
changed = False
|
|
i += 1
|
|
|
|
for v in NODES:
|
|
old_in = IN[v].copy()
|
|
old_out = OUT[v].copy()
|
|
|
|
OUT[v] = set().union(*(IN[s] for s in SUCCESSORS[v]))
|
|
IN[v] = USE[v] | (OUT[v] - DEF[v])
|
|
|
|
if IN[v] != old_in or OUT[v] != old_out:
|
|
changed = True
|
|
|
|
pretty_print(i, NODES, IN, OUT) |