Routino SVN Repository Browser

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

ViewVC logotype

Contents of /trunk/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 603 - (show annotations) (download) (as text)
Sat Jan 15 22:22:57 2011 UTC (14 years, 2 months ago) by amb
File MIME type: text/x-csrc
File size: 13246 byte(s)
Change the results structure to contain next segment and rename elements to
clarify prev/next node and prev/next segment.

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

Properties

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