← Back to branch summary

~dongpo-deng/sahana-eden/test

« back to all changes in this revision

Viewing changes to static/scripts/gis/proj4js/tools/toposort.py

  • Committer: Deng Dongpo
  • Date: 2010-08-01 09:29:44 UTC
  • Revision ID: dongpo@dhcp-21193.iis.sinica.edu.tw-20100801092944-8t9obt4xtl7otesb
initial

Show diffs side-by-side

added added

removed removed

Lines of Context:
static/scripts/gis/proj4js/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