Bienvenue sur PostGIS.fr

Bienvenue sur PostGIS.fr , le site de la communauté des utilisateurs francophones de PostGIS.

PostGIS ajoute le support d'objets géographique à la base de données PostgreSQL. En effet, PostGIS "spatialise" le serverur PostgreSQL, ce qui permet de l'utiliser comme une base de données SIG.

Maintenu à jour, en fonction de nos disponibilités et des diverses sorties des outils que nous testons, nous vous proposons l'ensemble de nos travaux publiés en langue française.

source: trunk/workshop-routing-foss4g/web/proj4js/tools/toposort.py @ 76

Revision 76, 8.6 KB checked in by djay, 12 years ago (diff)

Ajout du répertoire web

  • Property svn:executable set to *
Line 
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
9class RecursionError( OverflowError, ValueError ):
10    '''Unable to calculate result because of recursive structure'''
11   
12
13def 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
70def _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
85def 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
173if __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   
Note: See TracBrowser for help on using the repository browser.