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