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

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