Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/optimiser.c
Parent Directory
|
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)
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. |