Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/optimiser.c
ViewVC logotype

Contents of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 302 - (show annotations) (download) (as text)
Fri Nov 13 19:26:18 2009 UTC (15 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 21627 byte(s) 
Added in some more constants with the value ~0.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.79 2009-11-13 19:26:18 amb Exp $
3
4 Routing optimiser.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 Andrew M. Bishop
9
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.
14
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.
19
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 ***************************************/
23
24
25 #include <stdio.h>
26
27 #include "types.h"
28 #include "functions.h"
29 #include "nodes.h"
30 #include "segments.h"
31 #include "ways.h"
32 #include "results.h"
33
34
35 /*+ The option not to print any progress information. +*/
36 extern int option_quiet;
37
38 /*+ The option to calculate the quickest route insted of the shortest. +*/
39 extern int option_quickest;
40
41
42 /*++++++++++++++++++++++++++++++++++++++
43 Find the optimum route between two nodes not passing through a super-node.
44
45 Results *FindNormalRoute Returns a set of results.
46
47 Nodes *nodes The set of nodes to use.
48
49 Segments *segments The set of segments to use.
50
51 Ways *ways The set of ways to use.
52
53 index_t start The start node.
54
55 index_t finish The finish node.
56
57 Profile *profile The profile containing the transport type, speeds and allowed highways.
58 ++++++++++++++++++++++++++++++++++++++*/
59
60 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
61 {
62 Results *results;
63 Queue *queue;
64 index_t node1,node2;
65 score_t finish_score;
66 double finish_lat,finish_lon;
67 Result *result1,*result2;
68 Segment *segment;
69 Way *way;
70
71 /* Set up the finish conditions */
72
73 finish_score=INF_SCORE;
74
75 GetLatLong(nodes,finish,&finish_lat,&finish_lon);
76
77 /* Create the list of results and insert the first node into the queue */
78
79 results=NewResultsList(8);
80
81 results->start=start;
82 results->finish=finish;
83
84 result1=InsertResult(results,start);
85
86 ZeroResult(result1);
87
88 queue=NewQueueList();
89
90 InsertInQueue(queue,result1);
91
92 /* Loop across all nodes in the queue */
93
94 while((result1=PopFromQueue(queue)))
95 {
96 if(result1->score>finish_score)
97 continue;
98
99 node1=result1->node;
100
101 segment=FirstSegment(segments,nodes,node1);
102
103 while(segment)
104 {
105 score_t segment_pref,segment_score,cumulative_score;
106 int i;
107
108 if(!IsNormalSegment(segment))
109 goto endloop;
110
111 if(profile->oneway && IsOnewayTo(segment,node1))
112 goto endloop;
113
114 node2=OtherNode(segment,node1);
115
116 if(result1->prev==node2)
117 goto endloop;
118
119 if(node2!=finish && IsSuperNode(nodes,node2))
120 goto endloop;
121
122 way=LookupWay(ways,segment->way);
123
124 if(!(way->allow&profile->allow))
125 goto endloop;
126
127 if(!profile->highway[HIGHWAY(way->type)])
128 goto endloop;
129
130 if(way->weight && way->weight<profile->weight)
131 goto endloop;
132
133 if((way->height && way->height<profile->height) ||
134 (way->width && way->width <profile->width ) ||
135 (way->length && way->length<profile->length))
136 goto endloop;
137
138 segment_pref=profile->highway[HIGHWAY(way->type)];
139
140 for(i=1;i<Property_Count;i++)
141 if(way->props && PROPERTIES(i))
142 segment_pref*=profile->props_yes[i];
143 else
144 segment_pref*=profile->props_no[i];
145
146 if(segment_pref==0)
147 goto endloop;
148
149 if(option_quickest==0)
150 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
151 else
152 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
153
154 cumulative_score=result1->score+segment_score;
155
156 if(cumulative_score>finish_score)
157 goto endloop;
158
159 result2=FindResult(results,node2);
160
161 if(!result2) /* New end node */
162 {
163 result2=InsertResult(results,node2);
164 result2->prev=node1;
165 result2->next=NO_NODE;
166 result2->score=cumulative_score;
167 result2->segment=segment;
168
169 if(node2==finish)
170 {
171 finish_score=cumulative_score;
172 }
173 else
174 {
175 result2->sortby=result2->score;
176
177 InsertInQueue(queue,result2);
178 }
179 }
180 else if(cumulative_score<result2->score) /* New end node is better */
181 {
182 result2->prev=node1;
183 result2->score=cumulative_score;
184 result2->segment=segment;
185
186 if(node2==finish)
187 {
188 finish_score=cumulative_score;
189 }
190 else
191 {
192 result2->sortby=result2->score;
193
194 if(result2->score<finish_score)
195 InsertInQueue(queue,result2);
196 }
197 }
198
199 endloop:
200
201 segment=NextSegment(segments,segment,node1);
202 }
203 }
204
205 FreeQueueList(queue);
206
207 /* Check it worked */
208
209 if(!FindResult(results,finish))
210 {
211 FreeResultsList(results);
212 return(NULL);
213 }
214
215 FixForwardRoute(results,finish);
216
217 return(results);
218 }
219
220
221 /*++++++++++++++++++++++++++++++++++++++
222 Find the optimum route between two nodes where the start and end are a set of pre-routed super-nodes.
223
224 Results *FindMiddleRoute Returns a set of results.
225
226 Nodes *nodes The set of nodes to use.
227
228 Segments *segments The set of segments to use.
229
230 Ways *ways The set of ways to use.
231
232 Results *begin The initial portion of the route.
233
234 Results *end The final portion of the route.
235
236 Profile *profile The profile containing the transport type, speeds and allowed highways.
237 ++++++++++++++++++++++++++++++++++++++*/
238
239 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
240 {
241 Results *results;
242 Queue *queue;
243 index_t node1,node2;
244 score_t finish_score;
245 double finish_lat,finish_lon;
246 Result *result1,*result2,*result3;
247 Segment *segment;
248 Way *way;
249
250 if(!option_quiet)
251 {
252 printf("Routing: End Nodes=0");
253 fflush(stdout);
254 }
255
256 /* Set up the finish conditions */
257
258 finish_score=INF_DISTANCE;
259
260 GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
261
262 /* Create the list of results and insert the first node into the queue */
263
264 results=NewResultsList(65536);
265
266 results->start=begin->start;
267 results->finish=end->finish;
268
269 result1=InsertResult(results,begin->start);
270 result3=FindResult(begin,begin->start);
271
272 *result1=*result3;
273
274 queue=NewQueueList();
275
276 /* Insert the finish points of the beginning part of the path into the queue */
277
278 result3=FirstResult(begin);
279
280 while(result3)
281 {
282 if(result3->node!=begin->start && IsSuperNode(nodes,result3->node))
283 {
284 result2=InsertResult(results,result3->node);
285
286 *result2=*result3;
287
288 result2->prev=begin->start;
289
290 result2->sortby=result2->score;
291
292 InsertInQueue(queue,result2);
293 }
294
295 result3=NextResult(begin,result3);
296 }
297
298 if(begin->number==1)
299 InsertInQueue(queue,result1);
300
301 /* Loop across all nodes in the queue */
302
303 while((result1=PopFromQueue(queue)))
304 {
305 if(result1->score>finish_score)
306 continue;
307
308 node1=result1->node;
309
310 segment=FirstSegment(segments,nodes,node1);
311
312 while(segment)
313 {
314 score_t segment_pref,segment_score,cumulative_score;
315 int i;
316
317 if(!IsSuperSegment(segment))
318 goto endloop;
319
320 if(profile->oneway && IsOnewayTo(segment,node1))
321 goto endloop;
322
323 node2=OtherNode(segment,node1);
324
325 if(result1->prev==node2)
326 goto endloop;
327
328 way=LookupWay(ways,segment->way);
329
330 if(!(way->allow&profile->allow))
331 goto endloop;
332
333 if(!profile->highway[HIGHWAY(way->type)])
334 goto endloop;
335
336 if(way->weight && way->weight<profile->weight)
337 goto endloop;
338
339 if((way->height && way->height<profile->height) ||
340 (way->width && way->width <profile->width ) ||
341 (way->length && way->length<profile->length))
342 goto endloop;
343
344 segment_pref=profile->highway[HIGHWAY(way->type)];
345
346 for(i=1;i<Property_Count;i++)
347 if(way->props && PROPERTIES(i))
348 segment_pref*=profile->props_yes[i];
349 else
350 segment_pref*=profile->props_no[i];
351
352 if(segment_pref==0)
353 goto endloop;
354
355 if(option_quickest==0)
356 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
357 else
358 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
359
360 cumulative_score=result1->score+segment_score;
361
362 if(cumulative_score>finish_score)
363 goto endloop;
364
365 result2=FindResult(results,node2);
366
367 if(!result2) /* New end node */
368 {
369 result2=InsertResult(results,node2);
370 result2->prev=node1;
371 result2->next=NO_NODE;
372 result2->score=cumulative_score;
373 result2->segment=segment;
374
375 if((result3=FindResult(end,node2)))
376 {
377 finish_score=result2->score+result3->score;
378 }
379 else
380 {
381 double lat,lon;
382 distance_t direct;
383
384 GetLatLong(nodes,node2,&lat,&lon);
385 direct=Distance(lat,lon,finish_lat,finish_lon);
386
387 if(option_quickest==0)
388 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
389 else
390 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
391
392 InsertInQueue(queue,result2);
393 }
394 }
395 else if(cumulative_score<result2->score) /* New end node is better */
396 {
397 result2->prev=node1;
398 result2->score=cumulative_score;
399 result2->segment=segment;
400
401 if((result3=FindResult(end,node2)))
402 {
403 if((result2->score+result3->score)<finish_score)
404 {
405 finish_score=result2->score+result3->score;
406 }
407 }
408 else if(result2->score<finish_score)
409 {
410 double lat,lon;
411 distance_t direct;
412
413 GetLatLong(nodes,node2,&lat,&lon);
414 direct=Distance(lat,lon,finish_lat,finish_lon);
415
416 if(option_quickest==0)
417 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
418 else
419 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
420
421 InsertInQueue(queue,result2);
422 }
423 }
424
425 endloop:
426
427 if(!option_quiet && !(results->number%10000))
428 {
429 printf("\rRouting: End Nodes=%d",results->number);
430 fflush(stdout);
431 }
432
433 segment=NextSegment(segments,segment,node1);
434 }
435 }
436
437 if(!option_quiet)
438 {
439 printf("\rRouted: End Super-Nodes=%d\n",results->number);
440 fflush(stdout);
441 }
442
443 /* Finish off the end part of the route. */
444
445 if(!FindResult(results,end->finish))
446 {
447 result2=InsertResult(results,end->finish);
448 result3=FindResult(end,end->finish);
449
450 *result2=*result3;
451
452 result2->score=INF_DISTANCE;
453
454 result3=FirstResult(end);
455
456 while(result3)
457 {
458 if(IsSuperNode(nodes,result3->node))
459 if((result1=FindResult(results,result3->node)))
460 if((result1->score+result3->score)<result2->score)
461 {
462 result2->score=result1->score+result3->score;
463 result2->prev=result1->node;
464 }
465
466 result3=NextResult(end,result3);
467 }
468 }
469
470 FreeQueueList(queue);
471
472 /* Check it worked */
473
474 if(!FindResult(results,end->finish))
475 {
476 FreeResultsList(results);
477 return(NULL);
478 }
479
480 FixForwardRoute(results,end->finish);
481
482 return(results);
483 }
484
485
486 /*++++++++++++++++++++++++++++++++++++++
487 Find all routes from a specified node to any super-node.
488
489 Results *FindStartRoutes Returns a set of results.
490
491 Nodes *nodes The set of nodes to use.
492
493 Segments *segments The set of segments to use.
494
495 Ways *ways The set of ways to use.
496
497 index_t start The start node.
498
499 Profile *profile The profile containing the transport type, speeds and allowed highways.
500 ++++++++++++++++++++++++++++++++++++++*/
501
502 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
503 {
504 Results *results;
505 Queue *queue;
506 index_t node1,node2;
507 Result *result1,*result2;
508 Segment *segment;
509 Way *way;
510
511 /* Insert the first node into the queue */
512
513 results=NewResultsList(8);
514
515 results->start=start;
516
517 result1=InsertResult(results,start);
518
519 ZeroResult(result1);
520
521 queue=NewQueueList();
522
523 InsertInQueue(queue,result1);
524
525 /* Loop across all nodes in the queue */
526
527 while((result1=PopFromQueue(queue)))
528 {
529 node1=result1->node;
530
531 segment=FirstSegment(segments,nodes,node1);
532
533 while(segment)
534 {
535 score_t segment_pref,segment_score,cumulative_score;
536 int i;
537
538 if(!IsNormalSegment(segment))
539 goto endloop;
540
541 if(profile->oneway && IsOnewayTo(segment,node1))
542 goto endloop;
543
544 node2=OtherNode(segment,node1);
545
546 if(result1->prev==node2)
547 goto endloop;
548
549 way=LookupWay(ways,segment->way);
550
551 if(!(way->allow&profile->allow))
552 goto endloop;
553
554 if(!profile->highway[HIGHWAY(way->type)])
555 goto endloop;
556
557 if(way->weight && way->weight<profile->weight)
558 goto endloop;
559
560 if((way->height && way->height<profile->height) ||
561 (way->width && way->width <profile->width ) ||
562 (way->length && way->length<profile->length))
563 goto endloop;
564
565 segment_pref=profile->highway[HIGHWAY(way->type)];
566
567 for(i=1;i<Property_Count;i++)
568 if(way->props && PROPERTIES(i))
569 segment_pref*=profile->props_yes[i];
570 else
571 segment_pref*=profile->props_no[i];
572
573 if(segment_pref==0)
574 goto endloop;
575
576 if(option_quickest==0)
577 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
578 else
579 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
580
581 cumulative_score=result1->score+segment_score;
582
583 result2=FindResult(results,node2);
584
585 if(!result2) /* New end node */
586 {
587 result2=InsertResult(results,node2);
588 result2->prev=node1;
589 result2->next=NO_NODE;
590 result2->score=cumulative_score;
591 result2->segment=segment;
592
593 if(!IsSuperNode(nodes,node2))
594 {
595 result2->sortby=result2->score;
596 InsertInQueue(queue,result2);
597 }
598 }
599 else if(cumulative_score<result2->score) /* New end node is better */
600 {
601 result2->prev=node1;
602 result2->score=cumulative_score;
603 result2->segment=segment;
604
605 if(!IsSuperNode(nodes,node2))
606 {
607 result2->sortby=result2->score;
608 InsertInQueue(queue,result2);
609 }
610 }
611
612 endloop:
613
614 segment=NextSegment(segments,segment,node1);
615 }
616 }
617
618 FreeQueueList(queue);
619
620 /* Check it worked */
621
622 if(results->number==1)
623 {
624 FreeResultsList(results);
625 return(NULL);
626 }
627
628 return(results);
629 }
630
631
632 /*++++++++++++++++++++++++++++++++++++++
633 Find all routes from any super-node to a specific node.
634
635 Results *FindFinishRoutes Returns a set of results.
636
637 Nodes *nodes The set of nodes to use.
638
639 Segments *segments The set of segments to use.
640
641 Ways *ways The set of ways to use.
642
643 index_t finish The finishing node.
644
645 Profile *profile The profile containing the transport type, speeds and allowed highways.
646 ++++++++++++++++++++++++++++++++++++++*/
647
648 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
649 {
650 Results *results;
651 Queue *queue;
652 index_t node1,node2;
653 Result *result1,*result2;
654 Segment *segment;
655 Way *way;
656
657 /* Insert the first node into the queue */
658
659 results=NewResultsList(8);
660
661 results->finish=finish;
662
663 result1=InsertResult(results,finish);
664
665 ZeroResult(result1);
666
667 queue=NewQueueList();
668
669 InsertInQueue(queue,result1);
670
671 /* Loop across all nodes in the queue */
672
673 while((result1=PopFromQueue(queue)))
674 {
675 node1=result1->node;
676
677 segment=FirstSegment(segments,nodes,node1);
678
679 while(segment)
680 {
681 score_t segment_pref,segment_score,cumulative_score;
682 int i;
683
684 if(!IsNormalSegment(segment))
685 goto endloop;
686
687 if(profile->oneway && IsOnewayFrom(segment,node1))
688 goto endloop;
689
690 node2=OtherNode(segment,node1);
691
692 if(result1->next==node2)
693 goto endloop;
694
695 way=LookupWay(ways,segment->way);
696
697 if(!(way->allow&profile->allow))
698 goto endloop;
699
700 if(!profile->highway[HIGHWAY(way->type)])
701 goto endloop;
702
703 if(way->weight && way->weight<profile->weight)
704 goto endloop;
705
706 if((way->height && way->height<profile->height) ||
707 (way->width && way->width <profile->width ) ||
708 (way->length && way->length<profile->length))
709 goto endloop;
710
711 segment_pref=profile->highway[HIGHWAY(way->type)];
712
713 for(i=1;i<Property_Count;i++)
714 if(way->props && PROPERTIES(i))
715 segment_pref*=profile->props_yes[i];
716 else
717 segment_pref*=profile->props_no[i];
718
719 if(segment_pref==0)
720 goto endloop;
721
722 if(option_quickest==0)
723 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
724 else
725 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
726
727 cumulative_score=result1->score+segment_score;
728
729 result2=FindResult(results,node2);
730
731 if(!result2) /* New end node */
732 {
733 result2=InsertResult(results,node2);
734 result2->prev=NO_NODE;
735 result2->next=node1;
736 result2->score=cumulative_score;
737 result2->segment=segment;
738
739 if(!IsSuperNode(nodes,node2))
740 {
741 result2->sortby=result2->score;
742 InsertInQueue(queue,result2);
743 }
744 }
745 else if(cumulative_score<result2->score) /* New end node is better */
746 {
747 result2->next=node1;
748 result2->score=cumulative_score;
749 result2->segment=segment;
750
751 if(!IsSuperNode(nodes,node2))
752 {
753 result2->sortby=result2->score;
754 InsertInQueue(queue,result2);
755 }
756 }
757
758 endloop:
759
760 segment=NextSegment(segments,segment,node1);
761 }
762 }
763
764 FreeQueueList(queue);
765
766 /* Check it worked */
767
768 if(results->number==1)
769 {
770 FreeResultsList(results);
771 return(NULL);
772 }
773
774 return(results);
775 }
776
777
778 /*++++++++++++++++++++++++++++++++++++++
779 Create an optimum route given the set of super-nodes to follow.
780
781 Results *CombineRoutes Returns the results from joining the super-nodes.
782
783 Results *results The set of results from the super-nodes.
784
785 Nodes *nodes The list of nodes.
786
787 Segments *segments The set of segments to use.
788
789 Ways *ways The list of ways.
790
791 Profile *profile The profile containing the transport type, speeds and allowed highways.
792 ++++++++++++++++++++++++++++++++++++++*/
793
794 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
795 {
796 Result *result1,*result2,*result3,*result4;
797 Results *combined;
798
799 combined=NewResultsList(64);
800
801 combined->start=results->start;
802 combined->finish=results->finish;
803
804 /* Sort out the combined route */
805
806 result1=FindResult(results,results->start);
807
808 result3=InsertResult(combined,results->start);
809
810 ZeroResult(result3);
811
812 do
813 {
814 if(result1->next!=NO_NODE)
815 {
816 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
817
818 result2=FindResult(results2,result1->node);
819
820 result3->next=result2->next;
821
822 result2=FindResult(results2,result2->next);
823
824 do
825 {
826 result4=InsertResult(combined,result2->node);
827
828 *result4=*result2;
829 result4->score+=result3->score;
830
831 if(result2->next!=NO_NODE)
832 result2=FindResult(results2,result2->next);
833 else
834 result2=NULL;
835 }
836 while(result2);
837
838 FreeResultsList(results2);
839
840 result1=FindResult(results,result1->next);
841
842 result3=result4;
843 }
844 else
845 result1=NULL;
846 }
847 while(result1);
848
849 return(combined);
850 }
851
852
853 /*++++++++++++++++++++++++++++++++++++++
854 Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
855
856 Results *results The set of results to update.
857
858 index_t finish The finish point.
859 ++++++++++++++++++++++++++++++++++++++*/
860
861 void FixForwardRoute(Results *results,index_t finish)
862 {
863 Result *result2=FindResult(results,finish);
864 Result *result1;
865
866 /* Create the forward links for the optimum path */
867
868 do
869 {
870 if(result2->prev!=NO_NODE)
871 {
872 index_t node1=result2->prev;
873
874 result1=FindResult(results,node1);
875
876 result1->next=result2->node;
877
878 result2=result1;
879 }
880 else
881 result2=NULL;
882 }
883 while(result2);
884
885 results->finish=finish;
886 }

Properties

Name Value
cvs:description Route optimiser.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root