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 68 - (show annotations) (download) (as text)
Thu Jan 22 19:39:30 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 35790 byte(s) 
Removed the Way_TYPE() macro.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.26 2009-01-22 19:39:30 amb Exp $
3
4 Routing optimiser.
5 ******************/ /******************
6 Written by Andrew M. Bishop
7
8 This file Copyright 2008,2009 Andrew M. Bishop
9 It may be distributed under the GNU Public License, version 2, or
10 any higher version. See section COPYING of the GNU Public license
11 for conditions under which this file may be redistributed.
12 ***************************************/
13
14
15 #include <assert.h>
16 #include <string.h>
17 #include <stdlib.h>
18
19 #include "nodes.h"
20 #include "ways.h"
21 #include "segments.h"
22 #include "results.h"
23 #include "functions.h"
24
25
26 /*+ Print the progress? +*/
27 int print_progress=1;
28
29
30 /*++++++++++++++++++++++++++++++++++++++
31 Find the optimum route between two nodes.
32
33 Results *FindRoute Returns a set of results.
34
35 Nodes *nodes The set of nodes to use.
36
37 Segments *segments The set of segments to use.
38
39 Ways *ways The set of ways to use.
40
41 node_t start The start node.
42
43 node_t finish The finish node.
44
45 wayallow_t transport The mode of transport.
46 ++++++++++++++++++++++++++++++++++++++*/
47
48 Results *FindRoute(Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport)
49 {
50 Results *results;
51 node_t node1,node2;
52 HalfResult shortest1,quickest1;
53 HalfResult shortest2,quickest2;
54 HalfResult shortestfinish,quickestfinish;
55 Result *result1,*result2;
56 Segment *segment;
57 Way *way;
58
59 /* Set up the finish conditions */
60
61 shortestfinish.distance=INVALID_DISTANCE;
62 shortestfinish.duration=INVALID_DURATION;
63 quickestfinish.distance=INVALID_DISTANCE;
64 quickestfinish.duration=INVALID_DURATION;
65
66 /* Insert the first node into the queue */
67
68 results=NewResultsList();
69
70 result1=InsertResult(results,start);
71
72 result1->node=start;
73 result1->shortest.prev=0;
74 result1->shortest.next=0;
75 result1->shortest.distance=0;
76 result1->shortest.duration=0;
77 result1->quickest.prev=0;
78 result1->quickest.next=0;
79 result1->quickest.distance=0;
80 result1->quickest.duration=0;
81
82 insert_in_queue(results,result1);
83
84 /* Loop across all nodes in the queue */
85
86 while((result1=pop_from_queue(results)))
87 {
88 node1=result1->node;
89 shortest1=result1->shortest;
90 quickest1=result1->quickest;
91
92 segment=FindFirstSegment(segments,node1);
93
94 while(segment)
95 {
96 duration_t segment_duration;
97
98 if(segment->distance==INVALID_DISTANCE)
99 goto endloop;
100
101 node2=segment->node2;
102
103 if(shortest1.prev==node2 && quickest1.prev==node2)
104 goto endloop;
105
106 way=FindWay(ways,segment->way);
107
108 if((way->allow&transport)!=transport)
109 goto endloop;
110
111 segment_duration=Duration(segment,way,transport);
112
113 shortest2.distance=shortest1.distance+segment->distance;
114 shortest2.duration=shortest1.duration+segment_duration;
115 quickest2.distance=quickest1.distance+segment->distance;
116 quickest2.duration=quickest1.duration+segment_duration;
117
118 if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration)
119 goto endloop;
120
121 result2=FindResult(results,node2);
122
123 if(!result2) /* New end node */
124 {
125 result2=InsertResult(results,node2);
126 result2->node=node2;
127 result2->shortest.prev=node1;
128 result2->shortest.next=0;
129 result2->shortest.distance=shortest2.distance;
130 result2->shortest.duration=shortest2.duration;
131 result2->quickest.prev=node1;
132 result2->quickest.next=0;
133 result2->quickest.distance=quickest2.distance;
134 result2->quickest.duration=quickest2.duration;
135
136 if(node2==finish)
137 {
138 shortestfinish.distance=shortest2.distance;
139 shortestfinish.duration=shortest2.duration;
140 quickestfinish.distance=quickest2.distance;
141 quickestfinish.duration=quickest2.duration;
142 }
143 else
144 insert_in_queue(results,result2);
145 }
146 else
147 {
148 if(shortest2.distance<result2->shortest.distance ||
149 (shortest2.distance==result2->shortest.distance &&
150 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
151 {
152 result2->shortest.prev=node1;
153 result2->shortest.distance=shortest2.distance;
154 result2->shortest.duration=shortest2.duration;
155
156 if(node2==finish)
157 {
158 shortestfinish.distance=shortest2.distance;
159 shortestfinish.duration=shortest2.duration;
160 }
161 else
162 insert_in_queue(results,result2);
163 }
164
165 if(quickest2.duration<result2->quickest.duration ||
166 (quickest2.duration==result2->quickest.duration &&
167 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
168 {
169 result2->quickest.prev=node1;
170 result2->quickest.distance=quickest2.distance;
171 result2->quickest.duration=quickest2.duration;
172
173 if(node2==finish)
174 {
175 quickestfinish.distance=quickest2.distance;
176 quickestfinish.duration=quickest2.duration;
177 }
178 else
179 insert_in_queue(results,result2);
180 }
181 }
182
183 endloop:
184
185 segment=FindNextSegment(segments,segment);
186 }
187
188 if(print_progress && !(results->number%10000))
189 {
190 printf("\rRouting: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin ",results->number,
191 distance_to_km(shortest2.distance),duration_to_minutes(shortest2.duration),
192 distance_to_km(quickest2.distance),duration_to_minutes(quickest2.duration));
193 fflush(stdout);
194 }
195 }
196
197 if(print_progress)
198 {
199 printf("\rRouted: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number,
200 distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration),
201 distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration));
202 fflush(stdout);
203 }
204
205 /* Reverse the results */
206
207 result2=FindResult(results,finish);
208
209 do
210 {
211 if(result2->shortest.prev)
212 {
213 node_t node1=result2->shortest.prev;
214
215 result1=FindResult(results,node1);
216
217 result1->shortest.next=result2->node;
218
219 result2=result1;
220 }
221 else
222 result2=NULL;
223 }
224 while(result2);
225
226 result2=FindResult(results,finish);
227
228 do
229 {
230 if(result2->quickest.prev)
231 {
232 node_t node1=result2->quickest.prev;
233
234 result1=FindResult(results,node1);
235
236 result1->quickest.next=result2->node;
237
238 result2=result1;
239 }
240 else
241 result2=NULL;
242 }
243 while(result2);
244
245 return(results);
246 }
247
248
249 /*++++++++++++++++++++++++++++++++++++++
250 Find the optimum route between two nodes.
251
252 Results *FindRoute3 Returns a set of results.
253
254 Nodes *supernodes The set of supernodes to use.
255
256 Segments *supersegments The set of supersegments to use.
257
258 Ways *superways The set of superways to use.
259
260 node_t start The start node.
261
262 node_t finish The finish node.
263
264 Results *begin The initial portion of the route.
265
266 Results *end The final portion of the route.
267
268 wayallow_t transport The mode of transport.
269 ++++++++++++++++++++++++++++++++++++++*/
270
271 Results *FindRoute3(Nodes *supernodes,Segments *supersegments,Ways *superways,node_t start,node_t finish,Results *begin,Results *end,wayallow_t transport)
272 {
273 Results *results;
274 node_t node1,node2;
275 HalfResult shortest1,quickest1;
276 HalfResult shortest2,quickest2;
277 HalfResult shortestfinish,quickestfinish;
278 Result *result1,*result2,*result3;
279 Segment *segment;
280 Way *way;
281 int j;
282
283 /* Set up the finish conditions */
284
285 shortestfinish.distance=INVALID_DISTANCE;
286 shortestfinish.duration=INVALID_DURATION;
287 quickestfinish.distance=INVALID_DISTANCE;
288 quickestfinish.duration=INVALID_DURATION;
289
290 /* Insert the start node */
291
292 results=NewResultsList();
293
294 result1=InsertResult(results,start);
295 result2=FindResult(begin,start);
296
297 *result1=*result2;
298
299 /* Insert the finish points of the beginning part of the path into the queue */
300
301 for(j=0;j<begin->number;j++)
302 if(FindNode(supernodes,begin->results[j].node))
303 {
304 if(!(result1=FindResult(results,begin->results[j].node)))
305 {
306 result1=InsertResult(results,begin->results[j].node);
307
308 *result1=begin->results[j];
309
310 result1->shortest.prev=start;
311 result1->quickest.prev=start;
312 }
313
314 insert_in_queue(results,result1);
315 }
316
317 /* Loop across all supernodes in the queue */
318
319 while((result1=pop_from_queue(results)))
320 {
321 node1=result1->node;
322 shortest1=result1->shortest;
323 quickest1=result1->quickest;
324
325 segment=FindFirstSegment(supersegments,node1);
326
327 while(segment)
328 {
329 duration_t segment_duration;
330
331 if(segment->distance==INVALID_DISTANCE)
332 goto endloop;
333
334 node2=segment->node2;
335
336 if(shortest1.prev==node2 && quickest1.prev==node2)
337 goto endloop;
338
339 way=FindWay(superways,segment->way);
340
341 if((way->allow&transport)!=transport)
342 goto endloop;
343
344 segment_duration=Duration(segment,way,transport);
345
346 shortest2.distance=shortest1.distance+segment->distance;
347 shortest2.duration=shortest1.duration+segment_duration;
348 quickest2.distance=quickest1.distance+segment->distance;
349 quickest2.duration=quickest1.duration+segment_duration;
350
351 if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration)
352 goto endloop;
353
354 result2=FindResult(results,node2);
355 result3=NULL;
356
357 if(!result2) /* New end node */
358 {
359 result2=InsertResult(results,node2);
360 result2->node=node2;
361 result2->shortest.prev=node1;
362 result2->shortest.next=0;
363 result2->shortest.distance=shortest2.distance;
364 result2->shortest.duration=shortest2.duration;
365 result2->quickest.prev=node1;
366 result2->quickest.next=0;
367 result2->quickest.distance=quickest2.distance;
368 result2->quickest.duration=quickest2.duration;
369
370 if(!(result3=FindResult(end,node2)))
371 insert_in_queue(results,result2);
372 }
373 else
374 {
375 if(shortest2.distance<result2->shortest.distance ||
376 (shortest2.distance==result2->shortest.distance &&
377 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
378 {
379 result2->shortest.prev=node1;
380 result2->shortest.distance=shortest2.distance;
381 result2->shortest.duration=shortest2.duration;
382
383 if(!(result3=FindResult(end,node2)))
384 insert_in_queue(results,result2);
385 }
386
387 if(quickest2.duration<result2->quickest.duration ||
388 (quickest2.duration==result2->quickest.duration &&
389 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
390 {
391 result2->quickest.prev=node1;
392 result2->quickest.distance=quickest2.distance;
393 result2->quickest.duration=quickest2.duration;
394
395 if(!(result3=FindResult(end,node2)))
396 insert_in_queue(results,result2);
397 }
398 }
399
400 if(result3)
401 {
402 if((shortest2.distance+result3->shortest.distance)<shortestfinish.distance ||
403 ((shortest2.distance+result3->shortest.distance)==shortestfinish.distance &&
404 (shortest2.duration+result3->shortest.duration)<shortestfinish.duration))
405 {
406 shortestfinish.distance=shortest2.distance+result3->shortest.distance;
407 shortestfinish.duration=shortest2.duration+result3->shortest.duration;
408 }
409 if((quickest2.duration+result3->quickest.duration)<quickestfinish.duration ||
410 ((quickest2.duration+result3->quickest.duration)==quickestfinish.duration &&
411 (quickest2.distance+result3->quickest.distance)<quickestfinish.distance))
412 {
413 quickestfinish.distance=quickest2.distance+result3->quickest.distance;
414 quickestfinish.duration=quickest2.duration+result3->quickest.duration;
415 }
416 }
417
418 endloop:
419
420 segment=FindNextSegment(supersegments,segment);
421 }
422
423 if(print_progress && !(results->number%10000))
424 {
425 printf("\rRouting: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin ",results->number,
426 distance_to_km(shortest2.distance),duration_to_minutes(shortest2.duration),
427 distance_to_km(quickest2.distance),duration_to_minutes(quickest2.duration));
428 fflush(stdout);
429 }
430 }
431
432 if(print_progress)
433 {
434 printf("\rRouted: End Super-Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number,
435 distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration),
436 distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration));
437 fflush(stdout);
438 }
439
440 /* Finish off the end part of the route. */
441
442 if(!FindResult(results,finish))
443 {
444 result2=InsertResult(results,finish);
445 result1=FindResult(end,finish);
446
447 *result2=*result1;
448
449 result2->shortest.distance=INVALID_DISTANCE;
450 result2->shortest.duration=INVALID_DURATION;
451 result2->quickest.distance=INVALID_DISTANCE;
452 result2->quickest.duration=INVALID_DURATION;
453
454 for(j=0;j<end->number;j++)
455 if(FindNode(supernodes,end->results[j].node))
456 if((result1=FindResult(results,end->results[j].node)))
457 {
458 if((result1->shortest.distance+end->results[j].shortest.distance)<result2->shortest.distance ||
459 ((result1->shortest.distance+end->results[j].shortest.distance)==result2->shortest.distance &&
460 (result1->shortest.duration+end->results[j].shortest.duration)<result2->shortest.duration))
461 {
462 result2->shortest.distance=result1->shortest.distance+end->results[j].shortest.distance;
463 result2->shortest.duration=result1->shortest.duration+end->results[j].shortest.duration;
464 result2->shortest.prev=result1->node;
465 }
466 if((result1->quickest.duration+end->results[j].quickest.duration)<result2->quickest.duration ||
467 ((result1->quickest.duration+end->results[j].quickest.duration)==result2->quickest.duration &&
468 (result1->quickest.distance+end->results[j].quickest.distance)<result2->quickest.distance))
469 {
470 result2->quickest.distance=result1->quickest.distance+end->results[j].quickest.distance;
471 result2->quickest.duration=result1->quickest.duration+end->results[j].quickest.duration;
472 result2->quickest.prev=result1->node;
473 }
474 }
475 }
476
477 /* Reverse the results */
478
479 result2=FindResult(results,finish);
480
481 do
482 {
483 if(result2->shortest.prev)
484 {
485 node_t node1=result2->shortest.prev;
486
487 result1=FindResult(results,node1);
488
489 result1->shortest.next=result2->node;
490
491 result2=result1;
492 }
493 else
494 result2=NULL;
495 }
496 while(result2);
497
498 result2=FindResult(results,finish);
499
500 do
501 {
502 if(result2->quickest.prev)
503 {
504 node_t node1=result2->quickest.prev;
505
506 result1=FindResult(results,node1);
507
508 result1->quickest.next=result2->node;
509
510 result2=result1;
511 }
512 else
513 result2=NULL;
514 }
515 while(result2);
516
517 return(results);
518 }
519
520
521 /*++++++++++++++++++++++++++++++++++++++
522 Print the optimum route between two nodes.
523
524 Results *Results The set of results to print.
525
526 Nodes *nodes The list of nodes.
527
528 Segments *segments The set of segments to use.
529
530 Ways *ways The list of ways.
531
532 Nodes *supernodes The list of super-nodes.
533
534 node_t start The start node.
535
536 node_t finish The finish node.
537
538 wayallow_t transport The mode of transport.
539 ++++++++++++++++++++++++++++++++++++++*/
540
541 void PrintRoute(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,node_t start,node_t finish,wayallow_t transport)
542 {
543 FILE *textfile,*gpxfile;
544 Result *result;
545
546 /* Print the result for the shortest route */
547
548 textfile=fopen("shortest.txt","w");
549 gpxfile=fopen("shortest.gpx","w");
550
551 fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
552 fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n");
553 fprintf(gpxfile,"<trk>\n");
554 fprintf(gpxfile,"<trkseg>\n");
555
556 result=FindResult(results,start);
557
558 do
559 {
560 Node *node=FindNode(nodes,result->node);
561
562 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude);
563
564 if(result->shortest.prev)
565 {
566 Segment *segment;
567 Way *way;
568
569 segment=FindFirstSegment(segments,result->shortest.prev);
570 while(segment->node2!=result->node)
571 segment=FindNextSegment(segments,segment);
572
573 way=FindWay(ways,segment->way);
574
575 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude,
576 node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
577 distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)),
578 distance_to_km(result->shortest.distance),duration_to_minutes(result->shortest.duration),
579 WaySpeed(way),WayName(ways,way));
580 }
581 else
582 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude,
583 node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
584 0.0,0.0,0.0,0.0);
585
586 if(result->shortest.next)
587 result=FindResult(results,result->shortest.next);
588 else
589 result=NULL;
590 }
591 while(result);
592
593 fprintf(gpxfile,"</trkseg>\n");
594 fprintf(gpxfile,"</trk>\n");
595 fprintf(gpxfile,"</gpx>\n");
596
597 fclose(textfile);
598 fclose(gpxfile);
599
600 /* Print the result for the quickest route */
601
602 textfile=fopen("quickest.txt","w");
603 gpxfile=fopen("quickest.gpx","w");
604
605 fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
606 fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n");
607 fprintf(gpxfile,"<trk>\n");
608 fprintf(gpxfile,"<trkseg>\n");
609
610 result=FindResult(results,start);
611
612 do
613 {
614 Node *node=FindNode(nodes,result->node);
615
616 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude);
617
618 if(result->quickest.prev)
619 {
620 Segment *segment;
621 Way *way;
622
623 segment=FindFirstSegment(segments,result->quickest.prev);
624 while(segment->node2!=result->node)
625 segment=FindNextSegment(segments,segment);
626
627 way=FindWay(ways,segment->way);
628
629 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude,
630 node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
631 distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)),
632 distance_to_km(result->quickest.distance),duration_to_minutes(result->quickest.duration),
633 WaySpeed(way),WayName(ways,way));
634 }
635 else
636 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude,
637 node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
638 0.0,0.0,0.0,0.0);
639
640 if(result->quickest.next)
641 result=FindResult(results,result->quickest.next);
642 else
643 result=NULL;
644 }
645 while(result);
646
647 fprintf(gpxfile,"</trkseg>\n");
648 fprintf(gpxfile,"</trk>\n");
649 fprintf(gpxfile,"</gpx>\n");
650
651 fclose(textfile);
652 fclose(gpxfile);
653 }
654
655
656 /*++++++++++++++++++++++++++++++++++++++
657 Find all routes from a specified node to any node in the specified list.
658
659 Results *FindRoutes Returns a set of results.
660
661 Nodes *nodes The set of nodes to use.
662
663 Segments *segments The set of segments to use.
664
665 Ways *ways The set of ways to use.
666
667 node_t start The start node.
668
669 Nodes *finish The finishing nodes.
670
671 wayallow_t transport The mode of transport.
672 ++++++++++++++++++++++++++++++++++++++*/
673
674 Results *FindRoutes(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,wayallow_t transport)
675 {
676 Results *results;
677 node_t node1,node2;
678 HalfResult shortest1,quickest1;
679 HalfResult shortest2,quickest2;
680 Result *result1,*result2;
681 Segment *segment;
682 Way *way;
683
684 /* Insert the first node into the queue */
685
686 results=NewResultsList();
687
688 result1=InsertResult(results,start);
689
690 result1->node=start;
691 result1->shortest.prev=0;
692 result1->shortest.next=0;
693 result1->shortest.distance=0;
694 result1->shortest.duration=0;
695 result1->quickest.prev=0;
696 result1->quickest.next=0;
697 result1->quickest.distance=0;
698 result1->quickest.duration=0;
699
700 insert_in_queue(results,result1);
701
702 /* Loop across all nodes in the queue */
703
704 while((result1=pop_from_queue(results)))
705 {
706 node1=result1->node;
707 shortest1=result1->shortest;
708 quickest1=result1->quickest;
709
710 segment=FindFirstSegment(segments,node1);
711
712 while(segment)
713 {
714 duration_t segment_duration;
715
716 if(segment->distance==INVALID_DISTANCE)
717 goto endloop;
718
719 node2=segment->node2;
720
721 if(shortest1.prev==node2 && quickest1.prev==node2)
722 goto endloop;
723
724 way=FindWay(ways,segment->way);
725
726 if((way->allow&transport)!=transport)
727 goto endloop;
728
729 segment_duration=Duration(segment,way,transport);
730
731 shortest2.distance=shortest1.distance+segment->distance;
732 shortest2.duration=shortest1.duration+segment_duration;
733 quickest2.distance=quickest1.distance+segment->distance;
734 quickest2.duration=quickest1.duration+segment_duration;
735
736 result2=FindResult(results,node2);
737
738 if(!result2) /* New end node */
739 {
740 result2=InsertResult(results,node2);
741 result2->node=node2;
742 result2->shortest.prev=node1;
743 result2->shortest.next=0;
744 result2->shortest.distance=shortest2.distance;
745 result2->shortest.duration=shortest2.duration;
746 result2->quickest.prev=node1;
747 result2->quickest.next=0;
748 result2->quickest.distance=quickest2.distance;
749 result2->quickest.duration=quickest2.duration;
750
751 if(!FindNode(finish,node2))
752 insert_in_queue(results,result2);
753 }
754 else
755 {
756 if(shortest2.distance<result2->shortest.distance ||
757 (shortest2.distance==result2->shortest.distance &&
758 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
759 {
760 result2->shortest.prev=node1;
761 result2->shortest.distance=shortest2.distance;
762 result2->shortest.duration=shortest2.duration;
763
764 if(!FindNode(finish,node2))
765 insert_in_queue(results,result2);
766 }
767
768 if(quickest2.duration<result2->quickest.duration ||
769 (quickest2.duration==result2->quickest.duration &&
770 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
771 {
772 result2->quickest.prev=node1;
773 result2->quickest.distance=quickest2.distance;
774 result2->quickest.duration=quickest2.duration;
775
776 if(!FindNode(finish,node2))
777 insert_in_queue(results,result2);
778 }
779 }
780
781 endloop:
782
783 segment=FindNextSegment(segments,segment);
784 }
785 }
786
787 return(results);
788 }
789
790
791 /*++++++++++++++++++++++++++++++++++++++
792 Find all routes from any node in the specified list to a specific node.
793
794 Results *FindReverseRoute Returns a set of results.
795
796 Nodes *nodes The set of nodes to use.
797
798 Segments *segments The set of segments to use.
799
800 Ways *ways The set of ways to use.
801
802 Nodes *start The starting nodes.
803
804 node_t finish The finishing node.
805
806 wayallow_t transport The mode of transport.
807 ++++++++++++++++++++++++++++++++++++++*/
808
809 Results *FindReverseRoutes(Nodes *nodes,Segments *segments,Ways *ways,Nodes *start,node_t finish,wayallow_t transport)
810 {
811 Results *results;
812 node_t node1,node2;
813 HalfResult shortest1,quickest1;
814 HalfResult shortest2,quickest2;
815 Result *result1,*result2;
816 Segment *segment;
817 Way *way;
818
819 /* Insert the first node into the queue */
820
821 results=NewResultsList();
822
823 result1=InsertResult(results,finish);
824
825 result1->node=finish;
826 result1->shortest.prev=0;
827 result1->shortest.next=0;
828 result1->shortest.distance=0;
829 result1->shortest.duration=0;
830 result1->quickest.prev=0;
831 result1->quickest.next=0;
832 result1->quickest.distance=0;
833 result1->quickest.duration=0;
834
835 insert_in_queue(results,result1);
836
837 /* Loop across all nodes in the queue */
838
839 while((result1=pop_from_queue(results)))
840 {
841 node1=result1->node;
842 shortest1=result1->shortest;
843 quickest1=result1->quickest;
844
845 segment=FindFirstSegment(segments,node1);
846
847 while(segment)
848 {
849 duration_t reversesegment_duration;
850
851 /* Reverse the segment and check it exists */
852
853 node_t reversenode;
854 Segment *reversesegment;
855
856 reversenode=segment->node2;
857 reversesegment=FindFirstSegment(segments,reversenode);
858
859 while(reversesegment && reversesegment->node2!=node1)
860 reversesegment=FindNextSegment(segments,reversesegment);
861
862 if(!reversesegment)
863 goto endloop;
864
865 if(reversesegment->distance==INVALID_DISTANCE)
866 goto endloop;
867
868 node2=reversesegment->node1;
869
870 if(shortest1.prev==node2 && quickest1.prev==node2)
871 goto endloop;
872
873 way=FindWay(ways,reversesegment->way);
874
875 if((way->allow&transport)!=transport)
876 goto endloop;
877
878 reversesegment_duration=Duration(reversesegment,way,transport);
879
880 shortest2.distance=shortest1.distance+reversesegment->distance;
881 shortest2.duration=shortest1.duration+reversesegment_duration;
882 quickest2.distance=quickest1.distance+reversesegment->distance;
883 quickest2.duration=quickest1.duration+reversesegment_duration;
884
885 result2=FindResult(results,node2);
886
887 if(!result2) /* New end node */
888 {
889 result2=InsertResult(results,node2);
890 result2->node=node2;
891 result2->shortest.prev=0;
892 result2->shortest.next=node1;
893 result2->shortest.distance=shortest2.distance;
894 result2->shortest.duration=shortest2.duration;
895 result2->quickest.prev=0;
896 result2->quickest.next=node1;
897 result2->quickest.distance=quickest2.distance;
898 result2->quickest.duration=quickest2.duration;
899
900 if(!FindNode(start,node2))
901 insert_in_queue(results,result2);
902 }
903 else
904 {
905 if(shortest2.distance<result2->shortest.distance ||
906 (shortest2.distance==result2->shortest.distance &&
907 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
908 {
909 result2->shortest.next=node1;
910 result2->shortest.distance=shortest2.distance;
911 result2->shortest.duration=shortest2.duration;
912
913 if(!FindNode(start,node2))
914 insert_in_queue(results,result2);
915 }
916
917 if(quickest2.duration<result2->quickest.duration ||
918 (quickest2.duration==result2->quickest.duration &&
919 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
920 {
921 result2->quickest.next=node1;
922 result2->quickest.distance=quickest2.distance;
923 result2->quickest.duration=quickest2.duration;
924
925 if(!FindNode(start,node2))
926 insert_in_queue(results,result2);
927 }
928 }
929
930 endloop:
931
932 segment=FindNextSegment(segments,segment);
933 }
934 }
935
936 return(results);
937 }
938
939
940 /*++++++++++++++++++++++++++++++++++++++
941 Print the optimum route between two nodes.
942
943 Results *CombineRoutes Returns the results from joining the super-nodes.
944
945 Results *results The set of results from the super-nodes.
946
947 Nodes *nodes The list of nodes.
948
949 Segments *segments The set of segments to use.
950
951 Ways *ways The list of ways.
952
953 node_t start The start node.
954
955 node_t finish The finish node.
956
957 wayallow_t transport The mode of transport.
958 ++++++++++++++++++++++++++++++++++++++*/
959
960 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport)
961 {
962 Result *result1,*result2,*result3,*result4;
963 Results *combined;
964
965 combined=NewResultsList();
966
967 print_progress=0;
968
969 /* Sort out the shortest */
970
971 result1=FindResult(results,start);
972
973 result3=InsertResult(combined,start);
974
975 result3->node=result1->node;
976
977 result3->shortest.distance=0;
978 result3->shortest.duration=0;
979 result3->shortest.next=0;
980 result3->shortest.prev=0;
981
982 do
983 {
984 if(result1->shortest.next)
985 {
986 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->shortest.next,transport);
987
988 result2=FindResult(results2,result1->node);
989
990 result3->shortest.next=result2->shortest.next;
991
992 result2=FindResult(results2,result2->shortest.next);
993
994 do
995 {
996 result4=InsertResult(combined,result2->node);
997
998 result4->node=result2->node;
999
1000 result4->shortest=result2->shortest;
1001 result4->shortest.distance+=result3->shortest.distance;
1002 result4->shortest.duration+=result3->shortest.duration;
1003
1004 if(result2->shortest.next)
1005 result2=FindResult(results2,result2->shortest.next);
1006 else
1007 result2=NULL;
1008 }
1009 while(result2);
1010
1011 FreeResultsList(results2);
1012
1013 result1=FindResult(results,result1->shortest.next);
1014
1015 result3=result4;
1016 }
1017 else
1018 result1=NULL;
1019 }
1020 while(result1);
1021
1022 /* Sort out the quickest */
1023
1024 result1=FindResult(results,start);
1025
1026 result3=FindResult(combined,start);
1027
1028 result3->quickest.distance=0;
1029 result3->quickest.duration=0;
1030 result3->quickest.next=0;
1031 result3->quickest.prev=0;
1032
1033 do
1034 {
1035 if(result1->quickest.next)
1036 {
1037 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->quickest.next,transport);
1038
1039 result2=FindResult(results2,result1->node);
1040
1041 result3->quickest.next=result2->quickest.next;
1042
1043 result2=FindResult(results2,result2->quickest.next);
1044
1045 do
1046 {
1047 result4=FindResult(combined,result2->node);
1048
1049 if(!result4)
1050 {
1051 result4=InsertResult(combined,result2->node);
1052
1053 result4->node=result2->node;
1054 }
1055
1056 result4->quickest=result2->quickest;
1057 result4->quickest.distance+=result3->quickest.distance;
1058 result4->quickest.duration+=result3->quickest.duration;
1059
1060 if(result2->quickest.next)
1061 result2=FindResult(results2,result2->quickest.next);
1062 else
1063 result2=NULL;
1064 }
1065 while(result2);
1066
1067 FreeResultsList(results2);
1068
1069 result1=FindResult(results,result1->quickest.next);
1070
1071 result3=result4;
1072 }
1073 else
1074 result1=NULL;
1075 }
1076 while(result1);
1077
1078 /* Now print out the result normally */
1079
1080 print_progress=1;
1081
1082 return(combined);
1083 }
1084
1085
1086 /*++++++++++++++++++++++++++++++++++++++
1087 Find all routes from a specified node to any node in the specified list that follows a certain type of way.
1088
1089 Results *FindRoutesWay Returns a set of results.
1090
1091 Nodes *nodes The set of nodes to use.
1092
1093 Segments *segments The set of segments to use.
1094
1095 Ways *ways The set of ways to use.
1096
1097 node_t start The start node.
1098
1099 Nodes *finish The finishing nodes.
1100
1101 Way *match The way that the route must match.
1102
1103 int iteration The iteration number in Super-Segment generation.
1104 ++++++++++++++++++++++++++++++++++++++*/
1105
1106 Results *FindRoutesWay(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,Way *match,int iteration)
1107 {
1108 Results *results;
1109 node_t node1,node2;
1110 HalfResult shortest1,quickest1;
1111 HalfResult shortest2,quickest2;
1112 Result *result1,*result2;
1113 Segment *segment;
1114 Way *way;
1115
1116 /* Insert the first node into the queue */
1117
1118 results=NewResultsList();
1119
1120 result1=InsertResult(results,start);
1121
1122 result1->node=start;
1123 result1->shortest.prev=0;
1124 result1->shortest.next=0;
1125 result1->shortest.distance=0;
1126 result1->shortest.duration=0;
1127 result1->quickest.prev=0;
1128 result1->quickest.next=0;
1129 result1->quickest.distance=0;
1130 result1->quickest.duration=0;
1131
1132 insert_in_queue(results,result1);
1133
1134 /* Loop across all nodes in the queue */
1135
1136 while((result1=pop_from_queue(results)))
1137 {
1138 node1=result1->node;
1139 shortest1=result1->shortest;
1140 quickest1=result1->quickest;
1141
1142 segment=FindFirstSegment(segments,node1);
1143
1144 while(segment)
1145 {
1146 duration_t segment_duration;
1147
1148 if(segment->distance==INVALID_DISTANCE)
1149 goto endloop;
1150
1151 node2=segment->node2;
1152
1153 if(shortest1.prev==node2 && quickest1.prev==node2)
1154 goto endloop;
1155
1156 way=FindWay(ways,segment->way);
1157
1158 if(way->type !=match->type ||
1159 way->allow!=match->allow ||
1160 way->limit!=match->limit)
1161 goto endloop;
1162
1163 segment_duration=0;
1164
1165 shortest2.distance=shortest1.distance+segment->distance;
1166 shortest2.duration=shortest1.duration+segment_duration;
1167 quickest2.distance=quickest1.distance+segment->distance;
1168 quickest2.duration=quickest1.duration+segment_duration;
1169
1170 result2=FindResult(results,node2);
1171
1172 if(!result2) /* New end node */
1173 {
1174 result2=InsertResult(results,node2);
1175 result2->node=node2;
1176 result2->shortest.prev=node1;
1177 result2->shortest.next=0;
1178 result2->shortest.distance=shortest2.distance;
1179 result2->shortest.duration=shortest2.duration;
1180 result2->quickest.prev=node1;
1181 result2->quickest.next=0;
1182 result2->quickest.distance=quickest2.distance;
1183 result2->quickest.duration=quickest2.duration;
1184
1185 if(!FindNode(finish,node2))
1186 insert_in_queue(results,result2);
1187 }
1188 else
1189 {
1190 if(shortest2.distance<result2->shortest.distance ||
1191 (shortest2.distance==result2->shortest.distance &&
1192 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
1193 {
1194 result2->shortest.prev=node1;
1195 result2->shortest.distance=shortest2.distance;
1196 result2->shortest.duration=shortest2.duration;
1197
1198 if(!FindNode(finish,node2))
1199 insert_in_queue(results,result2);
1200 }
1201
1202 if(quickest2.duration<result2->quickest.duration ||
1203 (quickest2.duration==result2->quickest.duration &&
1204 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
1205 {
1206 result2->quickest.prev=node1;
1207 result2->quickest.distance=quickest2.distance;
1208 result2->quickest.duration=quickest2.duration;
1209
1210 if(!FindNode(finish,node2))
1211 insert_in_queue(results,result2);
1212 }
1213 }
1214
1215 endloop:
1216
1217 segment=FindNextSegment(segments,segment);
1218 }
1219 }
1220
1221 return(results);
1222 }

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.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