Module treeutil
[hide private]
[frames] | no frames]

Source Code for Module treeutil

  1  """ 
  2  treeutil 
  3  ======== 
  4  Contains all sort of utilities to search and manipulate nested lists as trees. 
  5   
  6  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  7  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
  8  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
  9  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 10  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 11  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 12  THE SOFTWARE. 
 13   
 14  @author: by Mehdi Khoury 
 15  @version: 1.20 
 16  @copyright: (c) 2009 Mehdi Khoury under the mit license 
 17  http://www.opensource.org/licenses/mit-license.html 
 18  """ 
 19   
 20  from collections import deque 
 21  import psyco 
 22  import pickle 
 23  import copy 
 24  import array 
 25  import string 
 26  #Define exceptions 
 27   
 28  # Exceptions related to tree manipulation 
29 -class TreeUtilError(Exception): pass
30 -class NestedHeadNode(TreeUtilError): pass
31 -class NotAList(TreeUtilError): pass
32 -class EmptyList(TreeUtilError): pass
33 -class EmptyDict(TreeUtilError): pass
34 35 # Exceptions related to operators and calculation of fitness
36 -class CalculationError(Exception): pass
37 -class WrongValues(CalculationError): pass
38 39 psyco.profile() 40
41 -def listGetRootNode(myTree):
42 """ 43 Function: listGetRootNode 44 ========================== 45 get the root node of a nested list 46 47 @param myTree: the nested list representing a tree 48 49 @return: the root node of a nested list 50 51 """ 52 if type(myTree)is not list: 53 raise NotAList, "Tree should be a (nested) list." 54 if not myTree: 55 raise EmptyList, "Tree should not be empty." 56 if type(myTree[0])is list: 57 raise NestedHeadNode, "Head node should not be a list." 58 exit 59 return myTree[0]
60 61
62 -def BFS_Search(myTree):
63 """ 64 65 Function: BFS_Search 66 ===================== 67 Traverse the nodes of a tree in breadth-first order. 68 69 @param myTree: the nested list representing a tree 70 71 @return: an generator for a list of nodes in Breath First Search order 72 73 """ 74 75 queue = deque(myTree) 76 while queue: 77 node = queue.popleft() 78 if type(node) is list: 79 yield node[0] 80 for elem in node[1:]: 81 queue.append(elem) 82 else: yield node
83 84 85
86 -def walk(seq):
87 """ 88 Function: walk 89 =============== 90 Walk over a sequence of items, printing each one in turn, and 91 recursively walking over sub-sequences. 92 93 @param seq: the nested list representing a tree 94 95 """ 96 print seq 97 if isinstance(seq, list): 98 for item in seq: 99 walk(item)
100 101
102 -def getChildrenNodes2(lst,depth):
103 """ 104 105 Function: getChildrenNodes2 106 ============================ 107 Get the children nodes in a nested list for a specific depth 108 109 @param lst: the nested list representing a tree 110 @param depth: the nested list representing a tree 111 112 @return: a flat list of children nodes for a specific depth 113 114 """ 115 result=[] 116 if depth>0: 117 for elem in getChildrenNodes2(lst,depth-1): 118 if isinstance(elem, list): 119 result.extend(elem[1:]) 120 else: 121 result =lst 122 return result
123 124 125 126 127 128 129
130 -def PostOrder_Search(myTree):
131 """ 132 Function: PostOrder_Search 133 =========================== 134 Traverse the nodes of a tree by getting the leafs 135 first and the branches after. Finishes with the root. 136 e.g. [1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,13,14]] 137 gives : [7, 6, 5, 4, 3, 2, 11, 10, 9, 8, 14, 13, 12, 1] 138 139 @param myTree: the nested list representing a tree 140 141 @return: a flat list of nodes in PostOrder Search 142 143 """ 144 queue = deque(myTree) 145 # place the root at the end of the traversal 146 node = queue.popleft() 147 queue.append(node) 148 # add the rest in required order 149 while queue: 150 node = queue.popleft() 151 if type(node) is list: 152 for elem in node: 153 queue.appendleft(elem) 154 else: yield node
155 156 157 #
158 -def DFS_Search(seq):
159 """ 160 Function: DFS_Search 161 ===================== 162 a recursive generator that flatten a nested list 163 gives a list of all nodes in the tree in Depth First Search order 164 165 @param seq: the nested list representing a tree 166 167 @return: a flat list of nodes in Depth First Search order 168 169 """ 170 for x in seq: 171 if type(x) is list: 172 for y in DFS_Search(x): 173 yield y 174 else: 175 yield x
176 177
178 -def BranchNodes_Search(myTree):
179 """ 180 Function: BranchNodes_Search 181 ============================= 182 a generator to iterate through branch nodes only in BFS order. 183 184 @param myTree: the nested list representing a tree 185 186 @return: a flat list of branch nodes nodes in BFS order. 187 188 """ 189 queue = deque(myTree) 190 node = queue.popleft() 191 yield node 192 while queue: 193 node = queue.popleft() 194 if type(node) is list: 195 yield node[0] 196 for elem in node: 197 queue.append(elem)
198 199
200 -def LeafNodes_Search(myTree):
201 """ 202 Function: LeafNodes_Search 203 =========================== 204 a generator to iterate through leaf nodes 205 only in right-to-left BFS preorder. 206 207 @param myTree: the nested list representing a tree 208 209 @return: a flat list of leaf nodes nodes in BFS preorder. 210 211 """ 212 queue = deque(myTree) 213 # get rid of root node 214 queue.popleft() 215 while queue: 216 node = queue.popleft() 217 if type(node) is list: 218 for elem in node[1:]: 219 queue.appendleft(elem) 220 else: yield node
221 222 223 224 225 226
227 -def isNested(myList):
228 """ 229 Function: isNested 230 =================== 231 Check if a list is nested 232 233 @param myList: the nested list representing a tree 234 235 @return: 1 if nested , 0 if not. 236 237 """ 238 for elem in myList: 239 if type(elem) is list: 240 return 1 241 else: 242 return 0
243 244 245 246 247 248
249 -def list_getTail(myList):
250 """ 251 Function: list_getTail 252 ======================= 253 get the tail of a 'node' 254 e.g. [1,2]->[2] 255 e.g. [1,[2,4],5]->[2,5] 256 257 @param myList: the nested list representing a tree 258 259 @return: the tail of the list 260 261 """ 262 value =[] 263 if type(myList) is list: 264 for elem in myList[1:]: 265 if type(elem) is not list : 266 value.append(elem) 267 else: 268 value.append(elem[0]) 269 return value
270 271
272 -def getSubLists(myList):
273 """ 274 Function: getSubLists 275 ====================== 276 get a list of all sub lists in a nested list 277 278 @param myList: the nested list representing a tree 279 280 @return: a list of all sub lists in a nested list 281 282 """ 283 temp = myList 284 result=[] 285 while temp: 286 elem = temp.pop(0) 287 if type(elem) is list: 288 result.append(elem) 289 temp.extend(elem) 290 return result
291 292
293 -def nestedListToDict(myList):
294 """ 295 Function: nestedListToDict 296 =========================== 297 get a dictionnary from a nested list 298 299 @param myList: the nested list representing a tree 300 301 @return: a dictionary 302 303 """ 304 if not myList: 305 raise EmptyList, "Tree should not be empty." 306 exit 307 result={} 308 result[myList[0]]=list_getTail(myList) 309 temp = getSubLists(myList) 310 for elem in temp: result[elem[0]]=list_getTail(elem) 311 return result
312 313
314 -def dictFindRootNode(myDict):
315 """ 316 Function: dictFindRootNode 317 =========================== 318 find the root node of a tree 319 in a dictionary (assumption is that 320 a root node is a key never found in 321 any of all values) 322 323 @param myDict: the dictionary representing a tree 324 325 @return: a dictionary 326 327 """ 328 result=None 329 temp=[] 330 for elem in myDict.itervalues(): 331 temp.extend(elem) 332 for key in myDict.iterkeys(): 333 if key not in temp: 334 result = key 335 return result 336 return result
337 338
339 -def dictGetRootList(myDict):
340 """ 341 Function: dictGetRootList 342 ========================== 343 get the list coresponding to the root node 344 345 @param myDict: the dictionary representing a tree 346 347 @return: the list coresponding to the root node 348 349 """ 350 result=[] 351 root = dictFindRootNode(myDict) 352 atom = [root] 353 atom.extend(myDict[root]) 354 result.extend(atom) 355 return result
356 357 358
359 -def dictToSubLists(myDict):
360 """ 361 Function: dictToSubLists 362 ========================= 363 get a list version of the dictionary 364 365 @param myDict: the dictionary representing a tree 366 367 @return: the list corresponding to the dictionary 368 369 """ 370 result =[] 371 for k, v in myDict.iteritems(): 372 atom=[k] 373 atom.extend(v) 374 result.append(atom) 375 return result
376 377
378 -def nestedInsert(list1,list2):
379 """ 380 Function: nestedInsert 381 ======================= 382 nest a list inside another one if the 383 first one has elements which are head of 384 lists or sub lists in list 2 385 386 @param list1: flat list 1 387 @param list1: flat list 2 388 389 @return: resulting nested list 390 391 """ 392 temp = list1 393 for i in xrange(1,len(temp)): 394 for elem in list2: 395 if temp[i]== elem[0]: 396 temp[i]=nestedInsert(elem,list2) 397 return temp
398 399
400 -def dictToNestedList(myDict):
401 """ 402 Function: dictToNestedList 403 =========================== 404 finally, transform the dictionary 405 into a nested list 406 407 @param myDict: the dictionary representing a tree 408 409 @return: the nested list corresponding to the dictionary 410 411 """ 412 if not myDict: 413 raise EmptyDict, "Dictionary should not be empty." 414 exit 415 root = dictGetRootList(myDict) 416 sublists = dictToSubLists(myDict) 417 sublists.remove(root) 418 return nestedInsert(root,sublists)
419