1 """module graphtheory
2
3 Helper module implementing several graph theory structures and algorithms.
4 """
5
6 from Queue import Queue
7 from dsc_suite.tools.math import catalan_number
8 from scipy import comb
9 from random import randint, randrange
13
14
15
16
17
18
19 distance = dict()
20 parent = dict()
21 for b in graph.keys():
22 distance[b] = 0
23 parent[b] = ''
24 q = Queue()
25 q.put('Source')
26 while not q.empty():
27 u = q.get()
28 for v in graph[u]:
29 if distance[u]+weights[v] > distance[v]:
30 distance[v] = distance[u]+weights[v]
31 parent[v] = u
32 q.put(v)
33 return distance, parent
34
37 """ basic TT functionality
38
39 This class implements basic ternary functionality, such as
40 ternary tree numbering and generation.
41
42 """
43 LEFT = 0
44 MIDDLE = 1
45 RIGHT = 2
46 PARENT = 3
47 INTERNAL = 4
48 DEPTH = 5
49
50 @staticmethod
52 """ Calculate number of possible ternary trees.
53
54 n ... number of nodes
55
56 Binomial(3n,n)/(2n+1)
57 (enumerates ternary trees and also non-crossing trees)
58 http://www.research.att.com/~njas/sequences/A001764
59
60 """
61 return int(round(comb(3*n, n) / (2*n + 1)))
62
63 @staticmethod
65 """ Generate a random ternary tree. Evenly distributed.
66
67 N ... number of (internal) nodes
68
69 Generate an evenly distributed random ternary tree.
70 Approach taken from [Panholzer2002]. Returned format
71 is a complete ternary tree with internal and external
72 nodes. To get a random ternary tree only the internal
73 nodes are to use.
74
75 Returns ternary tree in a list format where each entry
76 represents a node. The index of the root node is also returned.
77 T = [[LEFT, MIDDLE, RIGHT, PARENT, INTERNAL, DEPTH], ...]
78
79 returns T, root
80
81 NOTE: Depth information was intended to speed up the descendant
82 test. The depth assignment is erroneous. Some parent-child nodes
83 have the same depth. -> Don't use until resolved.
84 """
85 n = 0
86 root = 0
87 T = [[None, None, None, None, False, 0]]
88 while not n == N:
89 n += 1
90
91 x = randrange(len(T))
92 color = randrange(3)
93 y = randrange(len(T)+1)
94 if y == len(T):
95 y = 'extra node'
96
97 p = len(T)
98 a = len(T) + 1
99 b = len(T) + 2
100
101 T.append([None, None, None, T[x][TernaryTrees.PARENT], True, T[x][TernaryTrees.DEPTH]])
102
103 T[p][color] = a
104
105 T[p][(color+1)%3] = x
106
107 if not T[x][TernaryTrees.PARENT] == None:
108 T[T[x][TernaryTrees.PARENT]][T[T[x][TernaryTrees.PARENT]].index(x)] = p
109 else:
110 root = p
111 T[x][TernaryTrees.PARENT] = p
112 T[x][TernaryTrees.DEPTH] = T[p][TernaryTrees.DEPTH] + 1
113
114 T.append([None, None, None, p, False, T[p][TernaryTrees.DEPTH]+1])
115
116 """
117 TIEFENZUWEISUNG IST NOCH FEHLERHAFT, ALSO NICHT VERWENDEN BIS
118 FEHLER GEFUNDEN WIRD. SYMPTOM: ELTERNKNOTEN HABEN MANCHMAL DIE
119 SELBE TIEFE WIE IHRE KINDKNOTEN (BZW. ANDERSRUM).
120 p_desc_of_y = False
121 if not y == 'extra node' and T[p][DEPTH] > T[y][DEPTH]:
122 parent = T[p][PARENT]
123 while T[parent][DEPTH] > T[y][DEPTH]: #TODO check depth
124 #print T[parent][DEPTH], T[y][DEPTH]
125 if T[T[parent][PARENT]][DEPTH] >= T[parent][DEPTH]:
126 print p, y
127 for i in range(len(T)):
128 print i, T[i]
129 return None
130 parent = T[parent][PARENT]
131 if parent == y:
132 p_desc_of_y = True
133 """
134 p_desc_of_y = False
135 parent = T[p][TernaryTrees.PARENT]
136 while not parent == None:
137 if parent == y:
138 p_desc_of_y = True
139 break
140 parent = T[parent][TernaryTrees.PARENT]
141
142 if not p_desc_of_y:
143
144 if y == 'extra node':
145
146 T.append([None, None, None, p, False, T[p][TernaryTrees.DEPTH]+1])
147
148 T[p][(color-1)%3] = b
149 else:
150
151 T.append([None, None, None, T[y][TernaryTrees.PARENT], False, T[y][TernaryTrees.DEPTH]])
152 T[T[y][TernaryTrees.PARENT]][T[T[y][TernaryTrees.PARENT]].index(y)] = b
153
154 T[p][(color-1)%3] = y
155 T[y][TernaryTrees.PARENT] = p
156 T[y][TernaryTrees.DEPTH] = T[p][TernaryTrees.DEPTH]+1
157 else:
158
159 T.append([None, None, None, T[p][TernaryTrees.PARENT], False, T[p][TernaryTrees.DEPTH]])
160 T[T[p][TernaryTrees.PARENT]][T[T[p][TernaryTrees.PARENT]].index(p)] = b
161
162 T[p][TernaryTrees.PARENT] = T[y][TernaryTrees.PARENT]
163 T[p][TernaryTrees.DEPTH] = T[y][TernaryTrees.DEPTH]
164 if not T[y][TernaryTrees.PARENT] == None:
165 T[T[y][TernaryTrees.PARENT]][T[T[y][TernaryTrees.PARENT]].index(y)] = p
166 else:
167 root = p
168
169 T[p][(color-1)%3] = y
170 T[y][TernaryTrees.PARENT] = p
171 T[y][TernaryTrees.DEPTH] = T[p][TernaryTrees.DEPTH]+1
172 return T, root
173
174 @staticmethod
188
189 @staticmethod
212
216 """class BinaryTree() - basic BT functionality
217
218 This class implements basic binary tree functionality, such as
219 binary tree generation and numbering.
220
221 Most methods are static (class) methods. Basically, this class
222 is used to encapsulated conjoined functions.
223
224 """
225
226 @staticmethod
228 """ Calculate number of possible binary trees.
229
230 n -> number of inner nodes
231
232 Return catalan number of n.
233
234 """
235 return catalan_number(n)
236
237 @staticmethod
239 """Generate number i binary tree as a binary in order sequence.
240
241 n -> number of inner nodes
242 i -> index of binary tree, 0 <= i < catalan_number(n)
243
244 From all possible binary trees with n inner nodes the i'tht tree
245 is generated as an pre-order binary sequence. Algorithm by Ruskey1978.
246
247 """
248 N = i + 1
249 temp = ''
250 q = n
251 m = p = c = 1
252 while p < n:
253 p = p + 1
254 c = ((4 * p - 2) * c) / (p + 1)
255 while q > 0:
256 cc = ((q + 1) * (q - p) * c) / ((q + p) * (q - p + 1))
257 if N <= cc:
258 q = q - 1
259 c = cc
260 temp += '0'
261 m = m + 1
262 else:
263 p = p - 1
264 c = c - cc
265 N = N - cc
266 temp += '1'
267 m = m + 1
268 return temp + '0'
269
270 @staticmethod
272 """ Generate topology relations from a given pre-order representation."""
273 open_right = [0]
274
275 result = [[None, 1], [0]]
276
277 i = 1
278 while i < len(topology):
279 if topology[i] == '1':
280
281 if len(result) == i + 1:
282
283 result[i].append(i+1)
284
285 else:
286
287 parent = open_right.pop()
288 result[parent].append(i)
289 result.append([parent, i+1])
290
291 result.append([i])
292 open_right.append(i)
293 else:
294
295 if len(result) == i + 1:
296
297 result[i].append(None)
298 result[i].append(None)
299
300 else:
301
302 parent = open_right.pop()
303 result[parent].append(i)
304 result.append([parent, None, None])
305 i += 1
306 return result
307
308 @staticmethod
315
316 @staticmethod
325