Mercurial Repositories > eric / file comparison
comparison: Graphics/GraphicsUtilities.py
Graphics/GraphicsUtilities.py
- changeset 0
- de9c2efb9d02
- child 12
- 1d8dd9706f46
equal
deleted
inserted
replaced
| -1:000000000000 | 0:de9c2efb9d02 |
|---|---|
| 1 # -*- coding: utf-8 -*- | |
| 2 | |
| 3 # Copyright (c) 2004 - 2009 Detlev Offenbach <detlev@die-offenbachs.de> | |
| 4 # | |
| 5 | |
| 6 """ | |
| 7 Module implementing some graphical utility functions. | |
| 8 """ | |
| 9 | |
| 10 class RecursionError(OverflowError, ValueError): | |
| 11 """ | |
| 12 Unable to calculate result because of recursive structure. | |
| 13 """ | |
| 14 | |
| 15 def sort(nodes, routes, noRecursion = False): | |
| 16 """ | |
| 17 Function to sort widgets topographically. | |
| 18 | |
| 19 Passed a list of nodes and a list of source, dest routes, it attempts | |
| 20 to create a list of stages, where each sub list is one stage in a process. | |
| 21 | |
| 22 The algorithm was taken from Boa Constructor. | |
| 23 | |
| 24 @param nodes list of nodes to be sorted | |
| 25 @param routes list of routes between the nodes | |
| 26 @param noRecursion flag indicating, if recursion errors should be raised | |
| 27 @exception RecursionError a recursion error was detected | |
| 28 @return list of stages | |
| 29 """ | |
| 30 children, parents = _buildChildrenLists(routes) | |
| 31 | |
| 32 # first stage is those nodes having no incoming routes... | |
| 33 stage = [] | |
| 34 stages = [stage] | |
| 35 taken = [] | |
| 36 for node in nodes: | |
| 37 if not parents.get(node): | |
| 38 stage.append(node) | |
| 39 | |
| 40 if nodes and not stage: | |
| 41 # there is no element, which does not depend on some other element! | |
| 42 stage.append(nodes[0]) | |
| 43 | |
| 44 taken.extend(stage) | |
| 45 nodes = filter(lambda x, l = stage: x not in l, nodes) | |
| 46 while nodes: | |
| 47 previousStageChildren = [] | |
| 48 nodelen = len(nodes) | |
| 49 | |
| 50 # second stage are those nodes, which are direct children of the first stage | |
| 51 for node in stage: | |
| 52 for child in children.get(node, []): | |
| 53 if child not in previousStageChildren and child not in taken: | |
| 54 previousStageChildren.append(child) | |
| 55 elif child in taken and noRecursion: | |
| 56 raise RecursionError((child, node)) | |
| 57 | |
| 58 # unless they are children of other direct children... | |
| 59 stage = previousStageChildren | |
| 60 removes = [] | |
| 61 for current in stage: | |
| 62 currentParents = parents.get(current, []) | |
| 63 for parent in currentParents: | |
| 64 if parent in stage and parent != current: | |
| 65 # might wind up removing current | |
| 66 if not current in parents.get(parent, []): | |
| 67 # is not mutually dependant | |
| 68 removes.append(current) | |
| 69 | |
| 70 for remove in removes: | |
| 71 while remove in stage: | |
| 72 stage.remove(remove) | |
| 73 | |
| 74 stages.append(stage) | |
| 75 taken.extend(stage) | |
| 76 nodes = filter(lambda x, l = stage: x not in l, nodes) | |
| 77 if nodelen == len(nodes): | |
| 78 if noRecursion: | |
| 79 raise recursionError(nodes) | |
| 80 else: | |
| 81 stages.append(nodes[:]) | |
| 82 nodes = [] | |
| 83 | |
| 84 return stages | |
| 85 | |
| 86 def _buildChildrenLists(routes): | |
| 87 """ | |
| 88 Function to build up parent - child relationships. | |
| 89 | |
| 90 Taken from Boa Constructor. | |
| 91 | |
| 92 @param routes list of routes between nodes | |
| 93 @return dictionary of child and dictionary of parent relationships | |
| 94 """ | |
| 95 childrenTable = {} | |
| 96 parentTable = {} | |
| 97 for sourceID, destinationID in routes: | |
| 98 currentChildren = childrenTable.get(sourceID, []) | |
| 99 currentParents = parentTable.get(destinationID, []) | |
| 100 if not destinationID in currentChildren: | |
| 101 currentChildren.append(destinationID) | |
| 102 if not sourceID in currentParents: | |
| 103 currentParents.append(sourceID) | |
| 104 childrenTable[sourceID] = currentChildren | |
| 105 parentTable[destinationID] = currentParents | |
| 106 return childrenTable, parentTable |
