Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 463 - (hide annotations) (download) (as text)
Sat Jul 31 10:28:52 2010 UTC (14 years, 7 months ago) by amb
File MIME type: text/x-csrc
File size: 12095 byte(s)
Remove the assert statements that check the order of calling the functions.

1 amb 110 /***************************************
2 amb 463 $Header: /home/amb/CVS/routino/src/superx.c,v 1.41 2010-07-31 10:28:52 amb Exp $
3 amb 110
4     Super-Segment data type functions.
5 amb 151
6     Part of the Routino routing software.
7 amb 110 ******************/ /******************
8 amb 326 This file Copyright 2008-2010 Andrew M. Bishop
9 amb 110
10 amb 151 This program is free software: you can redistribute it and/or modify
11     it under the terms of the GNU Affero General Public License as published by
12     the Free Software Foundation, either version 3 of the License, or
13     (at your option) any later version.
14    
15     This program is distributed in the hope that it will be useful,
16     but WITHOUT ANY WARRANTY; without even the implied warranty of
17     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18     GNU Affero General Public License for more details.
19    
20     You should have received a copy of the GNU Affero General Public License
21     along with this program. If not, see <http://www.gnu.org/licenses/>.
22 amb 110 ***************************************/
23    
24    
25     #include <stdlib.h>
26     #include <stdio.h>
27    
28 amb 449 #include "ways.h"
29    
30 amb 110 #include "nodesx.h"
31     #include "segmentsx.h"
32     #include "waysx.h"
33     #include "superx.h"
34    
35 amb 449 #include "files.h"
36     #include "results.h"
37 amb 110
38 amb 449
39 amb 228 /* Local Functions */
40    
41     static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);
42    
43    
44 amb 110 /*++++++++++++++++++++++++++++++++++++++
45     Select the super-segments from the list of segments.
46    
47     NodesX *nodesx The nodes.
48    
49     SegmentsX *segmentsx The segments.
50    
51     WaysX *waysx The ways.
52     ++++++++++++++++++++++++++++++++++++++*/
53    
54 amb 214 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
55 amb 110 {
56 amb 214 index_t i;
57 amb 229 int nnodes=0;
58 amb 110
59 amb 275 /* Print the start message */
60    
61 amb 231 printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
62 amb 227 fflush(stdout);
63    
64 amb 275 /* Map into memory */
65    
66 amb 452 #if !SLIM
67     segmentsx->xdata=MapFile(segmentsx->filename);
68     waysx->xdata=MapFile(waysx->filename);
69     #endif
70 amb 257
71 amb 110 /* Find super-nodes */
72    
73 amb 229 for(i=0;i<nodesx->number;i++)
74 amb 110 {
75 amb 434 int difference=0;
76     index_t index1,index2;
77 amb 110
78 amb 434 index1=IndexFirstSegmentX(segmentsx,i);
79 amb 229
80 amb 434 while(index1!=NO_SEGMENT)
81 amb 110 {
82 amb 434 SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
83 amb 279 WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
84 amb 110
85 amb 434 index1=IndexNextSegmentX(segmentsx,index1,i);
86     index2=index1;
87 amb 229
88 amb 434 while(index2!=NO_SEGMENT)
89 amb 110 {
90 amb 434 SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
91 amb 279 WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
92 amb 110
93 amb 434 /* If the ways are different in any way and there is a type of traffic that can use both ... */
94 amb 110
95 amb 434 if(WaysCompare(&wayx1->way,&wayx2->way))
96     if(wayx1->way.allow & wayx2->way.allow)
97     {
98     difference=1;
99     break;
100     }
101    
102     index2=IndexNextSegmentX(segmentsx,index2,i);
103 amb 110 }
104    
105 amb 434 if(difference)
106     break;
107     }
108 amb 110
109 amb 434 /* Store the node if there is a difference in the connected ways that could affect routing. */
110 amb 110
111 amb 434 if(difference)
112     {
113     nodesx->super[i]++;
114    
115     nnodes++;
116 amb 110 }
117    
118     if(!((i+1)%10000))
119     {
120 amb 231 printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
121 amb 110 fflush(stdout);
122     }
123     }
124    
125 amb 275 /* Unmap from memory */
126    
127 amb 452 #if !SLIM
128     segmentsx->xdata=UnmapFile(segmentsx->filename);
129     waysx->xdata=UnmapFile(waysx->filename);
130     #endif
131 amb 275
132     /* Print the final message */
133    
134 amb 231 printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
135 amb 110 fflush(stdout);
136     }
137    
138    
139     /*++++++++++++++++++++++++++++++++++++++
140     Create the super-segments.
141    
142     SegmentsX *CreateSuperSegments Creates the super segments.
143    
144     NodesX *nodesx The nodes.
145    
146     SegmentsX *segmentsx The segments.
147    
148     WaysX *waysx The ways.
149    
150     int iteration The current super-node / super-segment iteration number.
151     ++++++++++++++++++++++++++++++++++++++*/
152    
153     SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
154     {
155 amb 214 index_t i;
156 amb 110 SegmentsX *supersegmentsx;
157 amb 227 int sn=0,ss=0;
158 amb 110
159 amb 275 /* Print the start message */
160    
161 amb 227 printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
162     fflush(stdout);
163    
164 amb 275 /* Map into memory */
165    
166 amb 452 #if !SLIM
167     segmentsx->xdata=MapFile(segmentsx->filename);
168     waysx->xdata=MapFile(waysx->filename);
169     #endif
170 amb 257
171 amb 275 /* Create super-segments for each super-node. */
172    
173 amb 326 supersegmentsx=NewSegmentList(0);
174 amb 110
175     for(i=0;i<nodesx->number;i++)
176     {
177 amb 249 if(nodesx->super[i]>iteration)
178 amb 110 {
179 amb 275 index_t index,first;
180 amb 110
181 amb 279 index=first=IndexFirstSegmentX(segmentsx,i);
182 amb 110
183 amb 275 while(index!=NO_SEGMENT)
184 amb 110 {
185 amb 275 SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
186 amb 279 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
187 amb 110
188     /* Check that this type of way hasn't already been routed */
189    
190 amb 256 if(index!=first)
191 amb 110 {
192 amb 275 index_t otherindex=first;
193 amb 110
194 amb 275 while(otherindex!=NO_SEGMENT && otherindex!=index)
195 amb 110 {
196 amb 275 SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
197 amb 279 WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
198 amb 110
199 amb 262 if(!WaysCompare(&otherwayx->way,&wayx->way))
200 amb 110 {
201 amb 204 wayx=NULL;
202 amb 110 break;
203     }
204    
205 amb 279 otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
206 amb 110 }
207     }
208    
209     /* Route the way and store the super-segments. */
210    
211 amb 204 if(wayx)
212 amb 110 {
213 amb 279 Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
214 amb 110 Result *result=FirstResult(results);
215    
216     while(result)
217     {
218 amb 279 if(result->node!=i && nodesx->super[result->node]>iteration)
219 amb 110 {
220 amb 262 if(wayx->way.type&Way_OneWay)
221 amb 277 {
222 amb 279 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
223     AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);
224 amb 277 }
225 amb 172 else
226 amb 279 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
227 amb 216
228 amb 229 ss++;
229 amb 110 }
230    
231     result=NextResult(results,result);
232     }
233    
234     FreeResultsList(results);
235     }
236    
237 amb 279 index=IndexNextSegmentX(segmentsx,index,i);
238 amb 110 }
239 amb 227
240     sn++;
241 amb 110
242 amb 229 if(!(sn%10000))
243     {
244     printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
245     fflush(stdout);
246     }
247 amb 110 }
248     }
249    
250 amb 275 /* Unmap from memory */
251    
252 amb 452 #if !SLIM
253     segmentsx->xdata=UnmapFile(segmentsx->filename);
254     waysx->xdata=UnmapFile(waysx->filename);
255     #endif
256 amb 275
257     /* Print the final message */
258    
259 amb 227 printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
260 amb 110 fflush(stdout);
261    
262     return(supersegmentsx);
263     }
264    
265    
266     /*++++++++++++++++++++++++++++++++++++++
267 amb 256 Merge the segments and super-segments into a new segment list.
268 amb 110
269 amb 256 SegmentsX* MergeSuperSegments Returns a new set of merged segments.
270    
271 amb 110 SegmentsX* segmentsx The set of segments to process.
272    
273     SegmentsX* supersegmentsx The set of super-segments to merge.
274     ++++++++++++++++++++++++++++++++++++++*/
275    
276 amb 256 SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
277 amb 110 {
278 amb 216 index_t i,j;
279     int m=0,a=0;
280 amb 256 SegmentsX* mergedsegmentsx;
281 amb 110
282 amb 275 /* Print the start message */
283    
284 amb 227 printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
285     fflush(stdout);
286    
287 amb 275 /* Map into memory */
288    
289 amb 452 #if !SLIM
290     segmentsx->xdata=MapFile(segmentsx->filename);
291     supersegmentsx->xdata=MapFile(supersegmentsx->filename);
292     #endif
293 amb 275
294     /* Loop through and create a new list of combined segments */
295    
296 amb 326 mergedsegmentsx=NewSegmentList(0);
297 amb 256
298 amb 216 for(i=0,j=0;i<segmentsx->number;i++)
299 amb 110 {
300 amb 256 int super=0;
301 amb 275 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
302 amb 256
303 amb 110 while(j<supersegmentsx->number)
304     {
305 amb 275 SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
306 amb 256
307     if(segmentx->node1 ==supersegmentx->node1 &&
308     segmentx->node2 ==supersegmentx->node2 &&
309     segmentx->distance==supersegmentx->distance)
310 amb 110 {
311 amb 257 m++;
312     j++;
313 amb 256 /* mark as super-segment and normal segment */
314     super=1;
315 amb 110 break;
316     }
317 amb 256 else if((segmentx->node1==supersegmentx->node1 &&
318     segmentx->node2==supersegmentx->node2) ||
319     (segmentx->node1==supersegmentx->node1 &&
320     segmentx->node2>supersegmentx->node2) ||
321     (segmentx->node1>supersegmentx->node1))
322 amb 110 {
323 amb 256 /* mark as super-segment */
324     AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
325 amb 216 a++;
326     j++;
327 amb 110 }
328     else
329 amb 257 {
330     /* mark as normal segment */
331 amb 110 break;
332 amb 257 }
333 amb 110 }
334    
335 amb 256 if(super)
336     AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
337     else
338     AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
339 amb 208
340 amb 110 if(!((i+1)%10000))
341     {
342 amb 216 printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
343 amb 110 fflush(stdout);
344     }
345     }
346    
347 amb 275 /* Unmap from memory */
348    
349 amb 452 #if !SLIM
350     segmentsx->xdata=UnmapFile(segmentsx->filename);
351     supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
352     #endif
353 amb 275
354     /* Print the final message */
355    
356 amb 216 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
357 amb 110 fflush(stdout);
358 amb 256
359     return(mergedsegmentsx);
360 amb 110 }
361    
362    
363     /*++++++++++++++++++++++++++++++++++++++
364     Find all routes from a specified node to any node in the specified list that follows a certain type of way.
365    
366     Results *FindRoutesWay Returns a set of results.
367    
368     NodesX *nodesx The set of nodes to use.
369    
370     SegmentsX *segmentsx The set of segments to use.
371    
372     WaysX *waysx The set of ways to use.
373    
374     node_t start The start node.
375    
376 amb 203 Way *match The way that the route must match.
377 amb 110
378     int iteration The current super-node / super-segment iteration number.
379     ++++++++++++++++++++++++++++++++++++++*/
380    
381 amb 228 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
382 amb 110 {
383     Results *results;
384 amb 236 Queue *queue;
385 amb 110 index_t node1,node2;
386     Result *result1,*result2;
387 amb 275 index_t index;
388 amb 204 WayX *wayx;
389 amb 110
390     /* Insert the first node into the queue */
391    
392     results=NewResultsList(8);
393    
394 amb 236 queue=NewQueueList();
395    
396 amb 110 result1=InsertResult(results,start);
397    
398 amb 166 ZeroResult(result1);
399 amb 110
400 amb 236 InsertInQueue(queue,result1);
401 amb 110
402     /* Loop across all nodes in the queue */
403    
404 amb 236 while((result1=PopFromQueue(queue)))
405 amb 110 {
406     node1=result1->node;
407    
408 amb 256 index=IndexFirstSegmentX(segmentsx,node1);
409 amb 110
410 amb 275 while(index!=NO_SEGMENT)
411 amb 110 {
412 amb 279 SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
413 amb 113 distance_t cumulative_distance;
414    
415 amb 275 if(segmentx->distance&ONEWAY_2TO1)
416     goto endloop;
417 amb 110
418 amb 275 node2=segmentx->node2;
419 amb 110
420 amb 113 if(result1->prev==node2)
421 amb 110 goto endloop;
422    
423 amb 279 wayx=LookupWayX(waysx,segmentx->way,2);
424 amb 110
425 amb 262 if(WaysCompare(&wayx->way,match))
426 amb 110 goto endloop;
427    
428 amb 256 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
429 amb 110
430     result2=FindResult(results,node2);
431    
432     if(!result2) /* New end node */
433     {
434     result2=InsertResult(results,node2);
435 amb 113 result2->prev=node1;
436 amb 176 result2->next=NO_NODE;
437 amb 172 result2->score=cumulative_distance;
438 amb 166 result2->sortby=cumulative_distance;
439 amb 110
440 amb 279 if(nodesx->super[node2]<=iteration)
441 amb 236 InsertInQueue(queue,result2);
442 amb 110 }
443 amb 172 else if(cumulative_distance<result2->score)
444 amb 110 {
445 amb 166 result2->prev=node1;
446 amb 172 result2->score=cumulative_distance;
447 amb 166 result2->sortby=cumulative_distance;
448 amb 110
449 amb 279 if(nodesx->super[node2]<=iteration)
450 amb 236 InsertInQueue(queue,result2);
451 amb 110 }
452    
453     endloop:
454    
455 amb 279 index=IndexNextSegmentX(segmentsx,index,node1);
456 amb 110 }
457     }
458    
459 amb 236 FreeQueueList(queue);
460    
461 amb 110 return(results);
462     }

Properties

Name Value
cvs:description Super-nodes and super-segments functions.