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

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