Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 97 - (hide annotations) (download) (as text)
Sun Feb 1 17:11:08 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 32586 byte(s)
Rename some variable types.

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

Properties

Name Value
cvs:description Route optimiser.