]> dev.renevier.net Git - syp.git/blob - openlayers/tools/toposort.py
small code cleanup (indentation, missing copyrights, etc)
[syp.git] / openlayers / tools / toposort.py
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