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 1168 - (show annotations) (download) (as text)
Wed Nov 21 09:20:57 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 15304 byte(s)
Revert r1164 - some super-segments are longer than 65535 metres even if no
individual segment is.

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

Properties

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