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

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