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

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