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