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

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