1 /***************************************
2 Routing optimiser.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2017, 2019 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 "types.h"
24 #include "nodes.h"
25 #include "segments.h"
26 #include "ways.h"
27 #include "relations.h"
28
29 #include "logging.h"
30 #include "functions.h"
31 #include "fakes.h"
32 #include "results.h"
33
34 #ifdef LIBROUTINO
35
36 #include "routino.h"
37
38 /*+ The function to be called to report on the routing progress. +*/
39 extern Routino_ProgressFunc progress_func;
40
41 /*+ The current state of the routing progress. +*/
42 extern double progress_value;
43
44 /*+ Set when the progress callback returns false in the routing function. +*/
45 extern int progress_abort;
46
47 #endif
48
49
50 /*+ To help when debugging +*/
51 #define DEBUG 0
52
53
54 /* Global variables */
55
56 /*+ The option not to print any progress information. +*/
57 extern int option_quiet;
58
59 /*+ The option to calculate the quickest route insted of the shortest. +*/
60 extern int option_quickest;
61
62
63 /* Local functions */
64
65 static Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node);
66 static Results *FindMiddleRoute(Nodes *supernodes,Segments *supersegments,Ways *superways,Relations *relations,Profile *profile,Results *begin,Results *end);
67 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t finish_node,index_t finish_segment);
68 static Results *FindSuperRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t finish_node);
69 static Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node);
70 static Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t finish_node);
71 static Results *CombineRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,Results *begin,Results *middle,Results *end);
72
73 static void FixForwardRoute(Results *results,Result *finish_result);
74
75 #if DEBUG
76 static void print_debug_route(Nodes *nodes,Segments *segments,Results *results,Result *first,int indent,int direction);
77 #endif
78
79
80 /*++++++++++++++++++++++++++++++++++++++
81 Find a complete route from a specified node to another node.
82
83 Results *CalculateRoute Returns a set of results.
84
85 Nodes *nodes The set of nodes to use.
86
87 Segments *segments The set of segments to use.
88
89 Ways *ways The set of ways to use.
90
91 Relations *relations The set of relations to use.
92
93 Profile *profile The profile containing the transport type, speeds and allowed highways.
94
95 index_t start_node The start node.
96
97 index_t prev_segment The previous segment before the start node.
98
99 index_t finish_node The finish node.
100
101 int start_waypoint The starting waypoint.
102
103 int finish_waypoint The finish waypoint.
104 ++++++++++++++++++++++++++++++++++++++*/
105
CalculateRoute(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t start_node,index_t prev_segment,index_t finish_node,int start_waypoint,int finish_waypoint)106 Results *CalculateRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,
107 index_t start_node,index_t prev_segment,index_t finish_node,
108 int start_waypoint,int finish_waypoint)
109 {
110 Results *complete=NULL;
111
112 /* A special case if the first and last nodes are the same */
113
114 if(start_node==finish_node)
115 {
116 index_t fake_segment;
117 Result *result1,*result2;
118
119 complete=NewResultsList(8);
120
121 if(prev_segment==NO_SEGMENT)
122 {
123 double lat,lon;
124 distance_t distmin,dist1,dist2;
125 index_t node1,node2;
126
127 GetLatLong(nodes,start_node,NULL,&lat,&lon);
128
129 prev_segment=FindClosestSegment(nodes,segments,ways,lat,lon,1,profile,&distmin,&node1,&node2,&dist1,&dist2);
130 }
131
132 if(IsFakeSegment(prev_segment))
133 prev_segment=IndexRealSegment(prev_segment);
134
135 fake_segment=CreateFakeNullSegment(segments,start_node,prev_segment,finish_waypoint);
136
137 result1=InsertResult(complete,start_node,prev_segment);
138 result2=InsertResult(complete,finish_node,fake_segment);
139
140 result1->next=result2;
141
142 complete->start_node=start_node;
143 complete->prev_segment=prev_segment;
144
145 complete->finish_node=finish_node;
146 complete->last_segment=fake_segment;
147 }
148 else
149 {
150 Results *begin;
151
152 /* Calculate the beginning of the route */
153
154 begin=FindStartRoutes(nodes,segments,ways,relations,profile,start_node,prev_segment,finish_node);
155
156 if(begin)
157 {
158 /* Check if the end of the route was reached */
159
160 if(begin->finish_node!=NO_NODE)
161 complete=begin;
162 }
163 else
164 {
165 if(prev_segment!=NO_SEGMENT)
166 {
167 /* Try again but allow a U-turn at the start waypoint -
168 this solves the problem of facing a dead-end that contains no super-nodes. */
169
170 prev_segment=NO_SEGMENT;
171
172 begin=FindStartRoutes(nodes,segments,ways,relations,profile,start_node,prev_segment,finish_node);
173 }
174
175 if(begin)
176 {
177 /* Check if the end of the route was reached */
178
179 if(begin->finish_node!=NO_NODE)
180 complete=begin;
181 }
182 else
183 {
184 #ifndef LIBROUTINO
185 fprintf(stderr,"Error: Cannot find initial section of route compatible with profile.\n");
186 #endif
187 return(NULL);
188 }
189 }
190
191 /* Calculate the rest of the route */
192
193 if(!complete)
194 {
195 Results *middle,*end;
196
197 /* Calculate the end of the route */
198
199 end=FindFinishRoutes(nodes,segments,ways,relations,profile,finish_node);
200
201 if(!end)
202 {
203 #ifndef LIBROUTINO
204 fprintf(stderr,"Error: Cannot find final section of route compatible with profile.\n");
205 #endif
206 return(NULL);
207 }
208
209 /* Calculate the middle of the route */
210
211 middle=FindMiddleRoute(nodes,segments,ways,relations,profile,begin,end);
212
213 if(!middle && prev_segment!=NO_SEGMENT)
214 {
215 /* Try again but allow a U-turn at the start waypoint -
216 this solves the problem of facing a dead-end that contains some super-nodes. */
217
218 FreeResultsList(begin);
219
220 begin=FindStartRoutes(nodes,segments,ways,relations,profile,start_node,NO_SEGMENT,finish_node);
221
222 if(begin)
223 middle=FindMiddleRoute(nodes,segments,ways,relations,profile,begin,end);
224 }
225
226 if(!middle)
227 {
228 #ifndef LIBROUTINO
229 fprintf(stderr,"Error: Cannot find super-route compatible with profile.\n");
230 #endif
231 return(NULL);
232 }
233
234 complete=CombineRoutes(nodes,segments,ways,relations,profile,begin,middle,end);
235
236 if(!complete)
237 {
238 #ifndef LIBROUTINO
239 fprintf(stderr,"Error: Cannot create combined route following super-route.\n");
240 #endif
241 return(NULL);
242 }
243
244 FreeResultsList(begin);
245 FreeResultsList(middle);
246 FreeResultsList(end);
247 }
248 }
249
250 complete->start_waypoint=start_waypoint;
251 complete->finish_waypoint=finish_waypoint;
252
253 #if DEBUG
254 printf("The final route is:\n");
255
256 print_debug_route(nodes,segments,complete,NULL,2,+1);
257 #endif
258
259 return(complete);
260 }
261
262
263 /*++++++++++++++++++++++++++++++++++++++
264 Find the optimum route between two nodes not passing through a super-node.
265
266 Results *FindNormalRoute Returns a set of results.
267
268 Nodes *nodes The set of nodes to use.
269
270 Segments *segments The set of segments to use.
271
272 Ways *ways The set of ways to use.
273
274 Relations *relations The set of relations to use.
275
276 Profile *profile The profile containing the transport type, speeds and allowed highways.
277
278 index_t start_node The start node.
279
280 index_t prev_segment The previous segment before the start node.
281
282 index_t finish_node The finish node.
283 ++++++++++++++++++++++++++++++++++++++*/
284
FindNormalRoute(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t start_node,index_t prev_segment,index_t finish_node)285 static Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node)
286 {
287 Results *results;
288 Queue *queue;
289 score_t total_score;
290 double finish_lat,finish_lon;
291 Result *start_result,*finish_result;
292 Result *result1,*result2;
293 int force_uturn=0;
294
295 #if DEBUG
296 printf(" FindNormalRoute(...,start_node=%"Pindex_t" prev_segment=%"Pindex_t" finish_node=%"Pindex_t")\n",start_node,prev_segment,finish_node);
297 #endif
298
299 /* Set up the finish conditions */
300
301 total_score=INF_SCORE;
302 finish_result=NULL;
303
304 if(IsFakeNode(finish_node))
305 GetFakeLatLong(finish_node,&finish_lat,&finish_lon);
306 else
307 GetLatLong(nodes,finish_node,NULL,&finish_lat,&finish_lon);
308
309 /* Create the list of results and insert the first node into the queue */
310
311 results=NewResultsList(8);
312 queue=NewQueueList(8);
313
314 start_result=InsertResult(results,start_node,prev_segment);
315
316 InsertInQueue(queue,start_result,0);
317
318 /* Check for barrier at start waypoint - must perform U-turn */
319
320 if(prev_segment!=NO_SEGMENT && !IsFakeNode(start_node))
321 {
322 Node *startp=LookupNode(nodes,start_node,1);
323
324 if(!(startp->allow&profile->transports))
325 force_uturn=1;
326 }
327
328 /* Loop across all nodes in the queue */
329
330 while((result1=PopFromQueue(queue)))
331 {
332 Node *node1p=NULL;
333 Segment *segment2p;
334 index_t node1,seg1,seg1r;
335 index_t turnrelation=NO_RELATION;
336
337 /* score must be better than current best score */
338 if(result1->score>=total_score)
339 continue;
340
341 node1=result1->node;
342 seg1=result1->segment;
343
344 if(IsFakeSegment(seg1))
345 seg1r=IndexRealSegment(seg1);
346 else
347 seg1r=seg1;
348
349 if(!IsFakeNode(node1))
350 node1p=LookupNode(nodes,node1,1);
351
352 /* lookup if a turn restriction applies */
353 if(profile->turns && node1p && IsTurnRestrictedNode(node1p))
354 turnrelation=FindFirstTurnRelation2(relations,node1,seg1r);
355
356 /* Loop across all segments */
357
358 if(IsFakeNode(node1))
359 segment2p=FirstFakeSegment(node1);
360 else
361 segment2p=FirstSegment(segments,node1p,1);
362
363 while(segment2p)
364 {
365 Node *node2p=NULL;
366 Way *way2p;
367 index_t node2,seg2,seg2r;
368 score_t segment_pref,segment_score,cumulative_score;
369 int i;
370
371 node2=OtherNode(segment2p,node1); /* need this here because we use node2 at the end of the loop */
372
373 /* must be a normal segment */
374 if(!IsNormalSegment(segment2p))
375 goto endloop;
376
377 /* must obey one-way restrictions (unless profile allows) */
378 if(profile->oneway && IsOnewayTo(segment2p,node1))
379 {
380 if(profile->transports!=Transports_Bicycle)
381 goto endloop;
382
383 way2p=LookupWay(ways,segment2p->way,1);
384
385 if(!(way2p->type&Highway_CycleBothWays))
386 goto endloop;
387 }
388
389 if(IsFakeNode(node1) || IsFakeNode(node2))
390 {
391 seg2 =IndexFakeSegment(segment2p);
392 seg2r=IndexRealSegment(seg2);
393 }
394 else
395 {
396 seg2 =IndexSegment(segments,segment2p);
397 seg2r=seg2;
398 }
399
400 /* must perform U-turn in special cases */
401 if(force_uturn && node1==start_node)
402 {
403 if(seg2r!=result1->segment)
404 goto endloop;
405 }
406 else
407 /* must not perform U-turn (unless profile allows) */
408 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2))))
409 goto endloop;
410
411 /* must obey turn relations */
412 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1r,seg2r,profile->transports))
413 goto endloop;
414
415 if(!IsFakeNode(node2))
416 node2p=LookupNode(nodes,node2,2);
417
418 /* must not pass over super-node */
419 if(node2!=finish_node && node2p && IsSuperNode(node2p))
420 goto endloop;
421
422 way2p=LookupWay(ways,segment2p->way,1);
423
424 /* mode of transport must be allowed on the highway */
425 if(!(way2p->allow&profile->transports))
426 goto endloop;
427
428 /* must obey weight restriction (if exists) */
429 if(way2p->weight && way2p->weight<profile->weight)
430 goto endloop;
431
432 /* must obey height/width/length restriction (if exist) */
433 if((way2p->height && way2p->height<profile->height) ||
434 (way2p->width && way2p->width <profile->width ) ||
435 (way2p->length && way2p->length<profile->length))
436 goto endloop;
437
438 segment_pref=profile->highway[HIGHWAY(way2p->type)];
439
440 /* highway preferences must allow this highway */
441 if(segment_pref==0)
442 goto endloop;
443
444 for(i=1;i<Property_Count;i++)
445 if(ways->file.properties & PROPERTIES(i))
446 {
447 if(way2p->props & PROPERTIES(i))
448 segment_pref*=profile->props_yes[i];
449 else
450 segment_pref*=profile->props_no[i];
451 }
452
453 /* profile preferences must allow this highway */
454 if(segment_pref==0)
455 goto endloop;
456
457 /* mode of transport must be allowed through node2 unless it is the final node */
458 if(node2p && node2!=finish_node && !(node2p->allow&profile->transports))
459 goto endloop;
460
461 /* calculate the score for the segment and cumulative */
462 if(option_quickest==0)
463 segment_score=(score_t)DISTANCE(segment2p->distance)/segment_pref;
464 else
465 segment_score=(score_t)Duration(segment2p,way2p,profile)/segment_pref;
466
467 cumulative_score=result1->score+segment_score;
468
469 /* score must be better than current best score */
470 if(cumulative_score>=total_score)
471 goto endloop;
472
473 /* find whether the node/segment combination already exists */
474 result2=FindResult(results,node2,seg2);
475
476 if(!result2) /* New end node/segment combination */
477 {
478 result2=InsertResult(results,node2,seg2);
479 result2->prev=result1;
480 result2->score=cumulative_score;
481 }
482 else if(cumulative_score<result2->score) /* New score for end node/segment combination is better */
483 {
484 result2->prev=result1;
485 result2->score=cumulative_score;
486 result2->segment=seg2;
487 }
488 else
489 goto endloop;
490
491 if(node2==finish_node)
492 {
493 total_score=cumulative_score;
494 finish_result=result2;
495 }
496 else
497 InsertInQueue(queue,result2,result2->score);
498
499 endloop:
500
501 if(IsFakeNode(node1))
502 segment2p=NextFakeSegment(segment2p,node1);
503 else if(IsFakeNode(node2))
504 segment2p=NULL; /* cannot call NextSegment() with a fake segment */
505 else
506 {
507 segment2p=NextSegment(segments,segment2p,node1);
508
509 if(!segment2p && IsFakeNode(finish_node))
510 segment2p=ExtraFakeSegment(node1,finish_node);
511 }
512 }
513 }
514
515 FreeQueueList(queue);
516
517 /* Check it worked */
518
519 if(!finish_result)
520 {
521 #if DEBUG
522 printf(" Failed\n");
523 #endif
524
525 FreeResultsList(results);
526 return(NULL);
527 }
528
529 /* Turn the route round and fill in the start and finish information */
530
531 FixForwardRoute(results,finish_result);
532
533 results->start_node =start_result->node;
534 results->prev_segment=start_result->segment;
535
536 results->finish_node =finish_result->node;
537 results->last_segment=finish_result->segment;
538
539 #if DEBUG
540 printf(" -------- normal route (between super-nodes)\n");
541
542 print_debug_route(nodes,segments,results,NULL,6,+1);
543 #endif
544
545 return(results);
546 }
547
548
549 /*++++++++++++++++++++++++++++++++++++++
550 Find the optimum route between two nodes where the start and end are a set of pre/post-routed super-nodes.
551
552 Results *FindMiddleRoute Returns a set of results.
553
554 Nodes *nodes The set of nodes to use.
555
556 Segments *segments The set of segments to use.
557
558 Ways *ways The set of ways to use.
559
560 Relations *relations The set of relations to use.
561
562 Profile *profile The profile containing the transport type, speeds and allowed highways.
563
564 Results *begin The initial portion of the route.
565
566 Results *end The final portion of the route.
567 ++++++++++++++++++++++++++++++++++++++*/
568
FindMiddleRoute(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,Results * begin,Results * end)569 static Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,Results *begin,Results *end)
570 {
571 Results *results;
572 Queue *fwd_queue,*rev_queue;
573 Result *start_result,*finish_result;
574 score_t total_score;
575 double start_lat,start_lon;
576 double finish_lat,finish_lon;
577 Result *result1,*result2;
578 int force_uturn=0;
579 #ifdef LIBROUTINO
580 int loopcount=0;
581 #endif
582
583 #if DEBUG
584 printf(" FindMiddleRoute(...,[begin has %d nodes],[end has %d nodes])\n",begin->number,end->number);
585 #endif
586
587 #if !DEBUG && !defined(LIBROUTINO)
588 if(!option_quiet)
589 printf_first("Finding Middle Route: Super-Nodes checked = 0");
590 #endif
591
592 /* Set up the finish conditions */
593
594 total_score=INF_SCORE;
595 start_result=NULL;
596 finish_result=NULL;
597
598 if(IsFakeNode(begin->start_node))
599 GetFakeLatLong(begin->start_node,&start_lat,&start_lon);
600 else
601 GetLatLong(nodes,begin->start_node,NULL,&start_lat,&start_lon);
602
603 if(IsFakeNode(end->finish_node))
604 GetFakeLatLong(end->finish_node,&finish_lat,&finish_lon);
605 else
606 GetLatLong(nodes,end->finish_node,NULL,&finish_lat,&finish_lon);
607
608 /* Create the list of results and queues */
609
610 results=NewResultsList(20);
611 fwd_queue=NewQueueList(12);
612 rev_queue=NewQueueList(12);
613
614 /* Insert the finish points of the beginning part of the path into the results,
615 translating the segments into super-segments. */
616
617 if(begin->number==1)
618 {
619 index_t superseg=NO_SEGMENT;
620
621 if(begin->prev_segment!=NO_SEGMENT)
622 superseg=FindSuperSegment(nodes,segments,ways,relations,profile,begin->start_node,begin->prev_segment);
623
624 start_result=InsertResult(results,begin->start_node,superseg);
625
626 InsertInQueue(fwd_queue,start_result,0);
627
628 /* Check for barrier at start waypoint - must perform U-turn */
629
630 if(superseg!=NO_SEGMENT)
631 {
632 Node *startp=LookupNode(nodes,begin->start_node,1);
633
634 if(!(startp->allow&profile->transports))
635 force_uturn=1;
636 }
637 }
638 else
639 {
640 Result *begin_result=FirstResult(begin);
641 Result *end_result;
642
643 while((begin_result=NextResult(begin,begin_result)))
644 {
645 if(!IsFakeNode(begin_result->node) && IsSuperNode(LookupNode(nodes,begin_result->node,3)))
646 {
647 index_t superseg=FindSuperSegment(nodes,segments,ways,relations,profile,begin_result->node,begin_result->segment);
648
649 if(superseg!=begin_result->segment)
650 {
651 result1=InsertResult(results,begin_result->node,begin_result->segment);
652
653 result1->score=begin_result->score;
654 }
655 else
656 result1=NO_RESULT;
657
658 result2=FindResult(results,begin_result->node,superseg);
659
660 if(!result2) /* New end node/super-segment pair */
661 {
662 result2=InsertResult(results,begin_result->node,superseg);
663 result2->prev=result1;
664 result2->score=begin_result->score;
665 }
666 else if(begin_result->score<result2->score) /* New end node/super-segment pair is better */
667 {
668 result2->prev=result1;
669 result2->score=begin_result->score;
670 }
671 else
672 continue;
673
674 if((end_result=FindResult(end,result2->node,result2->segment)))
675 {
676 if((result2->score+end_result->score)<total_score)
677 {
678 total_score=result2->score+end_result->score;
679 start_result=finish_result=result2;
680 }
681 }
682 }
683 }
684
685 /* Insert the start points of the beginning part of the path into the queue */
686
687 if(!finish_result)
688 {
689 Result *result=FirstResult(results);
690
691 while(result)
692 {
693 if(result->prev)
694 InsertInQueue(fwd_queue,result,result->score);
695
696 result=NextResult(results,result);
697 }
698 }
699
700 /* Insert the start points of the end part of the path into the queue */
701
702 if(!finish_result)
703 {
704 end_result=FirstResult(end);
705
706 while(end_result)
707 {
708 if(!IsFakeNode(end_result->node) && IsSuperNode(LookupNode(nodes,end_result->node,3)))
709 {
710 result1=InsertResult(results,end_result->node,end_result->segment);
711
712 result1->next=NO_RESULT;
713 result1->score=end_result->score;
714
715 InsertInQueue(rev_queue,result1,0);
716 }
717
718 end_result=NextResult(end,end_result);
719 }
720 }
721 }
722
723
724 /* Loop across all nodes in the two queues, alternating between them */
725
726 while(1)
727 {
728 int queue1_empty=0,queue2_empty=0;
729
730 /* Forward queue */
731
732 if((result1=PopFromQueue(fwd_queue)))
733 {
734 Node *node1p;
735 Segment *segment2p;
736 index_t node1,seg1;
737 index_t turnrelation=NO_RELATION;
738
739 /* score must be better than current best score */
740 if(result1->score>=total_score)
741 continue;
742
743 node1=result1->node;
744 seg1=result1->segment;
745
746 node1p=LookupNode(nodes,node1,1); /* node1 cannot be a fake node (must be a super-node) */
747
748 /* lookup if a turn restriction applies */
749 if(profile->turns && IsTurnRestrictedNode(node1p)) /* node1 cannot be a fake node (must be a super-node) */
750 turnrelation=FindFirstTurnRelation2(relations,node1,seg1);
751
752 /* Loop across all segments */
753
754 segment2p=FirstSegment(segments,node1p,1); /* node1 cannot be a fake node (must be a super-node) */
755
756 while(segment2p)
757 {
758 Node *node2p;
759 Way *way2p;
760 index_t node2,seg2;
761 score_t segment_pref,segment_score,cumulative_score,potential_score;
762 double lat,lon;
763 distance_t direct;
764 int i;
765
766 /* must be a super segment */
767 if(!IsSuperSegment(segment2p))
768 goto endloop_fwd;
769
770 /* must obey one-way restrictions (unless profile allows) */
771 if(profile->oneway && IsOnewayTo(segment2p,node1))
772 {
773 if(profile->transports!=Transports_Bicycle)
774 goto endloop_fwd;
775
776 way2p=LookupWay(ways,segment2p->way,1);
777
778 if(!(way2p->type&Highway_CycleBothWays))
779 goto endloop_fwd;
780 }
781
782 seg2=IndexSegment(segments,segment2p); /* segment cannot be a fake segment (must be a super-segment) */
783
784 /* must perform U-turn in special cases */
785 if(force_uturn && node1==begin->start_node)
786 {
787 if(seg2!=result1->segment)
788 goto endloop_fwd;
789 }
790 else
791 /* must not perform U-turn */
792 if(seg1==seg2) /* No fake segments, applies to all profiles */
793 goto endloop_fwd;
794
795 /* must obey turn relations */
796 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1,seg2,profile->transports))
797 goto endloop_fwd;
798
799 way2p=LookupWay(ways,segment2p->way,1);
800
801 /* mode of transport must be allowed on the highway */
802 if(!(way2p->allow&profile->transports))
803 goto endloop_fwd;
804
805 /* must obey weight restriction (if exists) */
806 if(way2p->weight && way2p->weight<profile->weight)
807 goto endloop_fwd;
808
809 /* must obey height/width/length restriction (if exist) */
810 if((way2p->height && way2p->height<profile->height) ||
811 (way2p->width && way2p->width <profile->width ) ||
812 (way2p->length && way2p->length<profile->length))
813 goto endloop_fwd;
814
815 segment_pref=profile->highway[HIGHWAY(way2p->type)];
816
817 /* highway preferences must allow this highway */
818 if(segment_pref==0)
819 goto endloop_fwd;
820
821 for(i=1;i<Property_Count;i++)
822 if(ways->file.properties & PROPERTIES(i))
823 {
824 if(way2p->props & PROPERTIES(i))
825 segment_pref*=profile->props_yes[i];
826 else
827 segment_pref*=profile->props_no[i];
828 }
829
830 /* profile preferences must allow this highway */
831 if(segment_pref==0)
832 goto endloop_fwd;
833
834 node2=OtherNode(segment2p,node1);
835
836 node2p=LookupNode(nodes,node2,2); /* node2 cannot be a fake node (must be a super-node) */
837
838 /* mode of transport must be allowed through node2 unless it is the final node */
839 if(node2!=end->finish_node && !(node2p->allow&profile->transports))
840 goto endloop_fwd;
841
842 /* calculate the score for the segment and cumulative */
843 if(option_quickest==0)
844 segment_score=(score_t)DISTANCE(segment2p->distance)/segment_pref;
845 else
846 segment_score=(score_t)Duration(segment2p,way2p,profile)/segment_pref;
847
848 cumulative_score=result1->score+segment_score;
849
850 /* score must be better than current best score */
851 if(cumulative_score>=total_score)
852 goto endloop_fwd;
853
854 /* find whether the node/segment combination already exists */
855 result2=FindResult(results,node2,seg2);
856
857 if(result2 && result2->next)
858 {
859 if((result2->score+cumulative_score)<total_score)
860 {
861 total_score=result2->score+cumulative_score;
862 finish_result=result2;
863 start_result =result1;
864 }
865
866 goto endloop_fwd;
867 }
868
869 if(!result2) /* New end node/segment pair */
870 {
871 result2=InsertResult(results,node2,seg2);
872 result2->prev=result1;
873 result2->score=cumulative_score;
874 }
875 else if(cumulative_score<result2->score) /* New end node/segment pair is better */
876 {
877 result2->prev=result1;
878 result2->score=cumulative_score;
879 }
880 else
881 goto endloop_fwd;
882
883 /* Insert a new node into the queue */
884
885 GetLatLong(nodes,node2,node2p,&lat,&lon); /* node2 cannot be a fake node (must be a super-node) */
886
887 direct=Distance(lat,lon,finish_lat,finish_lon);
888
889 if(option_quickest==0)
890 potential_score=result2->score+(score_t)direct/profile->max_pref;
891 else
892 potential_score=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
893
894 if(potential_score<total_score)
895 InsertInQueue(fwd_queue,result2,potential_score);
896
897 endloop_fwd:
898
899 segment2p=NextSegment(segments,segment2p,node1); /* node1 cannot be a fake node (must be a super-node) */
900 }
901
902 #ifdef LIBROUTINO
903 if(!(++loopcount%100000))
904 if(progress_func && !progress_func(progress_value))
905 {
906 progress_abort=1;
907 break;
908 }
909 #endif
910 }
911 else
912 queue1_empty=1;
913
914 /* Reverse queue */
915
916 if((result1=PopFromQueue(rev_queue)))
917 {
918 Node *node1p;
919 Segment *segment1p,*segment2p;
920 Way *way1p;
921 index_t real_node1,node1,seg1;
922 score_t segment1_pref,segment1_score=0;
923 int i;
924
925 /* score must be better than current best score */
926 if(result1->score>=total_score)
927 continue;
928
929 real_node1=result1->node;
930 seg1=result1->segment;
931
932 segment1p=LookupSegment(segments,seg1,1);
933
934 node1=OtherNode(segment1p,real_node1);
935
936 node1p=LookupNode(nodes,node1,1);
937
938 /* mode of transport must be allowed through node1 */
939 if(!(node1p->allow&profile->transports))
940 continue;
941
942 way1p=LookupWay(ways,segment1p->way,1);
943
944 segment1_pref=profile->highway[HIGHWAY(way1p->type)];
945
946 for(i=1;i<Property_Count;i++)
947 if(ways->file.properties & PROPERTIES(i))
948 {
949 if(way1p->props & PROPERTIES(i))
950 segment1_pref*=profile->props_yes[i];
951 else
952 segment1_pref*=profile->props_no[i];
953 }
954
955 /* calculate the score for the segment */
956 if(option_quickest==0)
957 segment1_score=(score_t)DISTANCE(segment1p->distance)/segment1_pref;
958 else
959 segment1_score=(score_t)Duration(segment1p,way1p,profile)/segment1_pref;
960
961 /* Loop across all segments */
962
963 segment2p=FirstSegment(segments,node1p,1); /* node1 cannot be a fake node (must be a super-node) */
964
965 while(segment2p)
966 {
967 Node *node2p;
968 Way *way2p;
969 index_t node2,seg2;
970 score_t segment_pref,cumulative_score,potential_score;
971 double lat,lon;
972 distance_t direct;
973
974 seg2=IndexSegment(segments,segment2p); /* segment cannot be a fake segment (must be a super-segment) */
975
976 /* must not perform U-turn */
977 if(seg1==seg2) /* No fake segments, applies to all profiles */
978 goto endloop_rev;
979
980 /* find whether the node/segment combination already exists */
981 result2=FindResult(results,node1,seg2);
982
983 /* must be a super segment */
984 if(!IsSuperSegment(segment2p) && !(result2 && result2->prev))
985 goto endloop_rev;
986
987 /* must obey turn relations */
988 if(profile->turns && IsTurnRestrictedNode(node1p)) /* node1 cannot be a fake node (must be a super-node) */
989 {
990 index_t turnrelation2=FindFirstTurnRelation2(relations,node1,seg2);
991
992 if(turnrelation2!=NO_RELATION && !IsTurnAllowed(relations,turnrelation2,node1,seg2,seg1,profile->transports))
993 goto endloop_rev;
994 }
995
996 /* must obey one-way restrictions (unless profile allows) */
997 if(profile->oneway && IsOnewayFrom(segment2p,node1)) /* working backwards => disallow oneway *from* node1 */
998 {
999 if(profile->transports!=Transports_Bicycle)
1000 goto endloop_rev;
1001
1002 way2p=LookupWay(ways,segment2p->way,1);
1003
1004 if(!(way2p->type&Highway_CycleBothWays))
1005 goto endloop_rev;
1006 }
1007
1008 way2p=LookupWay(ways,segment2p->way,1);
1009
1010 /* mode of transport must be allowed on the highway */
1011 if(!(way2p->allow&profile->transports))
1012 goto endloop_rev;
1013
1014 /* must obey weight restriction (if exists) */
1015 if(way2p->weight && way2p->weight<profile->weight)
1016 goto endloop_rev;
1017
1018 /* must obey height/width/length restriction (if exist) */
1019 if((way2p->height && way2p->height<profile->height) ||
1020 (way2p->width && way2p->width <profile->width ) ||
1021 (way2p->length && way2p->length<profile->length))
1022 goto endloop_rev;
1023
1024 segment_pref=profile->highway[HIGHWAY(way2p->type)];
1025
1026 /* highway preferences must allow this highway */
1027 if(segment_pref==0)
1028 goto endloop_rev;
1029
1030 for(i=1;i<Property_Count;i++)
1031 if(ways->file.properties & PROPERTIES(i))
1032 {
1033 if(way2p->props & PROPERTIES(i))
1034 segment_pref*=profile->props_yes[i];
1035 else
1036 segment_pref*=profile->props_no[i];
1037 }
1038
1039 /* profile preferences must allow this highway */
1040 if(segment_pref==0)
1041 goto endloop_rev;
1042
1043 node2=OtherNode(segment2p,node1);
1044
1045 cumulative_score=result1->score+segment1_score;
1046
1047 /* score must be better than current best score */
1048 if(cumulative_score>=total_score)
1049 goto endloop_rev;
1050
1051 if(result2 && result2->prev)
1052 {
1053 if((result2->score+cumulative_score)<total_score)
1054 {
1055 total_score=result2->score+cumulative_score;
1056 finish_result=result1;
1057 start_result =result2;
1058 }
1059
1060 goto endloop_rev;
1061 }
1062
1063 if(!result2) /* New end node/segment pair */
1064 {
1065 result2=InsertResult(results,node1,seg2); /* adding in reverse => node1,seg2 */
1066 result2->next=result1; /* working backwards */
1067 result2->score=cumulative_score;
1068 }
1069 else if(cumulative_score<result2->score) /* New end node/segment pair is better */
1070 {
1071 result2->next=result1; /* working backwards */
1072 result2->score=cumulative_score;
1073 }
1074 else
1075 goto endloop_rev;
1076
1077 /* Insert a new node into the queue */
1078
1079 node2p=LookupNode(nodes,node2,2); /* node2 cannot be a fake node (must be a super-node) */
1080
1081 GetLatLong(nodes,node2,node2p,&lat,&lon);
1082
1083 direct=Distance(lat,lon,start_lat,start_lon);
1084
1085 if(option_quickest==0)
1086 potential_score=result2->score+(score_t)direct/profile->max_pref;
1087 else
1088 potential_score=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
1089
1090 if(potential_score<total_score)
1091 InsertInQueue(rev_queue,result2,potential_score);
1092
1093 endloop_rev:
1094
1095 segment2p=NextSegment(segments,segment2p,node1); /* node1 cannot be a fake node (must be a super-node) */
1096 }
1097
1098 #ifdef LIBROUTINO
1099 if(!(++loopcount%100000))
1100 if(progress_func && !progress_func(progress_value))
1101 {
1102 progress_abort=1;
1103 break;
1104 }
1105 #endif
1106 }
1107 else
1108 queue2_empty=1;
1109
1110 if(queue1_empty || queue2_empty)
1111 break;
1112 }
1113
1114 FreeQueueList(fwd_queue);
1115 FreeQueueList(rev_queue);
1116
1117 /* Check it worked */
1118
1119 if(!finish_result)
1120 {
1121 #if DEBUG
1122 printf(" Failed\n");
1123 #endif
1124
1125 #if !DEBUG && !defined(LIBROUTINO)
1126 if(!option_quiet)
1127 printf_last("Found Middle Route: Super-Nodes checked = %d - Fail",results->number);
1128 #endif
1129
1130 FreeResultsList(results);
1131 return(NULL);
1132 }
1133
1134 /* Turn the route round and fill in the start and finish information */
1135
1136 if(start_result!=finish_result)
1137 {
1138 start_result->next=finish_result;
1139 finish_result->prev=start_result;
1140
1141 while(start_result->prev && start_result->prev!=NO_RESULT)
1142 start_result=start_result->prev;
1143
1144 FixForwardRoute(results,finish_result);
1145
1146 if(!start_result->prev && start_result->next)
1147 start_result=start_result->next;
1148
1149 while(finish_result->next && finish_result->next!=NO_RESULT)
1150 finish_result=finish_result->next;
1151 }
1152
1153 results->start_node=start_result->node;
1154 results->prev_segment=start_result->segment;
1155
1156 results->finish_node=finish_result->node;
1157 results->last_segment=finish_result->segment;
1158
1159 #if DEBUG
1160 printf(" -------- middle route (via super-nodes/segments) score=%.3f\n",total_score);
1161
1162 print_debug_route(nodes,segments,results,NULL,4,+1);
1163 #endif
1164
1165 #if !DEBUG && !defined(LIBROUTINO)
1166 if(!option_quiet)
1167 printf_last("Found Middle Route: Super-Nodes checked = %d",results->number);
1168 #endif
1169
1170 return(results);
1171 }
1172
1173
1174 /*++++++++++++++++++++++++++++++++++++++
1175 Find the super-segment that represents the route that contains a particular segment.
1176
1177 index_t FindSuperSegment Returns the index of the super-segment.
1178
1179 Nodes *nodes The set of nodes to use.
1180
1181 Segments *segments The set of segments to use.
1182
1183 Ways *ways The set of ways to use.
1184
1185 Relations *relations The set of relations to use.
1186
1187 Profile *profile The profile containing the transport type, speeds and allowed highways.
1188
1189 index_t finish_node The super-node that the route ends at.
1190
1191 index_t finish_segment The segment that the route ends with.
1192 ++++++++++++++++++++++++++++++++++++++*/
1193
FindSuperSegment(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t finish_node,index_t finish_segment)1194 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t finish_node,index_t finish_segment)
1195 {
1196 Node *supernodep;
1197 Segment *supersegmentp;
1198
1199 #if DEBUG
1200 printf(" FindSuperSegment(...,finish_node=%"Pindex_t",finish_segment=%"Pindex_t")\n",finish_node,finish_segment);
1201 #endif
1202
1203 if(IsFakeSegment(finish_segment))
1204 finish_segment=IndexRealSegment(finish_segment);
1205
1206 supernodep=LookupNode(nodes,finish_node,3); /* finish_node cannot be a fake node (must be a super-node) */
1207 supersegmentp=LookupSegment(segments,finish_segment,3); /* finish_segment cannot be a fake segment. */
1208
1209 if(IsSuperSegment(supersegmentp))
1210 {
1211 #if DEBUG
1212 printf(" -- already super-segment = %"Pindex_t"\n",finish_segment);
1213 #endif
1214
1215 return(finish_segment);
1216 }
1217
1218 /* Loop across all segments */
1219
1220 supersegmentp=FirstSegment(segments,supernodep,3); /* supernode cannot be a fake node (must be a super-node) */
1221
1222 while(supersegmentp)
1223 {
1224 if(IsSuperSegment(supersegmentp))
1225 {
1226 Results *results;
1227 Result *result;
1228 index_t start_node;
1229
1230 start_node=OtherNode(supersegmentp,finish_node);
1231
1232 results=FindSuperRoute(nodes,segments,ways,relations,profile,start_node,finish_node);
1233
1234 if(!results)
1235 continue;
1236
1237 result=FindResult(results,finish_node,finish_segment);
1238
1239 if(result && (distance_t)result->score==DISTANCE(supersegmentp->distance))
1240 {
1241 FreeResultsList(results);
1242
1243 #if DEBUG
1244 printf(" -- found super-segment = %"Pindex_t"\n",IndexSegment(segments,supersegmentp));
1245 #endif
1246
1247 return(IndexSegment(segments,supersegmentp));
1248 }
1249
1250 if(results)
1251 FreeResultsList(results);
1252 }
1253
1254 supersegmentp=NextSegment(segments,supersegmentp,finish_node); /* finish_node cannot be a fake node (must be a super-node) */
1255 }
1256
1257 #if DEBUG
1258 printf(" -- no super-segment = %"Pindex_t"\n",finish_segment);
1259 #endif
1260
1261 return(finish_segment);
1262 }
1263
1264
1265 /*++++++++++++++++++++++++++++++++++++++
1266 Find the shortest route between two super-nodes using only normal nodes.
1267 This is effectively the same function as is used in superx.c when finding super-segments initially.
1268
1269 Results *FindSuperRoute Returns a set of results.
1270
1271 Nodes *nodes The set of nodes to use.
1272
1273 Segments *segments The set of segments to use.
1274
1275 Ways *ways The set of ways to use.
1276
1277 Relations *relations The set of relations to use.
1278
1279 Profile *profile The profile containing the transport type, speeds and allowed highways.
1280
1281 index_t start_node The start node.
1282
1283 index_t finish_node The finish node.
1284 ++++++++++++++++++++++++++++++++++++++*/
1285
FindSuperRoute(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t start_node,index_t finish_node)1286 static Results *FindSuperRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t finish_node)
1287 {
1288 Results *results;
1289 Queue *queue;
1290 Result *result1,*result2;
1291
1292 #if DEBUG
1293 printf(" FindSuperRoute(...,start_node=%"Pindex_t" finish_node=%"Pindex_t")\n",start_node,finish_node);
1294 #endif
1295
1296 /* Create the list of results and insert the first node into the queue */
1297
1298 results=NewResultsList(8);
1299 queue=NewQueueList(8);
1300
1301 result1=InsertResult(results,start_node,NO_SEGMENT);
1302
1303 InsertInQueue(queue,result1,0);
1304
1305 /* Loop across all nodes in the queue */
1306
1307 while((result1=PopFromQueue(queue)))
1308 {
1309 Node *node1p=NULL;
1310 Segment *segment2p;
1311 index_t node1,seg1;
1312
1313 node1=result1->node;
1314 seg1=result1->segment;
1315
1316 node1p=LookupNode(nodes,node1,4); /* node1 cannot be a fake node */
1317
1318 /* Loop across all segments */
1319
1320 segment2p=FirstSegment(segments,node1p,4); /* node1 cannot be a fake node */
1321
1322 while(segment2p)
1323 {
1324 Node *node2p=NULL;
1325 index_t node2,seg2;
1326 score_t cumulative_score;
1327
1328 /* must be a normal segment */
1329 if(!IsNormalSegment(segment2p))
1330 goto endloop;
1331
1332 /* must obey one-way restrictions */
1333 if(IsOnewayTo(segment2p,node1))
1334 {
1335 Way *way2p;
1336
1337 if(profile->transports!=Transports_Bicycle)
1338 goto endloop;
1339
1340 way2p=LookupWay(ways,segment2p->way,2);
1341
1342 if(!(way2p->type&Highway_CycleBothWays))
1343 goto endloop;
1344 }
1345
1346 seg2=IndexSegment(segments,segment2p);
1347
1348 /* must not perform U-turn */
1349 if(seg1==seg2)
1350 goto endloop;
1351
1352 node2=OtherNode(segment2p,node1);
1353
1354 node2p=LookupNode(nodes,node2,4); /* node2 cannot be a fake node */
1355
1356 /* must not pass over super-node */
1357 if(node2!=finish_node && IsSuperNode(node2p))
1358 goto endloop;
1359
1360 /* Specifically looking for the shortest route to emulate superx.c */
1361 cumulative_score=result1->score+(score_t)DISTANCE(segment2p->distance);
1362
1363 result2=FindResult(results,node2,seg2);
1364
1365 if(!result2) /* New end node/segment combination */
1366 {
1367 result2=InsertResult(results,node2,seg2);
1368 result2->prev=result1;
1369 result2->score=cumulative_score;
1370 }
1371 else if(cumulative_score<result2->score) /* New score for end node/segment combination is better */
1372 {
1373 result2->prev=result1;
1374 result2->segment=seg2;
1375 result2->score=cumulative_score;
1376 }
1377 else goto endloop;
1378
1379 /* don't route beyond a super-node. */
1380 if(!IsSuperNode(node2p))
1381 InsertInQueue(queue,result2,result2->score);
1382
1383 endloop:
1384
1385 segment2p=NextSegment(segments,segment2p,node1);
1386 }
1387 }
1388
1389 FreeQueueList(queue);
1390
1391 #if DEBUG
1392 Result *s=FirstResult(results);
1393
1394 while(s)
1395 {
1396 if(s->node==finish_node)
1397 {
1398 printf(" -------- super-route\n");
1399
1400 print_debug_route(nodes,segments,results,FindResult(results,s->node,s->segment),8,-1);
1401 }
1402
1403 s=NextResult(results,s);
1404 }
1405 #endif
1406
1407 return(results);
1408 }
1409
1410
1411 /*++++++++++++++++++++++++++++++++++++++
1412 Find all routes from a specified node to any super-node.
1413
1414 Results *FindStartRoutes Returns a set of results.
1415
1416 Nodes *nodes The set of nodes to use.
1417
1418 Segments *segments The set of segments to use.
1419
1420 Ways *ways The set of ways to use.
1421
1422 Relations *relations The set of relations to use.
1423
1424 Profile *profile The profile containing the transport type, speeds and allowed highways.
1425
1426 index_t start_node The start node.
1427
1428 index_t prev_segment The previous segment before the start node.
1429
1430 index_t finish_node The finish node.
1431 ++++++++++++++++++++++++++++++++++++++*/
1432
FindStartRoutes(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t start_node,index_t prev_segment,index_t finish_node)1433 static Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node)
1434 {
1435 Results *results;
1436 Queue *queue,*superqueue;
1437 Result *result1,*result2;
1438 Result *start_result,*finish_result=NULL;
1439 score_t total_score=INF_SCORE;
1440 int nsuper=0,force_uturn=0;
1441
1442 #if DEBUG
1443 printf(" FindStartRoutes(...,start_node=%"Pindex_t" prev_segment=%"Pindex_t" finish_node=%"Pindex_t")\n",start_node,prev_segment,finish_node);
1444 #endif
1445
1446 #if !DEBUG && !defined(LIBROUTINO)
1447 if(!option_quiet)
1448 printf_first("Finding Start Route: Nodes checked = 0");
1449 #endif
1450
1451 /* Create the list of results and insert the first node into the queue */
1452
1453 results=NewResultsList(8);
1454 queue=NewQueueList(8);
1455 superqueue=NewQueueList(8);
1456
1457 start_result=InsertResult(results,start_node,prev_segment);
1458
1459 InsertInQueue(queue,start_result,0);
1460
1461 /* Check for barrier at start waypoint - must perform U-turn */
1462
1463 if(prev_segment!=NO_SEGMENT && !IsFakeNode(start_node))
1464 {
1465 Node *startp=LookupNode(nodes,start_node,1);
1466
1467 if(!(startp->allow&profile->transports))
1468 force_uturn=1;
1469 }
1470
1471 /* Loop across all nodes in the queue */
1472
1473 while((result1=PopFromQueue(queue)))
1474 {
1475 Node *node1p=NULL;
1476 Segment *segment2p;
1477 index_t node1,seg1,seg1r;
1478 index_t turnrelation=NO_RELATION;
1479
1480 /* score must be better than current best score */
1481 if(result1->score>=total_score)
1482 continue;
1483
1484 node1=result1->node;
1485 seg1=result1->segment;
1486
1487 if(IsFakeSegment(seg1))
1488 seg1r=IndexRealSegment(seg1);
1489 else
1490 seg1r=seg1;
1491
1492 if(!IsFakeNode(node1))
1493 node1p=LookupNode(nodes,node1,1);
1494
1495 /* lookup if a turn restriction applies */
1496 if(profile->turns && node1p && IsTurnRestrictedNode(node1p))
1497 turnrelation=FindFirstTurnRelation2(relations,node1,seg1r);
1498
1499 /* Loop across all segments */
1500
1501 if(IsFakeNode(node1))
1502 segment2p=FirstFakeSegment(node1);
1503 else
1504 segment2p=FirstSegment(segments,node1p,1);
1505
1506 while(segment2p)
1507 {
1508 Node *node2p=NULL;
1509 Way *way2p;
1510 index_t node2,seg2,seg2r;
1511 score_t segment_pref,segment_score,cumulative_score;
1512 int i;
1513
1514 node2=OtherNode(segment2p,node1); /* need this here because we use node2 at the end of the loop */
1515
1516 /* must be a normal segment */
1517 if(!IsNormalSegment(segment2p))
1518 goto endloop;
1519
1520 /* must obey one-way restrictions (unless profile allows) */
1521 if(profile->oneway && IsOnewayTo(segment2p,node1))
1522 {
1523 if(profile->transports!=Transports_Bicycle)
1524 goto endloop;
1525
1526 way2p=LookupWay(ways,segment2p->way,1);
1527
1528 if(!(way2p->type&Highway_CycleBothWays))
1529 goto endloop;
1530 }
1531
1532 if(IsFakeNode(node1) || IsFakeNode(node2))
1533 {
1534 seg2 =IndexFakeSegment(segment2p);
1535 seg2r=IndexRealSegment(seg2);
1536 }
1537 else
1538 {
1539 seg2 =IndexSegment(segments,segment2p);
1540 seg2r=seg2;
1541 }
1542
1543 /* must perform U-turn in special cases */
1544 if(node1==start_node && force_uturn)
1545 {
1546 if(seg2r!=result1->segment)
1547 goto endloop;
1548 }
1549 else
1550 /* must not perform U-turn (unless profile allows) */
1551 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2))))
1552 goto endloop;
1553
1554 /* must obey turn relations */
1555 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1r,seg2r,profile->transports))
1556 goto endloop;
1557
1558 way2p=LookupWay(ways,segment2p->way,1);
1559
1560 /* mode of transport must be allowed on the highway */
1561 if(!(way2p->allow&profile->transports))
1562 goto endloop;
1563
1564 /* must obey weight restriction (if exists) */
1565 if(way2p->weight && way2p->weight<profile->weight)
1566 goto endloop;
1567
1568 /* must obey height/width/length restriction (if exists) */
1569 if((way2p->height && way2p->height<profile->height) ||
1570 (way2p->width && way2p->width <profile->width ) ||
1571 (way2p->length && way2p->length<profile->length))
1572 goto endloop;
1573
1574 segment_pref=profile->highway[HIGHWAY(way2p->type)];
1575
1576 /* highway preferences must allow this highway */
1577 if(segment_pref==0)
1578 goto endloop;
1579
1580 for(i=1;i<Property_Count;i++)
1581 if(ways->file.properties & PROPERTIES(i))
1582 {
1583 if(way2p->props & PROPERTIES(i))
1584 segment_pref*=profile->props_yes[i];
1585 else
1586 segment_pref*=profile->props_no[i];
1587 }
1588
1589 /* profile preferences must allow this highway */
1590 if(segment_pref==0)
1591 goto endloop;
1592
1593 if(!IsFakeNode(node2))
1594 node2p=LookupNode(nodes,node2,2);
1595
1596 /* mode of transport must be allowed through node2 unless it is the final node */
1597 if(node2p && node2!=finish_node && !(node2p->allow&profile->transports))
1598 goto endloop;
1599
1600 /* calculate the score for the segment and cumulative */
1601 if(option_quickest==0)
1602 segment_score=(score_t)DISTANCE(segment2p->distance)/segment_pref;
1603 else
1604 segment_score=(score_t)Duration(segment2p,way2p,profile)/segment_pref;
1605
1606 /* prefer not to follow two fake segments when one would do (special case) */
1607 if(IsFakeSegment(seg2))
1608 segment_score*=1.01f;
1609
1610 cumulative_score=result1->score+segment_score;
1611
1612 /* score must be better than current best score (if finish node already found) */
1613 if(cumulative_score>=total_score)
1614 goto endloop;
1615
1616 /* find whether the node/segment combination already exists */
1617 result2=FindResult(results,node2,seg2);
1618
1619 if(!result2) /* New end node/segment combination */
1620 {
1621 result2=InsertResult(results,node2,seg2);
1622 result2->prev=result1;
1623 result2->score=cumulative_score;
1624
1625 if(node2p && IsSuperNode(node2p))
1626 nsuper++;
1627 }
1628 else if(cumulative_score<result2->score) /* New score for end node/segment combination is better */
1629 {
1630 result2->prev=result1;
1631 result2->score=cumulative_score;
1632 }
1633 else
1634 goto endloop;
1635
1636 if(node2==finish_node)
1637 {
1638 if(!finish_result)
1639 {
1640 Result *result3;
1641
1642 while((result3=PopFromQueue(superqueue)))
1643 InsertInQueue(queue,result3,result3->score);
1644 }
1645
1646 if(cumulative_score<total_score)
1647 {
1648 total_score=cumulative_score;
1649 finish_result=result2;
1650 }
1651 }
1652
1653 if(finish_result || (node2p && !IsSuperNode(node2p)))
1654 InsertInQueue(queue,result2,result2->score);
1655 else if(node2p && IsSuperNode(node2p))
1656 InsertInQueue(superqueue,result2,result2->score);
1657
1658 endloop:
1659
1660 if(IsFakeNode(node1))
1661 segment2p=NextFakeSegment(segment2p,node1);
1662 else if(IsFakeNode(node2))
1663 segment2p=NULL; /* cannot call NextSegment() with a fake segment */
1664 else
1665 {
1666 segment2p=NextSegment(segments,segment2p,node1);
1667
1668 if(!segment2p && IsFakeNode(finish_node))
1669 segment2p=ExtraFakeSegment(node1,finish_node);
1670 }
1671 }
1672 }
1673
1674 FreeQueueList(queue);
1675 FreeQueueList(superqueue);
1676
1677 /* Check it worked */
1678
1679 if(results->number==1 || (nsuper==0 && !finish_result))
1680 {
1681 #if DEBUG
1682 printf(" Failed (%d results, %d super)\n",results->number,nsuper);
1683 #endif
1684
1685 #if !DEBUG && !defined(LIBROUTINO)
1686 if(!option_quiet)
1687 printf_last("Found Start Route: Nodes checked = %d - Fail",results->number);
1688 #endif
1689
1690 FreeResultsList(results);
1691 return(NULL);
1692 }
1693
1694 /* Turn the route round and fill in the start and finish information */
1695
1696 results->start_node =start_result->node;
1697 results->prev_segment=start_result->segment;
1698
1699 if(finish_result)
1700 {
1701 FixForwardRoute(results,finish_result);
1702
1703 results->finish_node =finish_result->node;
1704 results->last_segment=finish_result->segment;
1705 }
1706
1707 #if DEBUG
1708 Result *s=FirstResult(results);
1709
1710 while(s)
1711 {
1712 if(s->node==finish_node || (!IsFakeNode(s->node) && IsSuperNode(LookupNode(nodes,s->node,1))))
1713 {
1714 printf(" -------- possible start route\n");
1715
1716 print_debug_route(nodes,segments,results,FindResult(results,s->node,s->segment),4,-1);
1717 }
1718
1719 s=NextResult(results,s);
1720 }
1721 #endif
1722
1723 #if !DEBUG && !defined(LIBROUTINO)
1724 if(!option_quiet)
1725 printf_last("Found Start Route: Nodes checked = %d",results->number);
1726 #endif
1727
1728 return(results);
1729 }
1730
1731
1732 /*++++++++++++++++++++++++++++++++++++++
1733 Find all routes from any super-node to a specific node (by working backwards from the specific node to all super-nodes).
1734
1735 Results *FindFinishRoutes Returns a set of results.
1736
1737 Nodes *nodes The set of nodes to use.
1738
1739 Segments *segments The set of segments to use.
1740
1741 Ways *ways The set of ways to use.
1742
1743 Relations *relations The set of relations to use.
1744
1745 Profile *profile The profile containing the transport type, speeds and allowed highways.
1746
1747 index_t finish_node The finishing node.
1748 ++++++++++++++++++++++++++++++++++++++*/
1749
FindFinishRoutes(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,index_t finish_node)1750 static Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t finish_node)
1751 {
1752 Results *results,*finish_results;
1753 Queue *queue;
1754 Result *result1,*result2;
1755 Result *finish_result;
1756
1757 #if DEBUG
1758 printf(" FindFinishRoutes(...,finish_node=%"Pindex_t")\n",finish_node);
1759 #endif
1760
1761 #if !DEBUG && !defined(LIBROUTINO)
1762 if(!option_quiet)
1763 printf_first("Finding Finish Route: Nodes checked = 0");
1764 #endif
1765
1766 /* Create the results and insert the finish node into the queue */
1767
1768 finish_results=NewResultsList(2);
1769
1770 results=NewResultsList(8);
1771 queue=NewQueueList(8);
1772
1773 finish_result=InsertResult(finish_results,finish_node,NO_SEGMENT);
1774
1775 InsertInQueue(queue,finish_result,0);
1776
1777 /* Loop across all nodes in the queue */
1778
1779 while((result1=PopFromQueue(queue)))
1780 {
1781 Node *node1p=NULL;
1782 Segment *segment1p,*segment2p;
1783 Way *way1p;
1784 index_t real_node1,node1,seg1,seg1r;
1785 index_t turnrelation=NO_RELATION;
1786 score_t segment1_pref,segment1_score=0;
1787 int i;
1788
1789 real_node1=result1->node;
1790 seg1=result1->segment;
1791
1792 if(seg1!=NO_SEGMENT && IsFakeSegment(seg1))
1793 seg1r=IndexRealSegment(seg1);
1794 else
1795 seg1r=seg1;
1796
1797 if(seg1!=NO_SEGMENT)
1798 {
1799 if(IsFakeSegment(seg1))
1800 segment1p=LookupFakeSegment(seg1);
1801 else
1802 segment1p=LookupSegment(segments,seg1,1);
1803 }
1804
1805 if(seg1==NO_SEGMENT)
1806 node1=real_node1;
1807 else
1808 node1=OtherNode(segment1p,real_node1);
1809
1810 if(!IsFakeNode(node1))
1811 node1p=LookupNode(nodes,node1,1);
1812
1813 /* mode of transport must be allowed through node1 */
1814 if(seg1!=NO_SEGMENT)
1815 if(node1p && !(node1p->allow&profile->transports))
1816 continue;
1817
1818 if(seg1!=NO_SEGMENT)
1819 {
1820 way1p=LookupWay(ways,segment1p->way,1);
1821
1822 segment1_pref=profile->highway[HIGHWAY(way1p->type)];
1823
1824 for(i=1;i<Property_Count;i++)
1825 if(ways->file.properties & PROPERTIES(i))
1826 {
1827 if(way1p->props & PROPERTIES(i))
1828 segment1_pref*=profile->props_yes[i];
1829 else
1830 segment1_pref*=profile->props_no[i];
1831 }
1832
1833 /* calculate the score for the segment */
1834 if(option_quickest==0)
1835 segment1_score=(score_t)DISTANCE(segment1p->distance)/segment1_pref;
1836 else
1837 segment1_score=(score_t)Duration(segment1p,way1p,profile)/segment1_pref;
1838
1839 /* prefer not to follow two fake segments when one would do (special case) */
1840 if(IsFakeSegment(seg1))
1841 segment1_score*=1.01f;
1842 }
1843
1844 /* Loop across all segments */
1845
1846 if(IsFakeNode(node1))
1847 segment2p=FirstFakeSegment(node1);
1848 else
1849 segment2p=FirstSegment(segments,node1p,1);
1850
1851 while(segment2p)
1852 {
1853 Node *node2p=NULL;
1854 Way *way2p;
1855 index_t node2,seg2,seg2r;
1856 score_t segment_pref,cumulative_score;
1857
1858 /* must be a normal segment unless node1 is a super-node (see below). */
1859 if((IsFakeNode(node1) || !IsSuperNode(node1p)) && !IsNormalSegment(segment2p))
1860 goto endloop;
1861
1862 /* must be a super segment if node1 is a super-node to give starting super-segment for finding middle route. */
1863 if((!IsFakeNode(node1) && IsSuperNode(node1p)) && !IsSuperSegment(segment2p))
1864 goto endloop;
1865
1866 /* must obey one-way restrictions (unless profile allows) */
1867 if(profile->oneway && IsOnewayFrom(segment2p,node1)) /* working backwards => disallow oneway *from* node1 */
1868 {
1869 if(profile->transports!=Transports_Bicycle)
1870 goto endloop;
1871
1872 way2p=LookupWay(ways,segment2p->way,1);
1873
1874 if(!(way2p->type&Highway_CycleBothWays))
1875 goto endloop;
1876 }
1877
1878 node2=OtherNode(segment2p,node1);
1879
1880 if(IsFakeNode(node1) || IsFakeNode(node2))
1881 {
1882 seg2 =IndexFakeSegment(segment2p);
1883 seg2r=IndexRealSegment(seg2);
1884 }
1885 else
1886 {
1887 seg2 =IndexSegment(segments,segment2p);
1888 seg2r=seg2;
1889 }
1890
1891 if(seg1!=NO_SEGMENT)
1892 {
1893 /* must not perform U-turn (unless profile allows) */
1894 if(profile->turns)
1895 {
1896 if(IsFakeNode(node1) || !IsSuperNode(node1p))
1897 {
1898 if(seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2)))
1899 goto endloop;
1900 }
1901 else
1902 {
1903 index_t superseg=FindSuperSegment(nodes,segments,ways,relations,profile,node1,seg1);
1904
1905 if(seg2==superseg)
1906 goto endloop;
1907 }
1908 }
1909
1910 /* lookup if a turn restriction applies */
1911 if(profile->turns && node1p && IsTurnRestrictedNode(node1p))
1912 turnrelation=FindFirstTurnRelation2(relations,node1,seg2r);
1913
1914 /* must obey turn relations */
1915 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg2r,seg1r,profile->transports))
1916 goto endloop;
1917 }
1918
1919 way2p=LookupWay(ways,segment2p->way,1);
1920
1921 /* mode of transport must be allowed on the highway */
1922 if(!(way2p->allow&profile->transports))
1923 goto endloop;
1924
1925 /* must obey weight restriction (if exists) */
1926 if(way2p->weight && way2p->weight<profile->weight)
1927 goto endloop;
1928
1929 /* must obey height/width/length restriction (if exist) */
1930 if((way2p->height && way2p->height<profile->height) ||
1931 (way2p->width && way2p->width <profile->width ) ||
1932 (way2p->length && way2p->length<profile->length))
1933 goto endloop;
1934
1935 segment_pref=profile->highway[HIGHWAY(way2p->type)];
1936
1937 /* highway preferences must allow this highway */
1938 if(segment_pref==0)
1939 goto endloop;
1940
1941 for(i=1;i<Property_Count;i++)
1942 if(ways->file.properties & PROPERTIES(i))
1943 {
1944 if(way2p->props & PROPERTIES(i))
1945 segment_pref*=profile->props_yes[i];
1946 else
1947 segment_pref*=profile->props_no[i];
1948 }
1949
1950 /* profile preferences must allow this highway */
1951 if(segment_pref==0)
1952 goto endloop;
1953
1954 if(!IsFakeNode(node2))
1955 node2p=LookupNode(nodes,node2,2);
1956
1957 /* mode of transport must be allowed through node2 */
1958 if(node2p && !(node2p->allow&profile->transports))
1959 goto endloop;
1960
1961 cumulative_score=result1->score+segment1_score;
1962
1963 /* find whether the node/segment combination already exists */
1964 result2=FindResult(results,node1,seg2); /* adding in reverse => node1,seg2 */
1965
1966 if(!result2) /* New end node */
1967 {
1968 result2=InsertResult(results,node1,seg2); /* adding in reverse => node1,seg2 */
1969 if(result1!=finish_result)
1970 result2->next=result1; /* working backwards */
1971 result2->score=cumulative_score;
1972 }
1973 else if(cumulative_score<result2->score) /* New end node is better */
1974 {
1975 if(result1!=finish_result)
1976 result2->next=result1; /* working backwards */
1977 result2->score=cumulative_score;
1978 }
1979 else
1980 goto endloop;
1981
1982 if(IsFakeNode(node1) || !IsSuperNode(node1p))
1983 InsertInQueue(queue,result2,result2->score);
1984
1985 endloop:
1986
1987 if(IsFakeNode(node1))
1988 segment2p=NextFakeSegment(segment2p,node1);
1989 else
1990 segment2p=NextSegment(segments,segment2p,node1);
1991 }
1992 }
1993
1994 FreeQueueList(queue);
1995
1996 FreeResultsList(finish_results);
1997
1998 /* Check it worked */
1999
2000 if(results->number==0)
2001 {
2002 #if DEBUG
2003 printf(" Failed\n");
2004 #endif
2005
2006 #if !DEBUG && !defined(LIBROUTINO)
2007 if(!option_quiet)
2008 printf_last("Found Finish Route: Nodes checked = %d - Fail",results->number);
2009 #endif
2010
2011 FreeResultsList(results);
2012 return(NULL);
2013 }
2014
2015 /* Update the results */
2016
2017 results->finish_node=finish_node;
2018
2019 #if DEBUG
2020 Result *s=FirstResult(results);
2021
2022 while(s)
2023 {
2024 if(!IsFakeNode(s->node) && IsSuperNode(LookupNode(nodes,s->node,1)))
2025 {
2026 printf(" -------- possible finish route\n");
2027
2028 print_debug_route(nodes,segments,results,FindResult(results,s->node,s->segment),4,+1);
2029 }
2030
2031 s=NextResult(results,s);
2032 }
2033 #endif
2034
2035 #if !DEBUG && !defined(LIBROUTINO)
2036 if(!option_quiet)
2037 printf_last("Found Finish Route: Nodes checked = %d",results->number);
2038 #endif
2039
2040 return(results);
2041 }
2042
2043
2044 /*++++++++++++++++++++++++++++++++++++++
2045 Create an optimum route given the set of super-nodes to follow.
2046
2047 Results *CombineRoutes Returns the results from joining the super-nodes.
2048
2049 Nodes *nodes The set of nodes to use.
2050
2051 Segments *segments The set of segments to use.
2052
2053 Ways *ways The set of ways to use.
2054
2055 Relations *relations The set of relations to use.
2056
2057 Profile *profile The profile containing the transport type, speeds and allowed highways.
2058
2059 Results *begin The set of results for the start of the route.
2060
2061 Results *middle The set of results from the super-node route.
2062
2063 Results *end The set of results for the end of the route.
2064 ++++++++++++++++++++++++++++++++++++++*/
2065
CombineRoutes(Nodes * nodes,Segments * segments,Ways * ways,Relations * relations,Profile * profile,Results * begin,Results * middle,Results * end)2066 static Results *CombineRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,Results *begin,Results *middle,Results *end)
2067 {
2068 Result *midres,*comres;
2069 Results *combined;
2070
2071 #if DEBUG
2072 printf(" CombineRoutes(...,[begin has %d nodes],[middle has %d nodes],[end has %d nodes])\n",begin->number,middle->number,end->number);
2073 #endif
2074
2075 #if !DEBUG && !defined(LIBROUTINO)
2076 if(!option_quiet)
2077 printf_first("Finding Combined Route: Nodes = 0");
2078 #endif
2079
2080 combined=NewResultsList(10);
2081
2082 /* Insert the start point */
2083
2084 midres=FindResult(middle,middle->start_node,middle->prev_segment);
2085
2086 comres=InsertResult(combined,begin->start_node,begin->prev_segment);
2087
2088 /* Insert the start of the route */
2089
2090 if(begin->number>1)
2091 {
2092 Result *begres;
2093
2094 if(midres->prev==NO_RESULT)
2095 begres=FindResult(begin,midres->node,midres->segment);
2096 else
2097 begres=FindResult(begin,midres->prev->node,midres->prev->segment);
2098
2099 FixForwardRoute(begin,begres);
2100
2101 begres=FindResult(begin,begin->start_node,begin->prev_segment);
2102
2103 begres=begres->next;
2104
2105 do
2106 {
2107 Result *comres2;
2108
2109 comres2=InsertResult(combined,begres->node,begres->segment);
2110
2111 comres2->score=begres->score;
2112 comres2->prev=comres;
2113
2114 begres=begres->next;
2115
2116 comres=comres2;
2117 }
2118 while(begres);
2119 }
2120
2121 /* Sort out the combined route */
2122
2123 while(midres->next && midres->next!=NO_RESULT)
2124 {
2125 Results *results=FindNormalRoute(nodes,segments,ways,relations,profile,comres->node,comres->segment,midres->next->node);
2126 Result *result;
2127
2128 if(!results)
2129 {
2130 #if !DEBUG && !defined(LIBROUTINO)
2131 if(!option_quiet)
2132 printf_last("Found Combined Route: Nodes = %d - Fail",combined->number);
2133 #endif
2134
2135 FreeResultsList(combined);
2136 return(NULL);
2137 }
2138
2139 result=FindResult(results,midres->node,comres->segment);
2140
2141 result=result->next;
2142
2143 /*
2144 * midres midres->next
2145 * = =
2146 * ---*----------------------------------* = middle
2147 *
2148 * ---*----.----.----.----.----.----.----* = results
2149 * =
2150 * result
2151 *
2152 * ---*----.----.----.----.----.----.----* = combined
2153 * = =
2154 * comres comres2
2155 */
2156
2157 do
2158 {
2159 Result *comres2;
2160
2161 comres2=InsertResult(combined,result->node,result->segment);
2162
2163 comres2->score=midres->score+result->score;
2164 comres2->prev=comres;
2165
2166 result=result->next;
2167
2168 comres=comres2;
2169 }
2170 while(result);
2171
2172 FreeResultsList(results);
2173
2174 midres=midres->next;
2175
2176 midres->score=comres->score;
2177 }
2178
2179 /* Insert the end of the route */
2180
2181 if(end->number>0)
2182 {
2183 Result *endres=FindResult(end,midres->node,midres->segment);
2184
2185 while(endres->next)
2186 {
2187 Result *comres2;
2188
2189 comres2=InsertResult(combined,endres->next->node,endres->next->segment);
2190
2191 comres2->score=comres->score+(endres->score-endres->next->score);
2192 comres2->prev=comres;
2193
2194 endres=endres->next;
2195
2196 comres=comres2;
2197 }
2198 }
2199
2200 /* Turn the route round and fill in the start and finish information */
2201
2202 FixForwardRoute(combined,comres);
2203
2204 combined->start_node=begin->start_node;
2205 combined->prev_segment=begin->prev_segment;
2206
2207 combined->finish_node=comres->node;
2208 combined->last_segment=comres->segment;
2209
2210 #if DEBUG
2211 printf(" -------- combined route (end-to-end)\n");
2212
2213 print_debug_route(nodes,segments,combined,NULL,4,+1);
2214 #endif
2215
2216 #if !DEBUG && !defined(LIBROUTINO)
2217 if(!option_quiet)
2218 printf_last("Found Combined Route: Nodes = %d",combined->number);
2219 #endif
2220
2221 return(combined);
2222 }
2223
2224
2225 /*++++++++++++++++++++++++++++++++++++++
2226 Fix the forward route (i.e. setup next pointers for forward path from prev nodes on reverse path).
2227
2228 Results *results The set of results to update.
2229
2230 Result *finish_result The result for the finish point.
2231 ++++++++++++++++++++++++++++++++++++++*/
2232
FixForwardRoute(Results * results,Result * finish_result)2233 static void FixForwardRoute(Results *results,Result *finish_result)
2234 {
2235 Result *current_result=finish_result;
2236
2237 do
2238 {
2239 Result *result;
2240
2241 if(current_result->prev && current_result->prev!=NO_RESULT)
2242 {
2243 result=current_result->prev;
2244
2245 result->next=current_result;
2246
2247 current_result=result;
2248 }
2249 else
2250 current_result=NULL;
2251 }
2252 while(current_result);
2253 }
2254
2255
2256 #if DEBUG
2257
2258 /*++++++++++++++++++++++++++++++++++++++
2259 Print a debug message about a route.
2260
2261 Nodes *nodes The set of nodes to use.
2262
2263 Segments *segments The set of segments to use.
2264
2265 Results *results The set of results to print.
2266
2267 Result *first The result to start with or NULL for the first result.
2268
2269 int indent The number of spaces of indentation at the beginning.
2270
2271 int direction The direction of travel, -1 = backwards (prev) or +1 = forwards (next).
2272 ++++++++++++++++++++++++++++++++++++++*/
2273
print_debug_route(Nodes * nodes,Segments * segments,Results * results,Result * first,int indent,int direction)2274 static void print_debug_route(Nodes *nodes,Segments *segments,Results *results,Result *first,int indent,int direction)
2275 {
2276 Result *r;
2277 char *spaces=" ";
2278
2279 if(first)
2280 r=first;
2281 else
2282 r=FindResult(results,results->start_node,results->prev_segment);
2283
2284 while(r && r!=NO_RESULT)
2285 {
2286 int is_fake_node=IsFakeNode(r->node);
2287 int is_super_node=is_fake_node?0:IsSuperNode(LookupNode(nodes,r->node,4));
2288 int is_no_segment=(r->segment==NO_SEGMENT);
2289 int is_fake_segment=is_no_segment?0:IsFakeSegment(r->segment);
2290 int is_super_segment=is_no_segment||is_fake_segment?0:IsSuperSegment(LookupSegment(segments,r->segment,4));
2291 int is_normal_segment=is_no_segment||is_fake_segment?0:IsNormalSegment(LookupSegment(segments,r->segment,4));
2292 int is_start=r->node==results->start_node&&r->segment==results->prev_segment;
2293 int is_finish=r->node==results->finish_node;
2294
2295 printf("%s %s node=%10"Pindex_t" segment=%10"Pindex_t" score=%8.3f (%s-node,%s-segment)%s%s\n",
2296 &spaces[8-indent],
2297 (is_start||is_finish?"*":(direction==-1?"^":"v")),
2298 r->node,r->segment,r->score,
2299 (is_fake_node?" fake":(is_super_node?" super":"normal")),
2300 (is_no_segment?" no":(is_fake_segment?" fake":(is_super_segment&&is_normal_segment?" both":(is_super_segment?" super":"normal")))),
2301 (is_start?" [start]":""),
2302 (is_finish?" [finish]":""));
2303
2304 if(direction==-1)
2305 r=r->prev;
2306 else
2307 r=r->next;
2308 }
2309 }
2310
2311 #endif
2312