Routino SVN Repository Browser

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

/[routino]/trunk/src/superx.c
ViewVC logotype

Contents of /trunk/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 1098 - (show annotations) (download) (as text)
Sat Oct 20 12:52:01 2012 UTC (12 years, 5 months ago) by amb
File MIME type: text/x-csrc
File size: 14900 byte(s) 
Delete the pruned nodes before searching for super-nodes etc.
1 /***************************************
2 Super-Segment data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2012 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 <assert.h>
24 #include <stdlib.h>
25
26 #include "types.h"
27 #include "segments.h"
28 #include "ways.h"
29
30 #include "typesx.h"
31 #include "nodesx.h"
32 #include "segmentsx.h"
33 #include "waysx.h"
34 #include "superx.h"
35
36 #include "files.h"
37 #include "logging.h"
38 #include "results.h"
39
40
41 /* Local functions */
42
43 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match);
44
45
46 /*++++++++++++++++++++++++++++++++++++++
47 Select the super-nodes from the list of nodes.
48
49 NodesX *nodesx The set of nodes to use.
50
51 SegmentsX *segmentsx The set of segments to use.
52
53 WaysX *waysx The set of ways to use.
54 ++++++++++++++++++++++++++++++++++++++*/
55
56 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
57 {
58 index_t i;
59 index_t nnodes=0;
60
61 if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
62 return;
63
64 /* Print the start message */
65
66 printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
67
68 /* Allocate and set the super-node markers */
69
70 if(!nodesx->super)
71 {
72 nodesx->super=AllocBitMask(nodesx->number);
73
74 assert(nodesx->super); /* Check AllocBitMask() worked */
75
76 SetAllBits(nodesx->super,nodesx->number);
77 }
78
79 /* Map into memory / open the files */
80
81 #if !SLIM
82 nodesx->data=MapFile(nodesx->filename);
83 segmentsx->data=MapFile(segmentsx->filename);
84 waysx->data=MapFile(waysx->filename);
85 #else
86 nodesx->fd=ReOpenFile(nodesx->filename);
87 segmentsx->fd=ReOpenFile(segmentsx->filename);
88 waysx->fd=ReOpenFile(waysx->filename);
89 #endif
90
91 /* Find super-nodes */
92
93 for(i=0;i<nodesx->number;i++)
94 {
95 if(IsBitSet(nodesx->super,i))
96 {
97 int issuper=0;
98 NodeX *nodex=LookupNodeX(nodesx,i,1);
99
100 if(nodex->flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
101 issuper=1;
102 else
103 {
104 int count=0,j;
105 Way segmentway[MAX_SEG_PER_NODE];
106 int segmentweight[MAX_SEG_PER_NODE];
107 SegmentX *segmentx=FirstSegmentX(segmentsx,i,1);
108
109 while(segmentx)
110 {
111 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
112 int nsegments;
113
114 /* Segments that are loops count twice */
115
116 assert(count<MAX_SEG_PER_NODE); /* Only a limited amount of information stored. */
117
118 if(segmentx->node1==segmentx->node2)
119 segmentweight[count]=2;
120 else
121 segmentweight[count]=1;
122
123 segmentway[count]=wayx->way;
124
125 /* If the node allows less traffic types than any connecting way then it is super if it allows anything */
126
127 if((wayx->way.allow&nodex->allow)!=wayx->way.allow && nodex->allow!=Transports_None)
128 {
129 issuper=1;
130 break;
131 }
132
133 nsegments=segmentweight[count];
134
135 for(j=0;j<count;j++)
136 if(wayx->way.allow & segmentway[j].allow)
137 {
138 /* If two ways are different in any attribute and there is a type of traffic that can use both then it is super */
139
140 if(WaysCompare(&segmentway[j],&wayx->way))
141 {
142 issuper=1;
143 break;
144 }
145
146 /* If there are two other segments that can be used by the same types of traffic as this one then it is super */
147
148 nsegments+=segmentweight[j];
149 if(nsegments>2)
150 {
151 issuper=1;
152 break;
153 }
154 }
155
156 if(issuper)
157 break;
158
159 segmentx=NextSegmentX(segmentsx,segmentx,i);
160
161 count++;
162 }
163 }
164
165 /* Mark the node as super if it is. */
166
167 if(issuper)
168 nnodes++;
169 else
170 ClearBit(nodesx->super,i);
171 }
172
173 if(!((i+1)%10000))
174 printf_middle("Finding Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,i+1,nnodes);
175 }
176
177 /* Unmap from memory / close the files */
178
179 #if !SLIM
180 nodesx->data=UnmapFile(nodesx->filename);
181 segmentsx->data=UnmapFile(segmentsx->filename);
182 waysx->data=UnmapFile(waysx->filename);
183 #else
184 nodesx->fd=CloseFile(nodesx->fd);
185 segmentsx->fd=CloseFile(segmentsx->fd);
186 waysx->fd=CloseFile(waysx->fd);
187 #endif
188
189 /* Print the final message */
190
191 printf_last("Found Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,nodesx->number,nnodes);
192 }
193
194
195 /*++++++++++++++++++++++++++++++++++++++
196 Create the super-segments from the existing segments.
197
198 SegmentsX *CreateSuperSegments Returns the new super segments.
199
200 NodesX *nodesx The set of nodes to use.
201
202 SegmentsX *segmentsx The set of segments to use.
203
204 WaysX *waysx The set of ways to use.
205 ++++++++++++++++++++++++++++++++++++++*/
206
207 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
208 {
209 index_t i;
210 SegmentsX *supersegmentsx;
211 index_t sn=0,ss=0;
212
213 supersegmentsx=NewSegmentList(0);
214
215 if(segmentsx->number==0 || waysx->number==0)
216 return(supersegmentsx);
217
218 /* Print the start message */
219
220 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
221
222 /* Map into memory / open the files */
223
224 #if !SLIM
225 nodesx->data=MapFile(nodesx->filename);
226 segmentsx->data=MapFile(segmentsx->filename);
227 waysx->data=MapFile(waysx->filename);
228 #else
229 nodesx->fd=ReOpenFile(nodesx->filename);
230 segmentsx->fd=ReOpenFile(segmentsx->filename);
231 waysx->fd=ReOpenFile(waysx->filename);
232 #endif
233
234 /* Create super-segments for each super-node. */
235
236 for(i=0;i<nodesx->number;i++)
237 {
238 if(IsBitSet(nodesx->super,i))
239 {
240 SegmentX *segmentx;
241 int count=0,match;
242 Way prevway[MAX_SEG_PER_NODE];
243
244 segmentx=FirstSegmentX(segmentsx,i,1);
245
246 while(segmentx)
247 {
248 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
249
250 /* Check that this type of way hasn't already been routed */
251
252 match=0;
253
254 if(count>0)
255 {
256 int j;
257
258 for(j=0;j<count;j++)
259 if(!WaysCompare(&prevway[j],&wayx->way))
260 {
261 match=1;
262 break;
263 }
264 }
265
266 assert(count<MAX_SEG_PER_NODE); /* Only a limited amount of history stored. */
267
268 prevway[count++]=wayx->way;
269
270 /* Route the way and store the super-segments. */
271
272 if(!match)
273 {
274 Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way);
275 Result *result=FirstResult(results);
276
277 while(result)
278 {
279 if(IsBitSet(nodesx->super,result->node) && result->segment!=NO_SEGMENT)
280 {
281 if(wayx->way.type&Way_OneWay && result->node!=i)
282 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
283 else
284 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
285
286 ss++;
287 }
288
289 result=NextResult(results,result);
290 }
291
292 FreeResultsList(results);
293 }
294
295 segmentx=NextSegmentX(segmentsx,segmentx,i);
296 }
297
298 sn++;
299
300 if(!(sn%10000))
301 printf_middle("Creating Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
302 }
303 }
304
305 /* Unmap from memory / close the files */
306
307 #if !SLIM
308 nodesx->data=UnmapFile(nodesx->filename);
309 segmentsx->data=UnmapFile(segmentsx->filename);
310 waysx->data=UnmapFile(waysx->filename);
311 #else
312 nodesx->fd=CloseFile(nodesx->fd);
313 segmentsx->fd=CloseFile(segmentsx->fd);
314 waysx->fd=CloseFile(waysx->fd);
315 #endif
316
317 /* Print the final message */
318
319 printf_last("Created Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
320
321 return(supersegmentsx);
322 }
323
324
325 /*++++++++++++++++++++++++++++++++++++++
326 Merge the segments and super-segments into a new segment list.
327
328 SegmentsX *MergeSuperSegments Returns a new set of merged segments.
329
330 SegmentsX *segmentsx The set of segments to use.
331
332 SegmentsX *supersegmentsx The set of super-segments to use.
333 ++++++++++++++++++++++++++++++++++++++*/
334
335 SegmentsX *MergeSuperSegments(SegmentsX *segmentsx,SegmentsX *supersegmentsx)
336 {
337 index_t i,j;
338 index_t merged=0,added=0;
339 SegmentsX *mergedsegmentsx;
340
341 mergedsegmentsx=NewSegmentList(0);
342
343 if(segmentsx->number==0)
344 return(mergedsegmentsx);
345
346 /* Print the start message */
347
348 printf_first("Merging Segments: Segments=0 Super=0 Merged=0 Added=0");
349
350 /* Map into memory / open the files */
351
352 #if !SLIM
353 segmentsx->data=MapFile(segmentsx->filename);
354 if(supersegmentsx->number>0)
355 supersegmentsx->data=MapFile(supersegmentsx->filename);
356 #else
357 segmentsx->fd=ReOpenFile(segmentsx->filename);
358 if(supersegmentsx->number>0)
359 supersegmentsx->fd=ReOpenFile(supersegmentsx->filename);
360 #endif
361
362 /* Loop through and create a new list of combined segments */
363
364 for(i=0,j=0;i<segmentsx->number;i++)
365 {
366 int super=0;
367 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
368
369 while(j<supersegmentsx->number)
370 {
371 SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
372
373 if(segmentx->node1 ==supersegmentx->node1 &&
374 segmentx->node2 ==supersegmentx->node2 &&
375 segmentx->distance==supersegmentx->distance)
376 {
377 merged++;
378 j++;
379 /* mark as super-segment and normal segment */
380 super=1;
381 break;
382 }
383 else if((segmentx->node1==supersegmentx->node1 &&
384 segmentx->node2==supersegmentx->node2) ||
385 (segmentx->node1==supersegmentx->node1 &&
386 segmentx->node2>supersegmentx->node2) ||
387 (segmentx->node1>supersegmentx->node1))
388 {
389 /* mark as super-segment */
390 AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
391 added++;
392 j++;
393 }
394 else
395 {
396 /* mark as normal segment */
397 break;
398 }
399 }
400
401 if(super)
402 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
403 else
404 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
405
406 if(!((i+1)%10000))
407 printf_middle("Merging Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,i+1,j,merged,added);
408 }
409
410 /* Unmap from memory / close the files */
411
412 #if !SLIM
413 segmentsx->data=UnmapFile(segmentsx->filename);
414 if(supersegmentsx->number>0)
415 supersegmentsx->data=UnmapFile(supersegmentsx->filename);
416 #else
417 segmentsx->fd=CloseFile(segmentsx->fd);
418 if(supersegmentsx->number>0)
419 supersegmentsx->fd=CloseFile(supersegmentsx->fd);
420 #endif
421
422 /* Print the final message */
423
424 printf_last("Merged Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,segmentsx->number,supersegmentsx->number,merged,added);
425
426 return(mergedsegmentsx);
427 }
428
429
430 /*++++++++++++++++++++++++++++++++++++++
431 Find all routes from a specified super-node to any other super-node that follows a certain type of way.
432
433 Results *FindRoutesWay Returns a set of results.
434
435 NodesX *nodesx The set of nodes to use.
436
437 SegmentsX *segmentsx The set of segments to use.
438
439 WaysX *waysx The set of ways to use.
440
441 node_t start The start node.
442
443 Way *match A template for the type of way that the route must follow.
444 ++++++++++++++++++++++++++++++++++++++*/
445
446 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match)
447 {
448 Results *results;
449 Queue *queue;
450 Result *result1,*result2;
451 WayX *wayx;
452
453 /* Insert the first node into the queue */
454
455 results=NewResultsList(64);
456
457 queue=NewQueueList();
458
459 result1=InsertResult(results,start,NO_SEGMENT);
460
461 InsertInQueue(queue,result1);
462
463 /* Loop across all nodes in the queue */
464
465 while((result1=PopFromQueue(queue)))
466 {
467 index_t node1;
468 SegmentX *segmentx;
469
470 node1=result1->node;
471
472 segmentx=FirstSegmentX(segmentsx,node1,2); /* position 1 is already used */
473
474 while(segmentx)
475 {
476 NodeX *node2x;
477 index_t node2,seg2;
478 distance_t cumulative_distance;
479
480 /* must not be one-way against the direction of travel */
481 if(IsOnewayTo(segmentx,node1))
482 goto endloop;
483
484 seg2=IndexSegmentX(segmentsx,segmentx);
485
486 /* must not be a u-turn */
487 if(result1->segment==seg2)
488 goto endloop;
489
490 wayx=LookupWayX(waysx,segmentx->way,2); /* position 1 is already used */
491
492 /* must be the right type of way */
493 if(WaysCompare(&wayx->way,match))
494 goto endloop;
495
496 node2=OtherNode(segmentx,node1);
497
498 node2x=LookupNodeX(nodesx,node2,2); /* position 1 is already used */
499
500 /* Don't route beyond a node with no access */
501 if(node2x->allow==Transports_None)
502 goto endloop;
503
504 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
505
506 result2=FindResult(results,node2,seg2);
507
508 if(!result2) /* New end node */
509 {
510 result2=InsertResult(results,node2,seg2);
511 result2->prev=result1;
512 result2->score=cumulative_distance;
513 result2->sortby=cumulative_distance;
514
515 /* don't route beyond a super-node. */
516 if(!IsBitSet(nodesx->super,node2))
517 InsertInQueue(queue,result2);
518 }
519 else if(cumulative_distance<result2->score)
520 {
521 result2->prev=result1;
522 result2->score=cumulative_distance;
523 result2->sortby=cumulative_distance;
524
525 /* don't route beyond a super-node. */
526 if(!IsBitSet(nodesx->super,node2))
527 InsertInQueue(queue,result2);
528 }
529
530 endloop:
531
532 segmentx=NextSegmentX(segmentsx,segmentx,node1);
533 }
534 }
535
536 FreeQueueList(queue);
537
538 return(results);
539 }

Properties

Name Value
cvs:description Super-nodes and super-segments functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root