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 544 - (hide annotations) (download) (as text)
Sat Dec 18 19:17:26 2010 UTC (14 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 12507 byte(s)
Duplicate the IndexFirstSegmentX() and IndexNextSegmentX() functions to create
two distinct one for use at different times.

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

Properties

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