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 647 - (show annotations) (download) (as text)
Sat Feb 26 19:45:56 2011 UTC (14 years ago) by amb
File MIME type: text/x-csrc
File size: 13151 byte(s)
Use the OtherNode and IsOneWay* macros when routing.

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

Properties

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