[76] | 1 | # |
---|
| 2 | # According to <http://www.vrplumber.com/programming/> this file |
---|
| 3 | # is licensed under a BSD-style license. We only use the section |
---|
| 4 | # originally by Tim Peters. |
---|
| 5 | # |
---|
| 6 | # TODO: The use of this code needs to be okayed by someone. |
---|
| 7 | # |
---|
| 8 | |
---|
| 9 | class RecursionError( OverflowError, ValueError ): |
---|
| 10 | '''Unable to calculate result because of recursive structure''' |
---|
| 11 | |
---|
| 12 | |
---|
| 13 | def sort(nodes, routes, noRecursion=1): |
---|
| 14 | '''Passed a list of node IDs and a list of source,dest ID routes |
---|
| 15 | attempt to create a list of stages where each sub list |
---|
| 16 | is one stage in a process. |
---|
| 17 | ''' |
---|
| 18 | children, parents = _buildChildrenLists(routes) |
---|
| 19 | # first stage is those nodes |
---|
| 20 | # having no incoming routes... |
---|
| 21 | stage = [] |
---|
| 22 | stages = [stage] |
---|
| 23 | taken = [] |
---|
| 24 | for node in nodes: |
---|
| 25 | if (not parents.get(node)): |
---|
| 26 | stage.append (node) |
---|
| 27 | if nodes and not stage: |
---|
| 28 | # there is no element which does not depend on |
---|
| 29 | # some other element!!! |
---|
| 30 | stage.append( nodes[0]) |
---|
| 31 | taken.extend( stage ) |
---|
| 32 | nodes = filter ( lambda x, l=stage: x not in l, nodes ) |
---|
| 33 | while nodes: |
---|
| 34 | previousStageChildren = [] |
---|
| 35 | nodelen = len(nodes) |
---|
| 36 | # second stage are those nodes |
---|
| 37 | # which are direct children of the first stage |
---|
| 38 | for node in stage: |
---|
| 39 | for child in children.get (node, []): |
---|
| 40 | if child not in previousStageChildren and child not in taken: |
---|
| 41 | previousStageChildren.append(child) |
---|
| 42 | elif child in taken and noRecursion: |
---|
| 43 | raise RecursionError( (child, node) ) |
---|
| 44 | # unless they are children of other direct children... |
---|
| 45 | # TODO, actually do that... |
---|
| 46 | stage = previousStageChildren |
---|
| 47 | removes = [] |
---|
| 48 | for current in stage: |
---|
| 49 | currentParents = parents.get( current, [] ) |
---|
| 50 | for parent in currentParents: |
---|
| 51 | if parent in stage and parent != current: |
---|
| 52 | # might wind up removing current... |
---|
| 53 | if not current in parents.get(parent, []): |
---|
| 54 | # is not mutually dependent... |
---|
| 55 | removes.append( current ) |
---|
| 56 | for remove in removes: |
---|
| 57 | while remove in stage: |
---|
| 58 | stage.remove( remove ) |
---|
| 59 | stages.append( stage) |
---|
| 60 | taken.extend( stage ) |
---|
| 61 | nodes = filter ( lambda x, l=stage: x not in l, nodes ) |
---|
| 62 | if nodelen == len(nodes): |
---|
| 63 | if noRecursion: |
---|
| 64 | raise RecursionError( nodes ) |
---|
| 65 | else: |
---|
| 66 | stages.append( nodes[:] ) |
---|
| 67 | nodes = [] |
---|
| 68 | return stages |
---|
| 69 | |
---|
| 70 | def _buildChildrenLists (routes): |
---|
| 71 | childrenTable = {} |
---|
| 72 | parentTable = {} |
---|
| 73 | for sourceID,destinationID in routes: |
---|
| 74 | currentChildren = childrenTable.get( sourceID, []) |
---|
| 75 | currentParents = parentTable.get( destinationID, []) |
---|
| 76 | if not destinationID in currentChildren: |
---|
| 77 | currentChildren.append ( destinationID) |
---|
| 78 | if not sourceID in currentParents: |
---|
| 79 | currentParents.append ( sourceID) |
---|
| 80 | childrenTable[sourceID] = currentChildren |
---|
| 81 | parentTable[destinationID] = currentParents |
---|
| 82 | return childrenTable, parentTable |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | def toposort (nodes, routes, noRecursion=1): |
---|
| 86 | '''Topological sort from Tim Peters, fairly efficient |
---|
| 87 | in comparison (it seems).''' |
---|
| 88 | #first calculate the recursion depth |
---|
| 89 | |
---|
| 90 | dependencies = {} |
---|
| 91 | inversedependencies = {} |
---|
| 92 | if not nodes: |
---|
| 93 | return [] |
---|
| 94 | if not routes: |
---|
| 95 | return [nodes] |
---|
| 96 | for node in nodes: |
---|
| 97 | dependencies[ node ] = (0, node) |
---|
| 98 | inversedependencies[ node ] = [] |
---|
| 99 | |
---|
| 100 | |
---|
| 101 | for depended, depends in routes: |
---|
| 102 | # is it a null rule |
---|
| 103 | try: |
---|
| 104 | newdependencylevel, object = dependencies.get ( depends, (0, depends)) |
---|
| 105 | except TypeError: |
---|
| 106 | print depends |
---|
| 107 | raise |
---|
| 108 | dependencies[ depends ] = (newdependencylevel + 1, depends) |
---|
| 109 | # "dependency (existence) of depended-on" |
---|
| 110 | newdependencylevel,object = dependencies.get ( depended, (0, depended) ) |
---|
| 111 | dependencies[ depended ] = (newdependencylevel, depended) |
---|
| 112 | # Inverse dependency set up |
---|
| 113 | dependencieslist = inversedependencies.get ( depended, []) |
---|
| 114 | dependencieslist.append (depends) |
---|
| 115 | inversedependencies[depended] = dependencieslist |
---|
| 116 | ### Now we do the actual sorting |
---|
| 117 | # The first task is to create the sortable |
---|
| 118 | # list of dependency-levels |
---|
| 119 | sortinglist = dependencies.values() |
---|
| 120 | sortinglist.sort () |
---|
| 121 | output = [] |
---|
| 122 | while sortinglist: |
---|
| 123 | deletelist = [] |
---|
| 124 | generation = [] |
---|
| 125 | output.append( generation) |
---|
| 126 | while sortinglist and sortinglist[0][0] == 0: |
---|
| 127 | number, object = sortinglist[0] |
---|
| 128 | generation.append ( object ) |
---|
| 129 | deletelist.append( object ) |
---|
| 130 | for inverse in inversedependencies.get(object, () ): |
---|
| 131 | try: |
---|
| 132 | oldcount, inverse = dependencies [ inverse] |
---|
| 133 | if oldcount > 0: |
---|
| 134 | # will be dealt with on later pass |
---|
| 135 | dependencies [ inverse] = (oldcount-1, inverse) |
---|
| 136 | else: |
---|
| 137 | # will be dealt with on this pass, |
---|
| 138 | # so needs not to be in the sorting list next time |
---|
| 139 | deletelist.append( inverse ) |
---|
| 140 | # just in case a loop comes through |
---|
| 141 | inversedependencies[object] = [] |
---|
| 142 | except KeyError: |
---|
| 143 | # dealing with a recursion-breaking run... |
---|
| 144 | pass |
---|
| 145 | del sortinglist [0] |
---|
| 146 | # if no elements could be deleted, then |
---|
| 147 | # there is something which depends upon itself |
---|
| 148 | if not deletelist: |
---|
| 149 | if noRecursion: |
---|
| 150 | raise RecursionError( sortinglist ) |
---|
| 151 | else: |
---|
| 152 | # hack so that something gets deleted... |
---|
| 153 | ## import pdb |
---|
| 154 | ## pdb.set_trace() |
---|
| 155 | dependencies[sortinglist[0][1]] = (0,sortinglist[0][1]) |
---|
| 156 | # delete the items that were dealt with |
---|
| 157 | for item in deletelist: |
---|
| 158 | try: |
---|
| 159 | del dependencies [ item ] |
---|
| 160 | except KeyError: |
---|
| 161 | pass |
---|
| 162 | # need to recreate the sortinglist |
---|
| 163 | sortinglist = dependencies.values() |
---|
| 164 | if not generation: |
---|
| 165 | output.remove( generation ) |
---|
| 166 | sortinglist.sort () |
---|
| 167 | return output |
---|
| 168 | |
---|
| 169 | |
---|
| 170 | |
---|
| 171 | |
---|
| 172 | |
---|
| 173 | if __name__ == "__main__": |
---|
| 174 | |
---|
| 175 | nodes = ['a', 'b', 'c', 'd', 'e', 'f'] |
---|
| 176 | route = [('a', 'b'), ('b', 'c'), ('b', 'd'), ('e','f')] |
---|
| 177 | |
---|
| 178 | for x in toposort( nodes, route): |
---|
| 179 | for a in x: |
---|
| 180 | print a |
---|
| 181 | |
---|
| 182 | raise SystemExit |
---|
| 183 | |
---|
| 184 | |
---|
| 185 | |
---|
| 186 | import pprint, traceback |
---|
| 187 | nodes= [ 0,1,2,3,4,5 ] |
---|
| 188 | testingValues = [ |
---|
| 189 | [ (0,1),(1,2),(2,3),(3,4),(4,5)], |
---|
| 190 | [ (0,1),(0,2),(1,2),(3,4),(4,5)], |
---|
| 191 | [ |
---|
| 192 | (0,1), |
---|
| 193 | (0,2), |
---|
| 194 | (0,2), |
---|
| 195 | (2,4), |
---|
| 196 | (2,5), |
---|
| 197 | (3,2), |
---|
| 198 | (0,3)], |
---|
| 199 | [ |
---|
| 200 | (0,1), # 3-element cycle test, no orphan nodes |
---|
| 201 | (1,2), |
---|
| 202 | (2,0), |
---|
| 203 | (2,4), |
---|
| 204 | (2,5), |
---|
| 205 | (3,2), |
---|
| 206 | (0,3)], |
---|
| 207 | [ |
---|
| 208 | (0,1), |
---|
| 209 | (1,1), |
---|
| 210 | (1,1), |
---|
| 211 | (1,4), |
---|
| 212 | (1,5), |
---|
| 213 | (1,2), |
---|
| 214 | (3,1), |
---|
| 215 | (2,1), |
---|
| 216 | (2,0)], |
---|
| 217 | [ |
---|
| 218 | (0,1), |
---|
| 219 | (1,0), |
---|
| 220 | (0,2), |
---|
| 221 | (0,3), |
---|
| 222 | ], |
---|
| 223 | [ |
---|
| 224 | (0,1), |
---|
| 225 | (1,0), |
---|
| 226 | (0,2), |
---|
| 227 | (3,1), |
---|
| 228 | ], |
---|
| 229 | ] |
---|
| 230 | print 'sort, no recursion allowed' |
---|
| 231 | for index in range(len(testingValues)): |
---|
| 232 | ## print ' %s -- %s'%( index, testingValues[index]) |
---|
| 233 | try: |
---|
| 234 | print ' ', sort( nodes, testingValues[index] ) |
---|
| 235 | except: |
---|
| 236 | print 'exception raised' |
---|
| 237 | print 'toposort, no recursion allowed' |
---|
| 238 | for index in range(len(testingValues)): |
---|
| 239 | ## print ' %s -- %s'%( index, testingValues[index]) |
---|
| 240 | try: |
---|
| 241 | print ' ', toposort( nodes, testingValues[index] ) |
---|
| 242 | except: |
---|
| 243 | print 'exception raised' |
---|
| 244 | print 'sort, recursion allowed' |
---|
| 245 | for index in range(len(testingValues)): |
---|
| 246 | ## print ' %s -- %s'%( index, testingValues[index]) |
---|
| 247 | try: |
---|
| 248 | print ' ', sort( nodes, testingValues[index],0 ) |
---|
| 249 | except: |
---|
| 250 | print 'exception raised' |
---|
| 251 | print 'toposort, recursion allowed' |
---|
| 252 | for index in range(len(testingValues)): |
---|
| 253 | ## print ' %s -- %s'%( index, testingValues[index]) |
---|
| 254 | try: |
---|
| 255 | print ' ', toposort( nodes, testingValues[index],0 ) |
---|
| 256 | except: |
---|
| 257 | print 'exception raised' |
---|
| 258 | |
---|
| 259 | |
---|
| 260 | |
---|