import repository from arizona
[raven.git] / apps / digdug / transition.py
1 INVERSE_CHAR = "~"
2 GLOB_CHAR = "*"
3
4 def inverse_state(x):
5     if x.startswith(INVERSE_CHAR):
6         return x[1:]
7     else:
8         return INVERSE_CHAR + x
9
10 # http://www.bitformation.com/art/python_toposort.html
11 def top_sort(items, partial_order):
12     def add_node(graph, node):
13         if not graph.has_key(node):
14             graph[node] = [0]
15
16     def add_arc(graph, fromnode, tonode):
17         graph[fromnode].append(tonode)
18         graph[tonode][0] = graph[tonode][0] + 1
19
20     graph = {}
21     for v in items:
22         add_node(graph, v)
23     for (a,b) in partial_order:
24         add_arc(graph, a, b)
25
26     roots = [node for (node,nodeinfo) in graph.items() if nodeinfo[0] == 0]
27
28     sorted = []
29     while len(roots) != 0:
30         root = roots.pop()
31         sorted.append(root)
32         for child in graph[root][1:]:
33             graph[child][0] = graph[child][0] - 1
34             if graph[child][0] == 0:
35                 roots.append(child)
36         del graph[root]
37     if len(graph.items()) != 0:
38         return None
39     return sorted
40
41 def is_edge(x,y):
42     pre_x = x[0]
43     post_x = x[1]
44     pre_y = y[0]
45     post_y = y[1]
46
47     # assume that pre_x != pre_y
48
49     if (pre_x == "*"):
50         return True
51
52     return (pre_y in post_x) #or (inverse_state(pre_y) in post_x)
53
54 def sort_transitions(dict):
55     items = []
56     item_names = []
57     partial_order = []
58
59     for key in dict:
60         x = (key, dict[key])
61
62         for y in items:
63             if is_edge(x,y):
64                 partial_order.append( (x[0],y[0]) )
65             if is_edge(y,x):
66                 partial_order.append( (y[0],x[0]) )
67
68         items.append(x)
69         item_names.append(x[0])
70
71     sorted_names = top_sort(item_names, partial_order)
72
73     if sorted_names == None:
74         # cycle
75         return None
76
77     l = []
78     for name in sorted_names:
79         l.append( (name, dict[name]) )
80
81     return l
82
83