1 /***************************************
2 $Header: /home/amb/routino/src/RCS/optimiser.c,v 1.93 2010/08/04 16:44:51 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 ***************************************/
32 #include "functions.h"
36 /*+ The option not to print any progress information. +*/
37 extern int option_quiet;
39 /*+ The option to calculate the quickest route insted of the shortest. +*/
40 extern int option_quickest;
43 /*++++++++++++++++++++++++++++++++++++++
44 Find the optimum route between two nodes not passing through a super-node.
46 Results *FindNormalRoute Returns a set of results.
48 Nodes *nodes The set of nodes to use.
50 Segments *segments The set of segments to use.
52 Ways *ways The set of ways to use.
54 index_t start The start node.
56 index_t finish The finish node.
58 Profile *profile The profile containing the transport type, speeds and allowed highways.
59 ++++++++++++++++++++++++++++++++++++++*/
61 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
67 double finish_lat,finish_lon;
68 Result *result1,*result2;
73 /* Set up the finish conditions */
75 finish_score=INF_SCORE;
77 if(IsFakeNode(finish))
78 GetFakeLatLong(finish,&finish_lat,&finish_lon);
80 GetLatLong(nodes,finish,&finish_lat,&finish_lon);
82 /* Create the list of results and insert the first node into the queue */
84 results=NewResultsList(8);
87 results->finish=finish;
89 result1=InsertResult(results,start);
95 InsertInQueue(queue,result1);
97 /* Loop across all nodes in the queue */
99 while((result1=PopFromQueue(queue)))
101 if(result1->score>finish_score)
106 if(IsFakeNode(node1))
107 segment=FirstFakeSegment(node1);
109 segment=FirstSegment(segments,nodes,node1);
113 score_t segment_pref,segment_score,cumulative_score;
116 node2=OtherNode(segment,node1); /* need this here because we use node2 later */
118 if(!IsNormalSegment(segment))
121 if(profile->oneway && IsOnewayTo(segment,node1))
124 if(result1->prev==node2)
127 if(node2!=finish && !IsFakeNode(node2) && IsSuperNode(nodes,node2))
130 way=LookupWay(ways,segment->way,1);
132 if(!(way->allow&profile->allow))
135 if(!profile->highway[HIGHWAY(way->type)])
138 if(way->weight && way->weight<profile->weight)
141 if((way->height && way->height<profile->height) ||
142 (way->width && way->width <profile->width ) ||
143 (way->length && way->length<profile->length))
146 segment_pref=profile->highway[HIGHWAY(way->type)];
148 for(i=1;i<Property_Count;i++)
149 if(ways->file.props & PROPERTIES(i))
151 if(way->props & PROPERTIES(i))
152 segment_pref*=profile->props_yes[i];
154 segment_pref*=profile->props_no[i];
160 if(!IsFakeNode(node2))
162 node=LookupNode(nodes,node2,1);
164 if(!(node->allow&profile->allow))
168 if(option_quickest==0)
169 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
171 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
173 cumulative_score=result1->score+segment_score;
175 if(cumulative_score>finish_score)
178 result2=FindResult(results,node2);
180 if(!result2) /* New end node */
182 result2=InsertResult(results,node2);
184 result2->next=NO_NODE;
185 result2->score=cumulative_score;
186 if(IsFakeNode(node1) || IsFakeNode(node2))
187 result2->segment=IndexFakeSegment(segment);
189 result2->segment=IndexSegment(segments,segment);
193 finish_score=cumulative_score;
197 result2->sortby=result2->score;
199 InsertInQueue(queue,result2);
202 else if(cumulative_score<result2->score) /* New end node is better */
205 result2->score=cumulative_score;
206 if(IsFakeNode(node1) || IsFakeNode(node2))
207 result2->segment=IndexFakeSegment(segment);
209 result2->segment=IndexSegment(segments,segment);
213 finish_score=cumulative_score;
217 result2->sortby=result2->score;
219 if(result2->score<finish_score)
220 InsertInQueue(queue,result2);
226 if(IsFakeNode(node1))
227 segment=NextFakeSegment(segment,node1);
228 else if(IsFakeNode(node2))
229 segment=NULL; /* cannot call NextSegment() with a fake segment */
232 segment=NextSegment(segments,segment,node1);
234 if(!segment && IsFakeNode(finish))
235 segment=ExtraFakeSegment(node1,finish);
240 FreeQueueList(queue);
242 /* Check it worked */
244 if(!FindResult(results,finish))
246 FreeResultsList(results);
250 FixForwardRoute(results,finish);
256 /*++++++++++++++++++++++++++++++++++++++
257 Find the optimum route between two nodes where the start and end are a set of pre-routed super-nodes.
259 Results *FindMiddleRoute Returns a set of results.
261 Nodes *nodes The set of nodes to use.
263 Segments *segments The set of segments to use.
265 Ways *ways The set of ways to use.
267 Results *begin The initial portion of the route.
269 Results *end The final portion of the route.
271 Profile *profile The profile containing the transport type, speeds and allowed highways.
272 ++++++++++++++++++++++++++++++++++++++*/
274 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
280 score_t finish_score;
281 double finish_lat,finish_lon;
282 Result *result1,*result2,*result3;
289 printf("Routing: Super-Nodes checked = 0");
293 /* Set up the finish conditions */
295 finish_score=INF_DISTANCE;
298 if(IsFakeNode(end->finish))
299 GetFakeLatLong(end->finish,&finish_lat,&finish_lon);
301 GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
303 /* Create the list of results and insert the first node into the queue */
305 results=NewResultsList(2048);
307 results->start=begin->start;
308 results->finish=end->finish;
310 result1=InsertResult(results,begin->start);
311 result3=FindResult(begin,begin->start);
315 queue=NewQueueList();
317 /* Insert the finish points of the beginning part of the path into the queue */
319 result3=FirstResult(begin);
323 if(result3->node!=begin->start && !IsFakeNode(result3->node) && IsSuperNode(nodes,result3->node))
325 result2=InsertResult(results,result3->node);
329 result2->prev=begin->start;
331 result2->sortby=result2->score;
333 InsertInQueue(queue,result2);
336 result3=NextResult(begin,result3);
340 InsertInQueue(queue,result1);
342 /* Loop across all nodes in the queue */
344 while((result1=PopFromQueue(queue)))
346 if(result1->score>finish_score)
351 segment=FirstSegment(segments,nodes,node1);
355 score_t segment_pref,segment_score,cumulative_score;
358 if(!IsSuperSegment(segment))
361 if(profile->oneway && IsOnewayTo(segment,node1))
364 node2=OtherNode(segment,node1);
366 if(result1->prev==node2)
369 way=LookupWay(ways,segment->way,1);
371 if(!(way->allow&profile->allow))
374 if(!profile->highway[HIGHWAY(way->type)])
377 if(way->weight && way->weight<profile->weight)
380 if((way->height && way->height<profile->height) ||
381 (way->width && way->width <profile->width ) ||
382 (way->length && way->length<profile->length))
385 segment_pref=profile->highway[HIGHWAY(way->type)];
387 for(i=1;i<Property_Count;i++)
388 if(ways->file.props & PROPERTIES(i))
390 if(way->props & PROPERTIES(i))
391 segment_pref*=profile->props_yes[i];
393 segment_pref*=profile->props_no[i];
399 node=LookupNode(nodes,node2,1);
401 if(!(node->allow&profile->allow))
404 if(option_quickest==0)
405 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
407 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
409 cumulative_score=result1->score+segment_score;
411 if(cumulative_score>finish_score)
414 result2=FindResult(results,node2);
416 if(!result2) /* New end node */
418 result2=InsertResult(results,node2);
420 result2->next=NO_NODE;
421 result2->score=cumulative_score;
422 result2->segment=IndexSegment(segments,segment);
424 if((result3=FindResult(end,node2)))
426 if((result2->score+result3->score)<finish_score)
428 finish_score=result2->score+result3->score;
437 GetLatLong(nodes,node2,&lat,&lon);
438 direct=Distance(lat,lon,finish_lat,finish_lon);
440 if(option_quickest==0)
441 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
443 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
445 InsertInQueue(queue,result2);
448 else if(cumulative_score<result2->score) /* New end node is better */
451 result2->score=cumulative_score;
452 result2->segment=IndexSegment(segments,segment);
454 if((result3=FindResult(end,node2)))
456 if((result2->score+result3->score)<finish_score)
458 finish_score=result2->score+result3->score;
462 else if(result2->score<finish_score)
467 GetLatLong(nodes,node2,&lat,&lon);
468 direct=Distance(lat,lon,finish_lat,finish_lon);
470 if(option_quickest==0)
471 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
473 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
475 InsertInQueue(queue,result2);
481 if(!option_quiet && !(results->number%10000))
483 printf("\rRouting: Super-Nodes checked = %d",results->number);
487 segment=NextSegment(segments,segment,node1);
493 printf("\rRouting: Super-Nodes checked = %d\n",results->number);
497 /* Finish off the end part of the route. */
499 if(!FindResult(results,end->finish) && end_prev!=NO_NODE)
501 result2=InsertResult(results,end->finish);
502 result3=FindResult(end,end->finish);
506 result2->prev=end_prev;
507 result2->score=finish_score;
510 FreeQueueList(queue);
512 /* Check it worked */
514 if(end_prev==NO_NODE)
516 FreeResultsList(results);
520 FixForwardRoute(results,end->finish);
526 /*++++++++++++++++++++++++++++++++++++++
527 Find all routes from a specified node to any super-node.
529 Results *FindStartRoutes Returns a set of results.
531 Nodes *nodes The set of nodes to use.
533 Segments *segments The set of segments to use.
535 Ways *ways The set of ways to use.
537 index_t start The start node.
539 Profile *profile The profile containing the transport type, speeds and allowed highways.
540 ++++++++++++++++++++++++++++++++++++++*/
542 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
547 Result *result1,*result2;
552 /* Insert the first node into the queue */
554 results=NewResultsList(8);
556 results->start=start;
558 result1=InsertResult(results,start);
562 queue=NewQueueList();
564 InsertInQueue(queue,result1);
566 /* Loop across all nodes in the queue */
568 while((result1=PopFromQueue(queue)))
572 if(IsFakeNode(node1))
573 segment=FirstFakeSegment(node1);
575 segment=FirstSegment(segments,nodes,node1);
579 score_t segment_pref,segment_score,cumulative_score;
582 if(!IsNormalSegment(segment))
585 if(profile->oneway && IsOnewayTo(segment,node1))
588 node2=OtherNode(segment,node1);
590 if(result1->prev==node2)
593 way=LookupWay(ways,segment->way,1);
595 if(!(way->allow&profile->allow))
598 if(!profile->highway[HIGHWAY(way->type)])
601 if(way->weight && way->weight<profile->weight)
604 if((way->height && way->height<profile->height) ||
605 (way->width && way->width <profile->width ) ||
606 (way->length && way->length<profile->length))
609 segment_pref=profile->highway[HIGHWAY(way->type)];
611 for(i=1;i<Property_Count;i++)
612 if(ways->file.props & PROPERTIES(i))
614 if(way->props & PROPERTIES(i))
615 segment_pref*=profile->props_yes[i];
617 segment_pref*=profile->props_no[i];
623 if(!IsFakeNode(node2))
625 node=LookupNode(nodes,node2,1);
627 if(!(node->allow&profile->allow))
631 if(option_quickest==0)
632 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
634 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
636 cumulative_score=result1->score+segment_score;
638 result2=FindResult(results,node2);
640 if(!result2) /* New end node */
642 result2=InsertResult(results,node2);
644 result2->next=NO_NODE;
645 result2->score=cumulative_score;
646 if(IsFakeNode(node1) || IsFakeNode(node2))
647 result2->segment=IndexFakeSegment(segment);
649 result2->segment=IndexSegment(segments,segment);
651 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
653 result2->sortby=result2->score;
654 InsertInQueue(queue,result2);
657 else if(cumulative_score<result2->score) /* New end node is better */
660 result2->score=cumulative_score;
661 if(IsFakeNode(node1) || IsFakeNode(node2))
662 result2->segment=IndexFakeSegment(segment);
664 result2->segment=IndexSegment(segments,segment);
666 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
668 result2->sortby=result2->score;
669 InsertInQueue(queue,result2);
675 if(IsFakeNode(node1))
676 segment=NextFakeSegment(segment,node1);
678 segment=NextSegment(segments,segment,node1);
682 FreeQueueList(queue);
684 /* Check it worked */
686 if(results->number==1)
688 FreeResultsList(results);
696 /*++++++++++++++++++++++++++++++++++++++
697 Find all routes from any super-node to a specific node.
699 Results *FindFinishRoutes Returns a set of results.
701 Nodes *nodes The set of nodes to use.
703 Segments *segments The set of segments to use.
705 Ways *ways The set of ways to use.
707 index_t finish The finishing node.
709 Profile *profile The profile containing the transport type, speeds and allowed highways.
710 ++++++++++++++++++++++++++++++++++++++*/
712 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
717 Result *result1,*result2;
722 /* Insert the first node into the queue */
724 results=NewResultsList(8);
726 results->finish=finish;
728 result1=InsertResult(results,finish);
732 queue=NewQueueList();
734 InsertInQueue(queue,result1);
736 /* Loop across all nodes in the queue */
738 while((result1=PopFromQueue(queue)))
742 if(IsFakeNode(node1))
743 segment=FirstFakeSegment(node1);
745 segment=FirstSegment(segments,nodes,node1);
749 score_t segment_pref,segment_score,cumulative_score;
752 if(!IsNormalSegment(segment))
755 if(profile->oneway && IsOnewayFrom(segment,node1))
758 node2=OtherNode(segment,node1);
760 if(result1->next==node2)
763 way=LookupWay(ways,segment->way,1);
765 if(!(way->allow&profile->allow))
768 if(!profile->highway[HIGHWAY(way->type)])
771 if(way->weight && way->weight<profile->weight)
774 if((way->height && way->height<profile->height) ||
775 (way->width && way->width <profile->width ) ||
776 (way->length && way->length<profile->length))
779 segment_pref=profile->highway[HIGHWAY(way->type)];
781 for(i=1;i<Property_Count;i++)
782 if(ways->file.props & PROPERTIES(i))
784 if(way->props & PROPERTIES(i))
785 segment_pref*=profile->props_yes[i];
787 segment_pref*=profile->props_no[i];
793 if(!IsFakeNode(node2))
795 node=LookupNode(nodes,node2,1);
797 if(!(node->allow&profile->allow))
801 if(option_quickest==0)
802 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
804 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
806 cumulative_score=result1->score+segment_score;
808 result2=FindResult(results,node2);
810 if(!result2) /* New end node */
812 result2=InsertResult(results,node2);
813 result2->prev=NO_NODE;
815 result2->score=cumulative_score;
816 if(IsFakeNode(node1) || IsFakeNode(node2))
817 result2->segment=IndexFakeSegment(segment);
819 result2->segment=IndexSegment(segments,segment);
821 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
823 result2->sortby=result2->score;
824 InsertInQueue(queue,result2);
827 else if(cumulative_score<result2->score) /* New end node is better */
830 result2->score=cumulative_score;
831 if(IsFakeNode(node1) || IsFakeNode(node2))
832 result2->segment=IndexFakeSegment(segment);
834 result2->segment=IndexSegment(segments,segment);
836 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
838 result2->sortby=result2->score;
839 InsertInQueue(queue,result2);
845 if(IsFakeNode(node1))
846 segment=NextFakeSegment(segment,node1);
848 segment=NextSegment(segments,segment,node1);
852 FreeQueueList(queue);
854 /* Check it worked */
856 if(results->number==1)
858 FreeResultsList(results);
866 /*++++++++++++++++++++++++++++++++++++++
867 Create an optimum route given the set of super-nodes to follow.
869 Results *CombineRoutes Returns the results from joining the super-nodes.
871 Results *results The set of results from the super-nodes.
873 Nodes *nodes The list of nodes.
875 Segments *segments The set of segments to use.
877 Ways *ways The list of ways.
879 Profile *profile The profile containing the transport type, speeds and allowed highways.
880 ++++++++++++++++++++++++++++++++++++++*/
882 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
884 Result *result1,*result2,*result3,*result4;
887 combined=NewResultsList(64);
889 combined->start=results->start;
890 combined->finish=results->finish;
892 /* Sort out the combined route */
894 result1=FindResult(results,results->start);
896 result3=InsertResult(combined,results->start);
902 if(result1->next!=NO_NODE)
904 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
906 result2=FindResult(results2,result1->node);
908 result3->next=result2->next;
910 result2=FindResult(results2,result2->next);
914 result4=InsertResult(combined,result2->node);
917 result4->score+=result3->score;
919 if(result2->next!=NO_NODE)
920 result2=FindResult(results2,result2->next);
926 FreeResultsList(results2);
928 result1=FindResult(results,result1->next);
941 /*++++++++++++++++++++++++++++++++++++++
942 Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
944 Results *results The set of results to update.
946 index_t finish The finish point.
947 ++++++++++++++++++++++++++++++++++++++*/
949 void FixForwardRoute(Results *results,index_t finish)
951 Result *result2=FindResult(results,finish);
954 /* Create the forward links for the optimum path */
958 if(result2->prev!=NO_NODE)
960 index_t node1=result2->prev;
962 result1=FindResult(results,node1);
964 result1->next=result2->node;
973 results->finish=finish;