1 /***************************************
2 $Header: /home/amb/routino/src/RCS/optimiser.c,v 1.87 2010/07/08 17:33:09 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 ***************************************/
28 #include "functions.h"
35 /*+ The option not to print any progress information. +*/
36 extern int option_quiet;
38 /*+ The option to calculate the quickest route insted of the shortest. +*/
39 extern int option_quickest;
42 /*++++++++++++++++++++++++++++++++++++++
43 Find the optimum route between two nodes not passing through a super-node.
45 Results *FindNormalRoute Returns a set of results.
47 Nodes *nodes The set of nodes to use.
49 Segments *segments The set of segments to use.
51 Ways *ways The set of ways to use.
53 index_t start The start node.
55 index_t finish The finish node.
57 Profile *profile The profile containing the transport type, speeds and allowed highways.
58 ++++++++++++++++++++++++++++++++++++++*/
60 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
66 double finish_lat,finish_lon;
67 Result *result1,*result2;
71 /* Set up the finish conditions */
73 finish_score=INF_SCORE;
75 if(IsFakeNode(finish))
76 GetFakeLatLong(finish,&finish_lat,&finish_lon);
78 GetLatLong(nodes,finish,&finish_lat,&finish_lon);
80 /* Create the list of results and insert the first node into the queue */
82 results=NewResultsList(8);
85 results->finish=finish;
87 result1=InsertResult(results,start);
93 InsertInQueue(queue,result1);
95 /* Loop across all nodes in the queue */
97 while((result1=PopFromQueue(queue)))
99 if(result1->score>finish_score)
104 if(IsFakeNode(node1))
105 segment=FirstFakeSegment(node1);
107 segment=FirstSegment(segments,nodes,node1);
111 score_t segment_pref,segment_score,cumulative_score;
114 node2=OtherNode(segment,node1); /* need this here because we use node2 later */
116 if(!IsNormalSegment(segment))
119 if(profile->oneway && IsOnewayTo(segment,node1))
122 if(result1->prev==node2)
125 if(node2!=finish && !IsFakeNode(node2) && IsSuperNode(nodes,node2))
128 way=LookupWay(ways,segment->way);
130 if(!(way->allow&profile->allow))
133 if(!profile->highway[HIGHWAY(way->type)])
136 if(way->weight && way->weight<profile->weight)
139 if((way->height && way->height<profile->height) ||
140 (way->width && way->width <profile->width ) ||
141 (way->length && way->length<profile->length))
144 segment_pref=profile->highway[HIGHWAY(way->type)];
146 for(i=1;i<Property_Count;i++)
147 if(ways->props & PROPERTIES(i))
149 if(way->props & PROPERTIES(i))
150 segment_pref*=profile->props_yes[i];
152 segment_pref*=profile->props_no[i];
158 if(option_quickest==0)
159 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
161 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
163 cumulative_score=result1->score+segment_score;
165 if(cumulative_score>finish_score)
168 result2=FindResult(results,node2);
170 if(!result2) /* New end node */
172 result2=InsertResult(results,node2);
174 result2->next=NO_NODE;
175 result2->score=cumulative_score;
176 result2->segment=segment;
180 finish_score=cumulative_score;
184 result2->sortby=result2->score;
186 InsertInQueue(queue,result2);
189 else if(cumulative_score<result2->score) /* New end node is better */
192 result2->score=cumulative_score;
193 result2->segment=segment;
197 finish_score=cumulative_score;
201 result2->sortby=result2->score;
203 if(result2->score<finish_score)
204 InsertInQueue(queue,result2);
210 if(IsFakeNode(node1))
211 segment=NextFakeSegment(segment,node1);
212 else if(IsFakeNode(node2))
213 segment=NULL; /* cannot call NextSegment() with a fake segment */
216 segment=NextSegment(segments,segment,node1);
218 if(!segment && IsFakeNode(finish))
219 segment=ExtraFakeSegment(node1,finish);
224 FreeQueueList(queue);
226 /* Check it worked */
228 if(!FindResult(results,finish))
230 FreeResultsList(results);
234 FixForwardRoute(results,finish);
240 /*++++++++++++++++++++++++++++++++++++++
241 Find the optimum route between two nodes where the start and end are a set of pre-routed super-nodes.
243 Results *FindMiddleRoute Returns a set of results.
245 Nodes *nodes The set of nodes to use.
247 Segments *segments The set of segments to use.
249 Ways *ways The set of ways to use.
251 Results *begin The initial portion of the route.
253 Results *end The final portion of the route.
255 Profile *profile The profile containing the transport type, speeds and allowed highways.
256 ++++++++++++++++++++++++++++++++++++++*/
258 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
264 score_t finish_score;
265 double finish_lat,finish_lon;
266 Result *result1,*result2,*result3;
272 printf("Routing: Super-Nodes checked = 0");
276 /* Set up the finish conditions */
278 finish_score=INF_DISTANCE;
281 if(IsFakeNode(end->finish))
282 GetFakeLatLong(end->finish,&finish_lat,&finish_lon);
284 GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
286 /* Create the list of results and insert the first node into the queue */
288 results=NewResultsList(2048);
290 results->start=begin->start;
291 results->finish=end->finish;
293 result1=InsertResult(results,begin->start);
294 result3=FindResult(begin,begin->start);
298 queue=NewQueueList();
300 /* Insert the finish points of the beginning part of the path into the queue */
302 result3=FirstResult(begin);
306 if(result3->node!=begin->start && !IsFakeNode(result3->node) && IsSuperNode(nodes,result3->node))
308 result2=InsertResult(results,result3->node);
312 result2->prev=begin->start;
314 result2->sortby=result2->score;
316 InsertInQueue(queue,result2);
319 result3=NextResult(begin,result3);
323 InsertInQueue(queue,result1);
325 /* Loop across all nodes in the queue */
327 while((result1=PopFromQueue(queue)))
329 if(result1->score>finish_score)
334 segment=FirstSegment(segments,nodes,node1);
338 score_t segment_pref,segment_score,cumulative_score;
341 if(!IsSuperSegment(segment))
344 if(profile->oneway && IsOnewayTo(segment,node1))
347 node2=OtherNode(segment,node1);
349 if(result1->prev==node2)
352 way=LookupWay(ways,segment->way);
354 if(!(way->allow&profile->allow))
357 if(!profile->highway[HIGHWAY(way->type)])
360 if(way->weight && way->weight<profile->weight)
363 if((way->height && way->height<profile->height) ||
364 (way->width && way->width <profile->width ) ||
365 (way->length && way->length<profile->length))
368 segment_pref=profile->highway[HIGHWAY(way->type)];
370 for(i=1;i<Property_Count;i++)
371 if(ways->props & PROPERTIES(i))
373 if(way->props & PROPERTIES(i))
374 segment_pref*=profile->props_yes[i];
376 segment_pref*=profile->props_no[i];
382 if(option_quickest==0)
383 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
385 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
387 cumulative_score=result1->score+segment_score;
389 if(cumulative_score>finish_score)
392 result2=FindResult(results,node2);
394 if(!result2) /* New end node */
396 result2=InsertResult(results,node2);
398 result2->next=NO_NODE;
399 result2->score=cumulative_score;
400 result2->segment=segment;
402 if((result3=FindResult(end,node2)))
404 if((result2->score+result3->score)<finish_score)
406 finish_score=result2->score+result3->score;
415 GetLatLong(nodes,node2,&lat,&lon);
416 direct=Distance(lat,lon,finish_lat,finish_lon);
418 if(option_quickest==0)
419 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
421 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
423 InsertInQueue(queue,result2);
426 else if(cumulative_score<result2->score) /* New end node is better */
429 result2->score=cumulative_score;
430 result2->segment=segment;
432 if((result3=FindResult(end,node2)))
434 if((result2->score+result3->score)<finish_score)
436 finish_score=result2->score+result3->score;
440 else if(result2->score<finish_score)
445 GetLatLong(nodes,node2,&lat,&lon);
446 direct=Distance(lat,lon,finish_lat,finish_lon);
448 if(option_quickest==0)
449 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
451 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
453 InsertInQueue(queue,result2);
459 if(!option_quiet && !(results->number%10000))
461 printf("\rRouting: Super-Nodes checked = %d",results->number);
465 segment=NextSegment(segments,segment,node1);
471 printf("\rRouting: Super-Nodes checked = %d\n",results->number);
475 /* Finish off the end part of the route. */
477 if(!FindResult(results,end->finish) && end_prev!=NO_NODE)
479 result2=InsertResult(results,end->finish);
480 result3=FindResult(end,end->finish);
484 result2->prev=end_prev;
485 result2->score=finish_score;
488 FreeQueueList(queue);
490 /* Check it worked */
492 if(end_prev==NO_NODE)
494 FreeResultsList(results);
498 FixForwardRoute(results,end->finish);
504 /*++++++++++++++++++++++++++++++++++++++
505 Find all routes from a specified node to any super-node.
507 Results *FindStartRoutes Returns a set of results.
509 Nodes *nodes The set of nodes to use.
511 Segments *segments The set of segments to use.
513 Ways *ways The set of ways to use.
515 index_t start The start node.
517 Profile *profile The profile containing the transport type, speeds and allowed highways.
518 ++++++++++++++++++++++++++++++++++++++*/
520 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
525 Result *result1,*result2;
529 /* Insert the first node into the queue */
531 results=NewResultsList(8);
533 results->start=start;
535 result1=InsertResult(results,start);
539 queue=NewQueueList();
541 InsertInQueue(queue,result1);
543 /* Loop across all nodes in the queue */
545 while((result1=PopFromQueue(queue)))
549 if(IsFakeNode(node1))
550 segment=FirstFakeSegment(node1);
552 segment=FirstSegment(segments,nodes,node1);
556 score_t segment_pref,segment_score,cumulative_score;
559 if(!IsNormalSegment(segment))
562 if(profile->oneway && IsOnewayTo(segment,node1))
565 node2=OtherNode(segment,node1);
567 if(result1->prev==node2)
570 way=LookupWay(ways,segment->way);
572 if(!(way->allow&profile->allow))
575 if(!profile->highway[HIGHWAY(way->type)])
578 if(way->weight && way->weight<profile->weight)
581 if((way->height && way->height<profile->height) ||
582 (way->width && way->width <profile->width ) ||
583 (way->length && way->length<profile->length))
586 segment_pref=profile->highway[HIGHWAY(way->type)];
588 for(i=1;i<Property_Count;i++)
589 if(ways->props & PROPERTIES(i))
591 if(way->props & PROPERTIES(i))
592 segment_pref*=profile->props_yes[i];
594 segment_pref*=profile->props_no[i];
600 if(option_quickest==0)
601 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
603 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
605 cumulative_score=result1->score+segment_score;
607 result2=FindResult(results,node2);
609 if(!result2) /* New end node */
611 result2=InsertResult(results,node2);
613 result2->next=NO_NODE;
614 result2->score=cumulative_score;
615 result2->segment=segment;
617 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
619 result2->sortby=result2->score;
620 InsertInQueue(queue,result2);
623 else if(cumulative_score<result2->score) /* New end node is better */
626 result2->score=cumulative_score;
627 result2->segment=segment;
629 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
631 result2->sortby=result2->score;
632 InsertInQueue(queue,result2);
638 if(IsFakeNode(node1))
639 segment=NextFakeSegment(segment,node1);
641 segment=NextSegment(segments,segment,node1);
645 FreeQueueList(queue);
647 /* Check it worked */
649 if(results->number==1)
651 FreeResultsList(results);
659 /*++++++++++++++++++++++++++++++++++++++
660 Find all routes from any super-node to a specific node.
662 Results *FindFinishRoutes Returns a set of results.
664 Nodes *nodes The set of nodes to use.
666 Segments *segments The set of segments to use.
668 Ways *ways The set of ways to use.
670 index_t finish The finishing node.
672 Profile *profile The profile containing the transport type, speeds and allowed highways.
673 ++++++++++++++++++++++++++++++++++++++*/
675 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
680 Result *result1,*result2;
684 /* Insert the first node into the queue */
686 results=NewResultsList(8);
688 results->finish=finish;
690 result1=InsertResult(results,finish);
694 queue=NewQueueList();
696 InsertInQueue(queue,result1);
698 /* Loop across all nodes in the queue */
700 while((result1=PopFromQueue(queue)))
704 if(IsFakeNode(node1))
705 segment=FirstFakeSegment(node1);
707 segment=FirstSegment(segments,nodes,node1);
711 score_t segment_pref,segment_score,cumulative_score;
714 if(!IsNormalSegment(segment))
717 if(profile->oneway && IsOnewayFrom(segment,node1))
720 node2=OtherNode(segment,node1);
722 if(result1->next==node2)
725 way=LookupWay(ways,segment->way);
727 if(!(way->allow&profile->allow))
730 if(!profile->highway[HIGHWAY(way->type)])
733 if(way->weight && way->weight<profile->weight)
736 if((way->height && way->height<profile->height) ||
737 (way->width && way->width <profile->width ) ||
738 (way->length && way->length<profile->length))
741 segment_pref=profile->highway[HIGHWAY(way->type)];
743 for(i=1;i<Property_Count;i++)
744 if(ways->props & PROPERTIES(i))
746 if(way->props & PROPERTIES(i))
747 segment_pref*=profile->props_yes[i];
749 segment_pref*=profile->props_no[i];
755 if(option_quickest==0)
756 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
758 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
760 cumulative_score=result1->score+segment_score;
762 result2=FindResult(results,node2);
764 if(!result2) /* New end node */
766 result2=InsertResult(results,node2);
767 result2->prev=NO_NODE;
769 result2->score=cumulative_score;
770 result2->segment=segment;
772 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
774 result2->sortby=result2->score;
775 InsertInQueue(queue,result2);
778 else if(cumulative_score<result2->score) /* New end node is better */
781 result2->score=cumulative_score;
782 result2->segment=segment;
784 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
786 result2->sortby=result2->score;
787 InsertInQueue(queue,result2);
793 if(IsFakeNode(node1))
794 segment=NextFakeSegment(segment,node1);
796 segment=NextSegment(segments,segment,node1);
800 FreeQueueList(queue);
802 /* Check it worked */
804 if(results->number==1)
806 FreeResultsList(results);
814 /*++++++++++++++++++++++++++++++++++++++
815 Create an optimum route given the set of super-nodes to follow.
817 Results *CombineRoutes Returns the results from joining the super-nodes.
819 Results *results The set of results from the super-nodes.
821 Nodes *nodes The list of nodes.
823 Segments *segments The set of segments to use.
825 Ways *ways The list of ways.
827 Profile *profile The profile containing the transport type, speeds and allowed highways.
828 ++++++++++++++++++++++++++++++++++++++*/
830 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
832 Result *result1,*result2,*result3,*result4;
835 combined=NewResultsList(64);
837 combined->start=results->start;
838 combined->finish=results->finish;
840 /* Sort out the combined route */
842 result1=FindResult(results,results->start);
844 result3=InsertResult(combined,results->start);
850 if(result1->next!=NO_NODE)
852 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
854 result2=FindResult(results2,result1->node);
856 result3->next=result2->next;
858 result2=FindResult(results2,result2->next);
862 result4=InsertResult(combined,result2->node);
865 result4->score+=result3->score;
867 if(result2->next!=NO_NODE)
868 result2=FindResult(results2,result2->next);
874 FreeResultsList(results2);
876 result1=FindResult(results,result1->next);
889 /*++++++++++++++++++++++++++++++++++++++
890 Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
892 Results *results The set of results to update.
894 index_t finish The finish point.
895 ++++++++++++++++++++++++++++++++++++++*/
897 void FixForwardRoute(Results *results,index_t finish)
899 Result *result2=FindResult(results,finish);
902 /* Create the forward links for the optimum path */
906 if(result2->prev!=NO_NODE)
908 index_t node1=result2->prev;
910 result1=FindResult(results,node1);
912 result1->next=result2->node;
921 results->finish=finish;