Package dsc_suite :: Package tools :: Module graphtheory
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.tools.graphtheory

  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 
10 11 # graph expecting source (target are all nodes without children) 12 -def longest_path(graph, weights):
13 # wird auch in slicing-tree verwendet, bei aenderungen angleichen 14 # noch uneffizient, da mehrfachens untersuchen der knoten 15 # moeglich. ist zur zeit aber noch notwendig, da es redundante 16 # kanten gibt. 17 # besser vorher red. kanten entfernen 18 # algorithmuss gibt graph ohne transitive kanten zurueck (parent) 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
35 ##### TERNARY TREES ############################################### 36 -class TernaryTrees(object):
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 # pick node randomly, with color 91 x = randrange(len(T)) 92 color = randrange(3) 93 y = randrange(len(T)+1) # if y == len(T) -> x-tra node 94 if y == len(T): 95 y = 'extra node' 96 # indices of new nodes 97 p = len(T) 98 a = len(T) + 1 99 b = len(T) + 2 100 # update T with new p, x and a 101 T.append([None, None, None, T[x][TernaryTrees.PARENT], True, T[x][TernaryTrees.DEPTH]]) 102 # insert a depending on chosen color 103 T[p][color] = a 104 # insert old x as cyclic right brother of a 105 T[p][(color+1)%3] = x 106 # modify x node 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 # append node a 114 T.append([None, None, None, p, False, T[p][TernaryTrees.DEPTH]+1]) 115 # test if p is a descendant of y 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 # take care for leaf labeled b 142 if not p_desc_of_y: 143 # in this case y cannot be root 144 if y == 'extra node': 145 # y == b 146 T.append([None, None, None, p, False, T[p][TernaryTrees.DEPTH]+1]) 147 # y(b) is cyclic left brother of a 148 T[p][(color-1)%3] = b 149 else: 150 # b substitutes y 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 # y is cyclic left brother of a 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 # rotate b -> f(a) -> y -> cl(a) 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 # p substitutes y 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 # y is cyclic left brother of a 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
176 topology = [] 177 dfs_order = [] 178 TernaryTrees.__transform_panholzer_to_topology_recursive(T, root, 179 topology, 180 dfs_order) 181 for i in range(len(topology)): 182 for j in range(4): # parent, left, middle, right 183 if topology[i][j] in dfs_order: 184 topology[i][j] = dfs_order.index(topology[i][j]) 185 else: 186 topology[i][j] = None 187 return topology
188 189 @staticmethod
190 - def __transform_panholzer_to_topology_recursive(T, node, topology, dfs_order, parent=None):
191 if T[node][TernaryTrees.INTERNAL] == True: 192 dfs_order.append(node) 193 topology.append([parent, 194 T[node][TernaryTrees.LEFT], 195 T[node][TernaryTrees.MIDDLE], 196 T[node][TernaryTrees.RIGHT]]) 197 TernaryTrees.__transform_panholzer_to_topology_recursive(T, 198 T[node][TernaryTrees.LEFT], 199 topology, 200 dfs_order, 201 node) 202 TernaryTrees.__transform_panholzer_to_topology_recursive(T, 203 T[node][TernaryTrees.MIDDLE], 204 topology, 205 dfs_order, 206 node) 207 TernaryTrees.__transform_panholzer_to_topology_recursive(T, 208 T[node][TernaryTrees.RIGHT], 209 topology, 210 dfs_order, 211 node)
212
213 214 ##### BINARY TREES ################################################ 215 -class BinaryTrees(object):
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
227 - def get_num_binary_trees(n):
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
238 - def get_binary_tree(n, i):
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
271 - def generate_relations(topology):
272 """ Generate topology relations from a given pre-order representation.""" 273 open_right = [0] 274 # which inner node misses it's right child 275 result = [[None, 1], [0]] 276 # result list: [[parent, left child, right child], ...] 277 i = 1 278 while i < len(topology): 279 if topology[i] == '1': 280 # inner node 281 if len(result) == i + 1: 282 # parent is already in result list 283 result[i].append(i+1) 284 # next node is left child 285 else: 286 # obtain parent from open_right list 287 parent = open_right.pop() 288 result[parent].append(i) 289 result.append([parent, i+1]) 290 # append parent for left node 291 result.append([i]) 292 open_right.append(i) 293 else: 294 # leaf 295 if len(result) == i + 1: 296 # parent is already in result list 297 result[i].append(None) 298 result[i].append(None) 299 # leaves don't have children 300 else: 301 # obtain parent from open_right list 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
309 - def generate_inversion_table(n, result, i=0, d=0, s=[]):
310 if d < n: 311 for j in range(i+2): 312 BinaryTrees.generate_inversion_table(n, result, j, d + 1, list(s)+[j]) 313 else: 314 result.append(s)
315 316 @staticmethod
317 - def get_binary_trees(n):
318 result = [] 319 i = 0 320 i_max = BinaryTrees.get_num_binary_trees(n) 321 while i < i_max: 322 result.append(BinaryTrees.get_binary_tree(n, i)) 323 i += 1 324 return result
325