1 /***************************************
2 $Header: /home/amb/routino/src/RCS/optimiser.c,v 1.94 2010/11/13 14:22:28 amb Exp $
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Affero General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU Affero General Public License for more details.
20 You should have received a copy of the GNU Affero General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 ***************************************/
33 #include "functions.h"
37 /*+ The option not to print any progress information. +*/
38 extern int option_quiet;
40 /*+ The option to calculate the quickest route insted of the shortest. +*/
41 extern int option_quickest;
44 /*++++++++++++++++++++++++++++++++++++++
45 Find the optimum route between two nodes not passing through a super-node.
47 Results *FindNormalRoute Returns a set of results.
49 Nodes *nodes The set of nodes to use.
51 Segments *segments The set of segments to use.
53 Ways *ways The set of ways to use.
55 index_t start The start node.
57 index_t finish The finish node.
59 Profile *profile The profile containing the transport type, speeds and allowed highways.
60 ++++++++++++++++++++++++++++++++++++++*/
62 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
68 double finish_lat,finish_lon;
69 Result *result1,*result2;
74 /* Set up the finish conditions */
76 finish_score=INF_SCORE;
78 if(IsFakeNode(finish))
79 GetFakeLatLong(finish,&finish_lat,&finish_lon);
81 GetLatLong(nodes,finish,&finish_lat,&finish_lon);
83 /* Create the list of results and insert the first node into the queue */
85 results=NewResultsList(8);
88 results->finish=finish;
90 result1=InsertResult(results,start);
96 InsertInQueue(queue,result1);
98 /* Loop across all nodes in the queue */
100 while((result1=PopFromQueue(queue)))
102 if(result1->score>finish_score)
107 if(IsFakeNode(node1))
108 segment=FirstFakeSegment(node1);
110 segment=FirstSegment(segments,nodes,node1);
114 score_t segment_pref,segment_score,cumulative_score;
117 node2=OtherNode(segment,node1); /* need this here because we use node2 later */
119 if(!IsNormalSegment(segment))
122 if(profile->oneway && IsOnewayTo(segment,node1))
125 if(result1->prev==node2)
128 if(node2!=finish && !IsFakeNode(node2) && IsSuperNode(nodes,node2))
131 way=LookupWay(ways,segment->way,1);
133 if(!(way->allow&profile->allow))
136 if(!profile->highway[HIGHWAY(way->type)])
139 if(way->weight && way->weight<profile->weight)
142 if((way->height && way->height<profile->height) ||
143 (way->width && way->width <profile->width ) ||
144 (way->length && way->length<profile->length))
147 segment_pref=profile->highway[HIGHWAY(way->type)];
149 for(i=1;i<Property_Count;i++)
150 if(ways->file.props & PROPERTIES(i))
152 if(way->props & PROPERTIES(i))
153 segment_pref*=profile->props_yes[i];
155 segment_pref*=profile->props_no[i];
161 if(!IsFakeNode(node2))
163 node=LookupNode(nodes,node2,1);
165 if(!(node->allow&profile->allow))
169 if(option_quickest==0)
170 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
172 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
174 cumulative_score=result1->score+segment_score;
176 if(cumulative_score>finish_score)
179 result2=FindResult(results,node2);
181 if(!result2) /* New end node */
183 result2=InsertResult(results,node2);
185 result2->next=NO_NODE;
186 result2->score=cumulative_score;
187 if(IsFakeNode(node1) || IsFakeNode(node2))
188 result2->segment=IndexFakeSegment(segment);
190 result2->segment=IndexSegment(segments,segment);
194 finish_score=cumulative_score;
198 result2->sortby=result2->score;
200 InsertInQueue(queue,result2);
203 else if(cumulative_score<result2->score) /* New end node is better */
206 result2->score=cumulative_score;
207 if(IsFakeNode(node1) || IsFakeNode(node2))
208 result2->segment=IndexFakeSegment(segment);
210 result2->segment=IndexSegment(segments,segment);
214 finish_score=cumulative_score;
218 result2->sortby=result2->score;
220 if(result2->score<finish_score)
221 InsertInQueue(queue,result2);
227 if(IsFakeNode(node1))
228 segment=NextFakeSegment(segment,node1);
229 else if(IsFakeNode(node2))
230 segment=NULL; /* cannot call NextSegment() with a fake segment */
233 segment=NextSegment(segments,segment,node1);
235 if(!segment && IsFakeNode(finish))
236 segment=ExtraFakeSegment(node1,finish);
241 FreeQueueList(queue);
243 /* Check it worked */
245 if(!FindResult(results,finish))
247 FreeResultsList(results);
251 FixForwardRoute(results,finish);
257 /*++++++++++++++++++++++++++++++++++++++
258 Find the optimum route between two nodes where the start and end are a set of pre-routed super-nodes.
260 Results *FindMiddleRoute Returns a set of results.
262 Nodes *nodes The set of nodes to use.
264 Segments *segments The set of segments to use.
266 Ways *ways The set of ways to use.
268 Results *begin The initial portion of the route.
270 Results *end The final portion of the route.
272 Profile *profile The profile containing the transport type, speeds and allowed highways.
273 ++++++++++++++++++++++++++++++++++++++*/
275 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
281 score_t finish_score;
282 double finish_lat,finish_lon;
283 Result *result1,*result2,*result3;
289 printf_first("Routing: Super-Nodes checked = 0");
291 /* Set up the finish conditions */
293 finish_score=INF_DISTANCE;
296 if(IsFakeNode(end->finish))
297 GetFakeLatLong(end->finish,&finish_lat,&finish_lon);
299 GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
301 /* Create the list of results and insert the first node into the queue */
303 results=NewResultsList(2048);
305 results->start=begin->start;
306 results->finish=end->finish;
308 result1=InsertResult(results,begin->start);
309 result3=FindResult(begin,begin->start);
313 queue=NewQueueList();
315 /* Insert the finish points of the beginning part of the path into the queue */
317 result3=FirstResult(begin);
321 if(result3->node!=begin->start && !IsFakeNode(result3->node) && IsSuperNode(nodes,result3->node))
323 result2=InsertResult(results,result3->node);
327 result2->prev=begin->start;
329 result2->sortby=result2->score;
331 InsertInQueue(queue,result2);
334 result3=NextResult(begin,result3);
338 InsertInQueue(queue,result1);
340 /* Loop across all nodes in the queue */
342 while((result1=PopFromQueue(queue)))
344 if(result1->score>finish_score)
349 segment=FirstSegment(segments,nodes,node1);
353 score_t segment_pref,segment_score,cumulative_score;
356 if(!IsSuperSegment(segment))
359 if(profile->oneway && IsOnewayTo(segment,node1))
362 node2=OtherNode(segment,node1);
364 if(result1->prev==node2)
367 way=LookupWay(ways,segment->way,1);
369 if(!(way->allow&profile->allow))
372 if(!profile->highway[HIGHWAY(way->type)])
375 if(way->weight && way->weight<profile->weight)
378 if((way->height && way->height<profile->height) ||
379 (way->width && way->width <profile->width ) ||
380 (way->length && way->length<profile->length))
383 segment_pref=profile->highway[HIGHWAY(way->type)];
385 for(i=1;i<Property_Count;i++)
386 if(ways->file.props & PROPERTIES(i))
388 if(way->props & PROPERTIES(i))
389 segment_pref*=profile->props_yes[i];
391 segment_pref*=profile->props_no[i];
397 node=LookupNode(nodes,node2,1);
399 if(!(node->allow&profile->allow))
402 if(option_quickest==0)
403 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
405 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
407 cumulative_score=result1->score+segment_score;
409 if(cumulative_score>finish_score)
412 result2=FindResult(results,node2);
414 if(!result2) /* New end node */
416 result2=InsertResult(results,node2);
418 result2->next=NO_NODE;
419 result2->score=cumulative_score;
420 result2->segment=IndexSegment(segments,segment);
422 if((result3=FindResult(end,node2)))
424 if((result2->score+result3->score)<finish_score)
426 finish_score=result2->score+result3->score;
435 GetLatLong(nodes,node2,&lat,&lon);
436 direct=Distance(lat,lon,finish_lat,finish_lon);
438 if(option_quickest==0)
439 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
441 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
443 InsertInQueue(queue,result2);
446 else if(cumulative_score<result2->score) /* New end node is better */
449 result2->score=cumulative_score;
450 result2->segment=IndexSegment(segments,segment);
452 if((result3=FindResult(end,node2)))
454 if((result2->score+result3->score)<finish_score)
456 finish_score=result2->score+result3->score;
460 else if(result2->score<finish_score)
465 GetLatLong(nodes,node2,&lat,&lon);
466 direct=Distance(lat,lon,finish_lat,finish_lon);
468 if(option_quickest==0)
469 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
471 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
473 InsertInQueue(queue,result2);
479 if(!option_quiet && !(results->number%10000))
480 printf_middle("Routing: Super-Nodes checked = %d",results->number);
482 segment=NextSegment(segments,segment,node1);
487 printf_last("Routing: Super-Nodes checked = %d",results->number);
489 /* Finish off the end part of the route. */
491 if(!FindResult(results,end->finish) && end_prev!=NO_NODE)
493 result2=InsertResult(results,end->finish);
494 result3=FindResult(end,end->finish);
498 result2->prev=end_prev;
499 result2->score=finish_score;
502 FreeQueueList(queue);
504 /* Check it worked */
506 if(end_prev==NO_NODE)
508 FreeResultsList(results);
512 FixForwardRoute(results,end->finish);
518 /*++++++++++++++++++++++++++++++++++++++
519 Find all routes from a specified node to any super-node.
521 Results *FindStartRoutes Returns a set of results.
523 Nodes *nodes The set of nodes to use.
525 Segments *segments The set of segments to use.
527 Ways *ways The set of ways to use.
529 index_t start The start node.
531 Profile *profile The profile containing the transport type, speeds and allowed highways.
532 ++++++++++++++++++++++++++++++++++++++*/
534 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
539 Result *result1,*result2;
544 /* Insert the first node into the queue */
546 results=NewResultsList(8);
548 results->start=start;
550 result1=InsertResult(results,start);
554 queue=NewQueueList();
556 InsertInQueue(queue,result1);
558 /* Loop across all nodes in the queue */
560 while((result1=PopFromQueue(queue)))
564 if(IsFakeNode(node1))
565 segment=FirstFakeSegment(node1);
567 segment=FirstSegment(segments,nodes,node1);
571 score_t segment_pref,segment_score,cumulative_score;
574 if(!IsNormalSegment(segment))
577 if(profile->oneway && IsOnewayTo(segment,node1))
580 node2=OtherNode(segment,node1);
582 if(result1->prev==node2)
585 way=LookupWay(ways,segment->way,1);
587 if(!(way->allow&profile->allow))
590 if(!profile->highway[HIGHWAY(way->type)])
593 if(way->weight && way->weight<profile->weight)
596 if((way->height && way->height<profile->height) ||
597 (way->width && way->width <profile->width ) ||
598 (way->length && way->length<profile->length))
601 segment_pref=profile->highway[HIGHWAY(way->type)];
603 for(i=1;i<Property_Count;i++)
604 if(ways->file.props & PROPERTIES(i))
606 if(way->props & PROPERTIES(i))
607 segment_pref*=profile->props_yes[i];
609 segment_pref*=profile->props_no[i];
615 if(!IsFakeNode(node2))
617 node=LookupNode(nodes,node2,1);
619 if(!(node->allow&profile->allow))
623 if(option_quickest==0)
624 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
626 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
628 cumulative_score=result1->score+segment_score;
630 result2=FindResult(results,node2);
632 if(!result2) /* New end node */
634 result2=InsertResult(results,node2);
636 result2->next=NO_NODE;
637 result2->score=cumulative_score;
638 if(IsFakeNode(node1) || IsFakeNode(node2))
639 result2->segment=IndexFakeSegment(segment);
641 result2->segment=IndexSegment(segments,segment);
643 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
645 result2->sortby=result2->score;
646 InsertInQueue(queue,result2);
649 else if(cumulative_score<result2->score) /* New end node is better */
652 result2->score=cumulative_score;
653 if(IsFakeNode(node1) || IsFakeNode(node2))
654 result2->segment=IndexFakeSegment(segment);
656 result2->segment=IndexSegment(segments,segment);
658 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
660 result2->sortby=result2->score;
661 InsertInQueue(queue,result2);
667 if(IsFakeNode(node1))
668 segment=NextFakeSegment(segment,node1);
670 segment=NextSegment(segments,segment,node1);
674 FreeQueueList(queue);
676 /* Check it worked */
678 if(results->number==1)
680 FreeResultsList(results);
688 /*++++++++++++++++++++++++++++++++++++++
689 Find all routes from any super-node to a specific node.
691 Results *FindFinishRoutes Returns a set of results.
693 Nodes *nodes The set of nodes to use.
695 Segments *segments The set of segments to use.
697 Ways *ways The set of ways to use.
699 index_t finish The finishing node.
701 Profile *profile The profile containing the transport type, speeds and allowed highways.
702 ++++++++++++++++++++++++++++++++++++++*/
704 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
709 Result *result1,*result2;
714 /* Insert the first node into the queue */
716 results=NewResultsList(8);
718 results->finish=finish;
720 result1=InsertResult(results,finish);
724 queue=NewQueueList();
726 InsertInQueue(queue,result1);
728 /* Loop across all nodes in the queue */
730 while((result1=PopFromQueue(queue)))
734 if(IsFakeNode(node1))
735 segment=FirstFakeSegment(node1);
737 segment=FirstSegment(segments,nodes,node1);
741 score_t segment_pref,segment_score,cumulative_score;
744 if(!IsNormalSegment(segment))
747 if(profile->oneway && IsOnewayFrom(segment,node1))
750 node2=OtherNode(segment,node1);
752 if(result1->next==node2)
755 way=LookupWay(ways,segment->way,1);
757 if(!(way->allow&profile->allow))
760 if(!profile->highway[HIGHWAY(way->type)])
763 if(way->weight && way->weight<profile->weight)
766 if((way->height && way->height<profile->height) ||
767 (way->width && way->width <profile->width ) ||
768 (way->length && way->length<profile->length))
771 segment_pref=profile->highway[HIGHWAY(way->type)];
773 for(i=1;i<Property_Count;i++)
774 if(ways->file.props & PROPERTIES(i))
776 if(way->props & PROPERTIES(i))
777 segment_pref*=profile->props_yes[i];
779 segment_pref*=profile->props_no[i];
785 if(!IsFakeNode(node2))
787 node=LookupNode(nodes,node2,1);
789 if(!(node->allow&profile->allow))
793 if(option_quickest==0)
794 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
796 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
798 cumulative_score=result1->score+segment_score;
800 result2=FindResult(results,node2);
802 if(!result2) /* New end node */
804 result2=InsertResult(results,node2);
805 result2->prev=NO_NODE;
807 result2->score=cumulative_score;
808 if(IsFakeNode(node1) || IsFakeNode(node2))
809 result2->segment=IndexFakeSegment(segment);
811 result2->segment=IndexSegment(segments,segment);
813 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
815 result2->sortby=result2->score;
816 InsertInQueue(queue,result2);
819 else if(cumulative_score<result2->score) /* New end node is better */
822 result2->score=cumulative_score;
823 if(IsFakeNode(node1) || IsFakeNode(node2))
824 result2->segment=IndexFakeSegment(segment);
826 result2->segment=IndexSegment(segments,segment);
828 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
830 result2->sortby=result2->score;
831 InsertInQueue(queue,result2);
837 if(IsFakeNode(node1))
838 segment=NextFakeSegment(segment,node1);
840 segment=NextSegment(segments,segment,node1);
844 FreeQueueList(queue);
846 /* Check it worked */
848 if(results->number==1)
850 FreeResultsList(results);
858 /*++++++++++++++++++++++++++++++++++++++
859 Create an optimum route given the set of super-nodes to follow.
861 Results *CombineRoutes Returns the results from joining the super-nodes.
863 Results *results The set of results from the super-nodes.
865 Nodes *nodes The list of nodes.
867 Segments *segments The set of segments to use.
869 Ways *ways The list of ways.
871 Profile *profile The profile containing the transport type, speeds and allowed highways.
872 ++++++++++++++++++++++++++++++++++++++*/
874 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
876 Result *result1,*result2,*result3,*result4;
879 combined=NewResultsList(64);
881 combined->start=results->start;
882 combined->finish=results->finish;
884 /* Sort out the combined route */
886 result1=FindResult(results,results->start);
888 result3=InsertResult(combined,results->start);
894 if(result1->next!=NO_NODE)
896 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
898 result2=FindResult(results2,result1->node);
900 result3->next=result2->next;
902 result2=FindResult(results2,result2->next);
906 result4=InsertResult(combined,result2->node);
909 result4->score+=result3->score;
911 if(result2->next!=NO_NODE)
912 result2=FindResult(results2,result2->next);
918 FreeResultsList(results2);
920 result1=FindResult(results,result1->next);
933 /*++++++++++++++++++++++++++++++++++++++
934 Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
936 Results *results The set of results to update.
938 index_t finish The finish point.
939 ++++++++++++++++++++++++++++++++++++++*/
941 void FixForwardRoute(Results *results,index_t finish)
943 Result *result2=FindResult(results,finish);
946 /* Create the forward links for the optimum path */
950 if(result2->prev!=NO_NODE)
952 index_t node1=result2->prev;
954 result1=FindResult(results,node1);
956 result1->next=result2->node;
965 results->finish=finish;