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 105 - (hide annotations) (download) (as text)
Sat Feb 7 10:06:37 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 32331 byte(s)
Routing works with super-nodes now.

1 amb 2 /***************************************
2 amb 105 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.46 2009-02-07 10:06:37 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 105 if(profile->oneway && IsOnewayTo(segment,node1))
102 amb 64 goto endloop;
103    
104 amb 105 node2=OtherNode(segment,node1);
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 104 segment=NextSegment(segments,segment,node1);
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 105 if(profile->oneway && IsOnewayTo(segment,node1))
353 amb 64 goto endloop;
354    
355 amb 105 node2=OtherNode(segment,node1);
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 104 segment=NextSegment(segments,segment,node1);
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 99 float latitude,longitude;
599 amb 88 Node *node=LookupNode(nodes,result->node);
600 amb 43
601 amb 99 GetLatLong(nodes,node,&latitude,&longitude);
602 amb 55
603 amb 99 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",latitude,longitude);
604    
605 amb 43 if(result->shortest.prev)
606 amb 2 {
607 amb 6 Segment *segment;
608     Way *way;
609 amb 2
610 amb 95 segment=FirstSegment(segments,LookupNode(nodes,result->shortest.prev));
611 amb 104 while(NODE(segment->node2)!=result->node && NODE(segment->node1)!=result->node)
612     segment=NextSegment(segments,segment,result->shortest.prev);
613 amb 2
614 amb 96 way=LookupWay(ways,segment->way);
615 amb 6
616 amb 99 fprintf(textfile,"%8.4f %9.4f %8d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",latitude,longitude,
617 amb 90 result->node,IsSuperNode(node)?'*':' ',
618 amb 105 distance_to_km(DISTANCE(segment->distance)),duration_to_minutes(Duration(segment,way,profile)),
619 amb 34 distance_to_km(result->shortest.distance),duration_to_minutes(result->shortest.duration),
620 amb 82 profile->speed[HIGHWAY(way->type)],WayName(ways,way));
621 amb 34 }
622     else
623 amb 99 fprintf(textfile,"%8.4f %9.4f %8d%c %5.3f %5.2f %7.2f %5.1f\n",latitude,longitude,
624 amb 90 result->node,IsSuperNode(node)?'*':' ',
625 amb 34 0.0,0.0,0.0,0.0);
626 amb 2
627 amb 43 if(result->shortest.next)
628     result=FindResult(results,result->shortest.next);
629 amb 2 else
630     result=NULL;
631     }
632     while(result);
633    
634 amb 55 fprintf(gpxfile,"</trkseg>\n");
635     fprintf(gpxfile,"</trk>\n");
636     fprintf(gpxfile,"</gpx>\n");
637 amb 2
638 amb 55 fclose(textfile);
639     fclose(gpxfile);
640    
641 amb 2 /* Print the result for the quickest route */
642    
643 amb 55 textfile=fopen("quickest.txt","w");
644     gpxfile=fopen("quickest.gpx","w");
645 amb 2
646 amb 55 fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
647     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");
648     fprintf(gpxfile,"<trk>\n");
649     fprintf(gpxfile,"<trkseg>\n");
650    
651 amb 31 result=FindResult(results,start);
652 amb 2
653     do
654     {
655 amb 99 float latitude,longitude;
656 amb 88 Node *node=LookupNode(nodes,result->node);
657 amb 43
658 amb 99 GetLatLong(nodes,node,&latitude,&longitude);
659 amb 55
660 amb 99 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",latitude,longitude);
661    
662 amb 43 if(result->quickest.prev)
663 amb 2 {
664 amb 6 Segment *segment;
665     Way *way;
666 amb 2
667 amb 95 segment=FirstSegment(segments,LookupNode(nodes,result->quickest.prev));
668 amb 104 while(NODE(segment->node2)!=result->node && NODE(segment->node1)!=result->node)
669     segment=NextSegment(segments,segment,result->quickest.prev);
670 amb 2
671 amb 96 way=LookupWay(ways,segment->way);
672 amb 6
673 amb 99 fprintf(textfile,"%8.4f %9.4f %8d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",latitude,longitude,
674 amb 90 result->node,IsSuperNode(node)?'*':' ',
675 amb 105 distance_to_km(DISTANCE(segment->distance)),duration_to_minutes(Duration(segment,way,profile)),
676 amb 34 distance_to_km(result->quickest.distance),duration_to_minutes(result->quickest.duration),
677 amb 82 profile->speed[HIGHWAY(way->type)],WayName(ways,way));
678 amb 34 }
679     else
680 amb 99 fprintf(textfile,"%8.4f %9.4f %8d%c %5.3f %5.2f %7.2f %5.1f\n",latitude,longitude,
681 amb 90 result->node,IsSuperNode(node)?'*':' ',
682 amb 34 0.0,0.0,0.0,0.0);
683 amb 2
684 amb 43 if(result->quickest.next)
685     result=FindResult(results,result->quickest.next);
686 amb 2 else
687     result=NULL;
688     }
689     while(result);
690    
691 amb 55 fprintf(gpxfile,"</trkseg>\n");
692     fprintf(gpxfile,"</trk>\n");
693     fprintf(gpxfile,"</gpx>\n");
694    
695     fclose(textfile);
696     fclose(gpxfile);
697 amb 31 }
698 amb 3
699    
700 amb 31 /*++++++++++++++++++++++++++++++++++++++
701 amb 95 Find all routes from a specified node to any super-node.
702 amb 3
703 amb 54 Results *FindRoutes Returns a set of results.
704 amb 31
705     Nodes *nodes The set of nodes to use.
706    
707     Segments *segments The set of segments to use.
708    
709 amb 54 Ways *ways The set of ways to use.
710    
711 amb 96 index_t start The start node.
712 amb 31
713 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
714 amb 31 ++++++++++++++++++++++++++++++++++++++*/
715    
716 amb 96 Results *FindRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
717 amb 31 {
718     Results *results;
719 amb 96 index_t node1,node2;
720 amb 31 HalfResult shortest2,quickest2;
721     Result *result1,*result2;
722     Segment *segment;
723 amb 54 Way *way;
724 amb 31
725     /* Insert the first node into the queue */
726    
727 amb 71 results=NewResultsList(8);
728 amb 31
729     result1=InsertResult(results,start);
730    
731     result1->node=start;
732 amb 43 result1->shortest.prev=0;
733     result1->shortest.next=0;
734 amb 31 result1->shortest.distance=0;
735     result1->shortest.duration=0;
736 amb 43 result1->quickest.prev=0;
737     result1->quickest.next=0;
738 amb 31 result1->quickest.distance=0;
739     result1->quickest.duration=0;
740    
741 amb 79 insert_in_queue(result1);
742 amb 31
743     /* Loop across all nodes in the queue */
744    
745 amb 79 while((result1=pop_from_queue()))
746 amb 31 {
747 amb 43 node1=result1->node;
748 amb 31
749 amb 95 segment=FirstSegment(segments,LookupNode(nodes,node1));
750 amb 31
751     while(segment)
752     {
753 amb 59 duration_t segment_duration;
754    
755 amb 95 if(!IsNormalSegment(segment))
756     goto endloop;
757    
758 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
759 amb 64 goto endloop;
760    
761 amb 105 node2=OtherNode(segment,node1);
762 amb 31
763 amb 79 if(result1->shortest.prev==node2 && result1->quickest.prev==node2)
764 amb 64 goto endloop;
765    
766 amb 96 way=LookupWay(ways,segment->way);
767 amb 54
768 amb 82 if(!(way->allow&profile->allow))
769 amb 54 goto endloop;
770    
771 amb 82 if(!profile->highways[HIGHWAY(way->type)])
772 amb 75 goto endloop;
773    
774 amb 82 segment_duration=Duration(segment,way,profile);
775 amb 59
776 amb 82 shortest2.distance=result1->shortest.distance+DISTANCE(segment->distance);
777 amb 79 shortest2.duration=result1->shortest.duration+segment_duration;
778 amb 82 quickest2.distance=result1->quickest.distance+DISTANCE(segment->distance);
779 amb 79 quickest2.duration=result1->quickest.duration+segment_duration;
780 amb 31
781     result2=FindResult(results,node2);
782    
783     if(!result2) /* New end node */
784     {
785     result2=InsertResult(results,node2);
786     result2->node=node2;
787 amb 43 result2->shortest.prev=node1;
788     result2->shortest.next=0;
789 amb 31 result2->shortest.distance=shortest2.distance;
790     result2->shortest.duration=shortest2.duration;
791 amb 43 result2->quickest.prev=node1;
792     result2->quickest.next=0;
793 amb 31 result2->quickest.distance=quickest2.distance;
794     result2->quickest.duration=quickest2.duration;
795    
796 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
797 amb 79 insert_in_queue(result2);
798 amb 31 }
799     else
800     {
801     if(shortest2.distance<result2->shortest.distance ||
802     (shortest2.distance==result2->shortest.distance &&
803     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
804     {
805 amb 43 result2->shortest.prev=node1;
806 amb 31 result2->shortest.distance=shortest2.distance;
807     result2->shortest.duration=shortest2.duration;
808    
809 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
810 amb 79 insert_in_queue(result2);
811 amb 31 }
812    
813     if(quickest2.duration<result2->quickest.duration ||
814     (quickest2.duration==result2->quickest.duration &&
815     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
816     {
817 amb 43 result2->quickest.prev=node1;
818 amb 31 result2->quickest.distance=quickest2.distance;
819     result2->quickest.duration=quickest2.duration;
820    
821 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
822 amb 79 insert_in_queue(result2);
823 amb 31 }
824     }
825    
826     endloop:
827    
828 amb 104 segment=NextSegment(segments,segment,node1);
829 amb 31 }
830     }
831    
832     return(results);
833 amb 2 }
834    
835    
836     /*++++++++++++++++++++++++++++++++++++++
837 amb 95 Find all routes from any super-node to a specific node.
838 amb 34
839 amb 47 Results *FindReverseRoute Returns a set of results.
840 amb 34
841     Nodes *nodes The set of nodes to use.
842    
843     Segments *segments The set of segments to use.
844    
845 amb 54 Ways *ways The set of ways to use.
846    
847 amb 96 index_t finish The finishing node.
848 amb 54
849 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
850 amb 34 ++++++++++++++++++++++++++++++++++++++*/
851    
852 amb 96 Results *FindReverseRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
853 amb 34 {
854     Results *results;
855 amb 96 index_t node1,node2;
856 amb 34 HalfResult shortest2,quickest2;
857     Result *result1,*result2;
858     Segment *segment;
859 amb 54 Way *way;
860 amb 34
861     /* Insert the first node into the queue */
862    
863 amb 71 results=NewResultsList(8);
864 amb 34
865     result1=InsertResult(results,finish);
866    
867     result1->node=finish;
868 amb 43 result1->shortest.prev=0;
869     result1->shortest.next=0;
870 amb 34 result1->shortest.distance=0;
871     result1->shortest.duration=0;
872 amb 43 result1->quickest.prev=0;
873     result1->quickest.next=0;
874 amb 34 result1->quickest.distance=0;
875     result1->quickest.duration=0;
876    
877 amb 79 insert_in_queue(result1);
878 amb 34
879     /* Loop across all nodes in the queue */
880    
881 amb 79 while((result1=pop_from_queue()))
882 amb 34 {
883 amb 43 node1=result1->node;
884 amb 34
885 amb 95 segment=FirstSegment(segments,LookupNode(nodes,node1));
886 amb 34
887     while(segment)
888     {
889 amb 104 duration_t segment_duration;
890 amb 59
891 amb 104 if(!IsNormalSegment(segment))
892 amb 34 goto endloop;
893    
894 amb 105 if(profile->oneway && IsOnewayFrom(segment,node1))
895 amb 95 goto endloop;
896    
897 amb 105 node2=OtherNode(segment,node1);
898 amb 64
899 amb 95 if(result1->shortest.next==node2 && result1->quickest.next==node2)
900 amb 64 goto endloop;
901    
902 amb 104 way=LookupWay(ways,segment->way);
903 amb 54
904 amb 82 if(!(way->allow&profile->allow))
905 amb 54 goto endloop;
906    
907 amb 82 if(!profile->highways[HIGHWAY(way->type)])
908 amb 75 goto endloop;
909    
910 amb 104 segment_duration=Duration(segment,way,profile);
911 amb 59
912 amb 104 shortest2.distance=result1->shortest.distance+DISTANCE(segment->distance);
913     shortest2.duration=result1->shortest.duration+segment_duration;
914     quickest2.distance=result1->quickest.distance+DISTANCE(segment->distance);
915     quickest2.duration=result1->quickest.duration+segment_duration;
916 amb 34
917     result2=FindResult(results,node2);
918    
919     if(!result2) /* New end node */
920     {
921     result2=InsertResult(results,node2);
922     result2->node=node2;
923 amb 43 result2->shortest.prev=0;
924     result2->shortest.next=node1;
925 amb 34 result2->shortest.distance=shortest2.distance;
926     result2->shortest.duration=shortest2.duration;
927 amb 43 result2->quickest.prev=0;
928     result2->quickest.next=node1;
929 amb 34 result2->quickest.distance=quickest2.distance;
930     result2->quickest.duration=quickest2.duration;
931    
932 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
933 amb 79 insert_in_queue(result2);
934 amb 34 }
935     else
936     {
937     if(shortest2.distance<result2->shortest.distance ||
938     (shortest2.distance==result2->shortest.distance &&
939     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
940     {
941 amb 43 result2->shortest.next=node1;
942 amb 34 result2->shortest.distance=shortest2.distance;
943     result2->shortest.duration=shortest2.duration;
944    
945 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
946 amb 79 insert_in_queue(result2);
947 amb 34 }
948    
949     if(quickest2.duration<result2->quickest.duration ||
950     (quickest2.duration==result2->quickest.duration &&
951     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
952     {
953 amb 43 result2->quickest.next=node1;
954 amb 34 result2->quickest.distance=quickest2.distance;
955     result2->quickest.duration=quickest2.duration;
956    
957 amb 95 if(!IsSuperNode(LookupNode(nodes,node2)))
958 amb 79 insert_in_queue(result2);
959 amb 34 }
960     }
961    
962     endloop:
963    
964 amb 104 segment=NextSegment(segments,segment,node1);
965 amb 34 }
966     }
967    
968     return(results);
969     }
970    
971    
972     /*++++++++++++++++++++++++++++++++++++++
973 amb 95 Create an optimum route given the set of super-nodes to follow.
974 amb 31
975 amb 58 Results *CombineRoutes Returns the results from joining the super-nodes.
976 amb 55
977 amb 58 Results *results The set of results from the super-nodes.
978 amb 31
979     Nodes *nodes The list of nodes.
980    
981     Segments *segments The set of segments to use.
982    
983     Ways *ways The list of ways.
984    
985 amb 96 index_t start The start node.
986 amb 31
987 amb 96 index_t finish The finish node.
988 amb 54
989 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
990 amb 31 ++++++++++++++++++++++++++++++++++++++*/
991    
992 amb 96 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
993 amb 31 {
994     Result *result1,*result2,*result3,*result4;
995     Results *combined;
996    
997 amb 71 combined=NewResultsList(64);
998 amb 31
999     print_progress=0;
1000    
1001     /* Sort out the shortest */
1002    
1003     result1=FindResult(results,start);
1004    
1005 amb 58 result3=InsertResult(combined,start);
1006 amb 31
1007 amb 58 result3->node=result1->node;
1008 amb 36
1009 amb 58 result3->shortest.distance=0;
1010     result3->shortest.duration=0;
1011     result3->shortest.next=0;
1012     result3->shortest.prev=0;
1013 amb 31
1014 amb 58 do
1015     {
1016 amb 43 if(result1->shortest.next)
1017 amb 31 {
1018 amb 82 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->shortest.next,profile,0);
1019 amb 31
1020     result2=FindResult(results2,result1->node);
1021    
1022 amb 43 result3->shortest.next=result2->shortest.next;
1023 amb 36
1024 amb 43 result2=FindResult(results2,result2->shortest.next);
1025 amb 36
1026 amb 31 do
1027     {
1028 amb 58 result4=InsertResult(combined,result2->node);
1029 amb 31
1030 amb 58 result4->node=result2->node;
1031 amb 36
1032 amb 58 result4->shortest=result2->shortest;
1033     result4->shortest.distance+=result3->shortest.distance;
1034     result4->shortest.duration+=result3->shortest.duration;
1035 amb 31
1036 amb 43 if(result2->shortest.next)
1037     result2=FindResult(results2,result2->shortest.next);
1038 amb 31 else
1039     result2=NULL;
1040     }
1041     while(result2);
1042    
1043     FreeResultsList(results2);
1044    
1045 amb 43 result1=FindResult(results,result1->shortest.next);
1046 amb 58
1047     result3=result4;
1048 amb 31 }
1049     else
1050     result1=NULL;
1051     }
1052     while(result1);
1053    
1054     /* Sort out the quickest */
1055    
1056     result1=FindResult(results,start);
1057    
1058 amb 58 result3=FindResult(combined,start);
1059    
1060     result3->quickest.distance=0;
1061     result3->quickest.duration=0;
1062     result3->quickest.next=0;
1063     result3->quickest.prev=0;
1064    
1065 amb 31 do
1066     {
1067 amb 43 if(result1->quickest.next)
1068 amb 31 {
1069 amb 82 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->quickest.next,profile,0);
1070 amb 31
1071     result2=FindResult(results2,result1->node);
1072    
1073 amb 43 result3->quickest.next=result2->quickest.next;
1074 amb 36
1075 amb 43 result2=FindResult(results2,result2->quickest.next);
1076 amb 36
1077 amb 31 do
1078     {
1079 amb 58 result4=FindResult(combined,result2->node);
1080    
1081     if(!result4)
1082 amb 31 {
1083 amb 58 result4=InsertResult(combined,result2->node);
1084 amb 31
1085 amb 58 result4->node=result2->node;
1086     }
1087 amb 31
1088 amb 58 result4->quickest=result2->quickest;
1089     result4->quickest.distance+=result3->quickest.distance;
1090     result4->quickest.duration+=result3->quickest.duration;
1091 amb 36
1092 amb 43 if(result2->quickest.next)
1093     result2=FindResult(results2,result2->quickest.next);
1094 amb 31 else
1095     result2=NULL;
1096     }
1097     while(result2);
1098    
1099     FreeResultsList(results2);
1100    
1101 amb 43 result1=FindResult(results,result1->quickest.next);
1102 amb 58
1103     result3=result4;
1104 amb 31 }
1105     else
1106     result1=NULL;
1107     }
1108     while(result1);
1109    
1110     /* Now print out the result normally */
1111    
1112     print_progress=1;
1113    
1114 amb 55 return(combined);
1115 amb 31 }

Properties

Name Value
cvs:description Route optimiser.