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

Annotation of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log

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

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