Routino SVN Repository Browser

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

ViewVC logotype

Annotation of /branches/2.3.2-dev/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 828 - (hide annotations) (download) (as text)
Sun Aug 21 14:49:20 2011 UTC (13 years, 6 months ago) by amb
Original Path: trunk/src/optimiser.c
File MIME type: text/x-csrc
File size: 37285 byte(s)
Merge version 2.0.3 into working version.

1 amb 2 /***************************************
2     Routing optimiser.
3 amb 151
4     Part of the Routino routing software.
5 amb 2 ******************/ /******************
6 amb 594 This file Copyright 2008-2011 Andrew M. Bishop
7 amb 2
8 amb 151 This program is free software: you can redistribute it and/or modify
9     it under the terms of the GNU Affero General Public License as published by
10     the Free Software Foundation, either version 3 of the License, or
11     (at your option) any later version.
12    
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16     GNU Affero General Public License for more details.
17    
18     You should have received a copy of the GNU Affero General Public License
19     along with this program. If not, see <http://www.gnu.org/licenses/>.
20 amb 2 ***************************************/
21    
22    
23 amb 109 #include <stdio.h>
24 amb 712 #include <assert.h>
25 amb 2
26 amb 96 #include "types.h"
27 amb 109 #include "nodes.h"
28     #include "segments.h"
29     #include "ways.h"
30 amb 596 #include "relations.h"
31 amb 449
32 amb 519 #include "logging.h"
33 amb 449 #include "functions.h"
34 amb 532 #include "fakes.h"
35 amb 28 #include "results.h"
36 amb 2
37 amb 26
38 amb 685 /* Global variables */
39    
40 amb 113 /*+ The option not to print any progress information. +*/
41 amb 107 extern int option_quiet;
42 amb 2
43 amb 113 /*+ The option to calculate the quickest route insted of the shortest. +*/
44     extern int option_quickest;
45 amb 31
46 amb 113
47 amb 685 /* Local functions */
48    
49 amb 721 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t endnode,index_t endsegment);
50 amb 685
51    
52 amb 2 /*++++++++++++++++++++++++++++++++++++++
53 amb 727 Find the optimum route between two nodes not passing through a super-node.
54 amb 2
55 amb 238 Results *FindNormalRoute Returns a set of results.
56 amb 26
57     Nodes *nodes The set of nodes to use.
58    
59     Segments *segments The set of segments to use.
60    
61 amb 54 Ways *ways The set of ways to use.
62    
63 amb 542 Relations *relations The set of relations to use.
64    
65 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
66    
67 amb 605 index_t start_node The start node.
68 amb 2
69 amb 605 index_t prev_segment The previous segment before the start node.
70 amb 54
71 amb 605 index_t finish_node The finish node.
72 amb 2 ++++++++++++++++++++++++++++++++++++++*/
73    
74 amb 723 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node)
75 amb 2 {
76 amb 31 Results *results;
77 amb 469 Queue *queue;
78 amb 166 score_t finish_score;
79 amb 219 double finish_lat,finish_lon;
80 amb 605 Result *finish_result;
81 amb 469 Result *result1,*result2;
82 amb 2
83 amb 10 /* Set up the finish conditions */
84    
85 amb 176 finish_score=INF_SCORE;
86 amb 605 finish_result=NULL;
87 amb 10
88 amb 605 if(IsFakeNode(finish_node))
89     GetFakeLatLong(finish_node,&finish_lat,&finish_lon);
90 amb 303 else
91 amb 605 GetLatLong(nodes,finish_node,&finish_lat,&finish_lon);
92 amb 119
93 amb 165 /* Create the list of results and insert the first node into the queue */
94 amb 2
95 amb 238 results=NewResultsList(8);
96 amb 2
97 amb 605 results->start_node=start_node;
98 amb 617 results->prev_segment=prev_segment;
99 amb 165
100 amb 735 result1=InsertResult(results,results->start_node,results->prev_segment);
101 amb 28
102 amb 236 queue=NewQueueList();
103 amb 2
104 amb 236 InsertInQueue(queue,result1);
105    
106 amb 2 /* Loop across all nodes in the queue */
107    
108 amb 236 while((result1=PopFromQueue(queue)))
109 amb 2 {
110 amb 594 Segment *segment;
111 amb 637 index_t node1,seg1,seg1r;
112 amb 608 index_t turnrelation=NO_RELATION;
113 amb 594
114 amb 680 /* score must be better than current best score */
115 amb 238 if(result1->score>finish_score)
116 amb 119 continue;
117    
118 amb 43 node1=result1->node;
119 amb 605 seg1=result1->segment;
120 amb 2
121 amb 637 if(IsFakeSegment(seg1))
122     seg1r=IndexRealSegment(seg1);
123     else
124     seg1r=seg1;
125    
126 amb 680 /* lookup if a turn restriction applies */
127 amb 700 if(profile->turns && !IsFakeNode(node1) && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
128 amb 637 turnrelation=FindFirstTurnRelation2(relations,node1,seg1r);
129 amb 596
130 amb 680 /* Loop across all segments */
131    
132 amb 303 if(IsFakeNode(node1))
133     segment=FirstFakeSegment(node1);
134     else
135 amb 707 segment=FirstSegment(segments,nodes,node1,1);
136 amb 2
137     while(segment)
138     {
139 amb 594 Way *way;
140 amb 637 index_t node2,seg2,seg2r;
141 amb 298 score_t segment_pref,segment_score,cumulative_score;
142     int i;
143 amb 59
144 amb 680 node2=OtherNode(segment,node1); /* need this here because we use node2 at the end of the loop */
145 amb 303
146 amb 680 /* must be a normal segment */
147 amb 95 if(!IsNormalSegment(segment))
148 amb 90 goto endloop;
149    
150 amb 680 /* must obey one-way restrictions (unless profile allows) */
151 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
152 amb 64 goto endloop;
153    
154 amb 605 if(IsFakeNode(node1) || IsFakeNode(node2))
155 amb 637 {
156     seg2 =IndexFakeSegment(segment);
157     seg2r=IndexRealSegment(seg2);
158     }
159 amb 605 else
160 amb 637 {
161     seg2 =IndexSegment(segments,segment);
162     seg2r=seg2;
163     }
164 amb 603
165 amb 699 /* must not perform U-turn (unless profile allows) */
166 amb 727 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2))))
167 amb 636 goto endloop;
168    
169 amb 680 /* must obey turn relations */
170 amb 637 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1r,seg2r,profile->allow))
171 amb 608 goto endloop;
172 amb 596
173 amb 723 /* must not pass over super-node */
174     if(node2!=finish_node && !IsFakeNode(node2) && IsSuperNode(LookupNode(nodes,node2,2)))
175 amb 238 goto endloop;
176    
177 amb 460 way=LookupWay(ways,segment->way,1);
178 amb 54
179 amb 680 /* mode of transport must be allowed on the highway */
180 amb 82 if(!(way->allow&profile->allow))
181 amb 54 goto endloop;
182    
183 amb 680 /* must obey weight restriction (if exists) */
184 amb 197 if(way->weight && way->weight<profile->weight)
185 amb 135 goto endloop;
186    
187 amb 680 /* must obey height/width/length restriction (if exists) */
188 amb 197 if((way->height && way->height<profile->height) ||
189     (way->width && way->width <profile->width ) ||
190     (way->length && way->length<profile->length))
191 amb 135 goto endloop;
192    
193 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
194    
195     for(i=1;i<Property_Count;i++)
196 amb 460 if(ways->file.props & PROPERTIES(i))
197 amb 307 {
198 amb 406 if(way->props & PROPERTIES(i))
199 amb 307 segment_pref*=profile->props_yes[i];
200     else
201     segment_pref*=profile->props_no[i];
202     }
203 amb 298
204 amb 680 /* profile preferences must allow this highway */
205 amb 298 if(segment_pref==0)
206     goto endloop;
207    
208 amb 680 /* mode of transport must be allowed through node2 */
209 amb 471 if(!IsFakeNode(node2))
210     {
211 amb 595 Node *node=LookupNode(nodes,node2,2);
212 amb 469
213 amb 471 if(!(node->allow&profile->allow))
214     goto endloop;
215     }
216 amb 469
217 amb 166 if(option_quickest==0)
218 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
219 amb 166 else
220 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
221 amb 59
222 amb 170 cumulative_score=result1->score+segment_score;
223 amb 166
224 amb 680 /* score must be better than current best score */
225 amb 166 if(cumulative_score>finish_score)
226 amb 2 goto endloop;
227    
228 amb 605 result2=FindResult(results,node2,seg2);
229 amb 42
230 amb 680 if(!result2) /* New end node/segment combination */
231 amb 2 {
232 amb 605 result2=InsertResult(results,node2,seg2);
233     result2->prev=result1;
234 amb 170 result2->score=cumulative_score;
235 amb 2
236 amb 605 if(node2==finish_node)
237 amb 2 {
238 amb 605 if(cumulative_score<finish_score)
239     {
240     finish_score=cumulative_score;
241     finish_result=result2;
242     }
243 amb 2 }
244     else
245 amb 119 {
246 amb 238 result2->sortby=result2->score;
247 amb 166
248 amb 236 InsertInQueue(queue,result2);
249 amb 119 }
250 amb 2 }
251 amb 605 else if(cumulative_score<result2->score) /* New score for end node/segment combination is better */
252 amb 2 {
253 amb 605 result2->prev=result1;
254 amb 170 result2->score=cumulative_score;
255 amb 605 result2->segment=seg2;
256 amb 166
257 amb 605 if(node2==finish_node)
258 amb 2 {
259 amb 605 if(cumulative_score<finish_score)
260     {
261     finish_score=cumulative_score;
262     finish_result=result2;
263     }
264 amb 2 }
265 amb 166 else
266     {
267 amb 238 result2->sortby=result2->score;
268 amb 2
269 amb 238 if(result2->score<finish_score)
270 amb 236 InsertInQueue(queue,result2);
271 amb 2 }
272     }
273    
274     endloop:
275    
276 amb 303 if(IsFakeNode(node1))
277     segment=NextFakeSegment(segment,node1);
278     else if(IsFakeNode(node2))
279     segment=NULL; /* cannot call NextSegment() with a fake segment */
280     else
281     {
282     segment=NextSegment(segments,segment,node1);
283    
284 amb 605 if(!segment && IsFakeNode(finish_node))
285     segment=ExtraFakeSegment(node1,finish_node);
286 amb 303 }
287 amb 2 }
288     }
289    
290 amb 236 FreeQueueList(queue);
291    
292 amb 77 /* Check it worked */
293    
294 amb 605 if(!finish_result)
295 amb 77 {
296     FreeResultsList(results);
297     return(NULL);
298     }
299    
300 amb 605 FixForwardRoute(results,finish_result);
301 amb 31
302     return(results);
303 amb 2 }
304    
305    
306     /*++++++++++++++++++++++++++++++++++++++
307 amb 680 Find the optimum route between two nodes where the start and end are a set of pre/post-routed super-nodes.
308 amb 34
309 amb 238 Results *FindMiddleRoute Returns a set of results.
310 amb 34
311 amb 95 Nodes *nodes The set of nodes to use.
312 amb 34
313 amb 95 Segments *segments The set of segments to use.
314 amb 34
315 amb 95 Ways *ways The set of ways to use.
316 amb 54
317 amb 542 Relations *relations The set of relations to use.
318    
319 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
320    
321 amb 34 Results *begin The initial portion of the route.
322    
323     Results *end The final portion of the route.
324     ++++++++++++++++++++++++++++++++++++++*/
325    
326 amb 721 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,Results *begin,Results *end)
327 amb 34 {
328     Results *results;
329 amb 469 Queue *queue;
330 amb 605 Result *finish_result;
331 amb 166 score_t finish_score;
332 amb 219 double finish_lat,finish_lon;
333 amb 632 Result *result1,*result2,*result3,*result4;
334 amb 34
335 amb 227 if(!option_quiet)
336 amb 519 printf_first("Routing: Super-Nodes checked = 0");
337 amb 227
338 amb 34 /* Set up the finish conditions */
339    
340 amb 302 finish_score=INF_DISTANCE;
341 amb 605 finish_result=NULL;
342 amb 34
343 amb 605 if(IsFakeNode(end->finish_node))
344     GetFakeLatLong(end->finish_node,&finish_lat,&finish_lon);
345 amb 303 else
346 amb 605 GetLatLong(nodes,end->finish_node,&finish_lat,&finish_lon);
347 amb 119
348 amb 165 /* Create the list of results and insert the first node into the queue */
349 amb 34
350 amb 441 results=NewResultsList(2048);
351 amb 34
352 amb 605 results->start_node=begin->start_node;
353     results->prev_segment=begin->prev_segment;
354 amb 34
355 amb 688 if(begin->number==1)
356     {
357 amb 828 if(begin->prev_segment==NO_SEGMENT)
358     results->prev_segment=NO_SEGMENT;
359     else
360     {
361     index_t superseg=FindSuperSegment(nodes,segments,ways,relations,profile,begin->start_node,begin->prev_segment);
362 amb 34
363 amb 828 results->prev_segment=superseg;
364     }
365 amb 688 }
366    
367     result1=InsertResult(results,results->start_node,results->prev_segment);
368    
369 amb 236 queue=NewQueueList();
370    
371 amb 685 /* Insert the finish points of the beginning part of the path into the queue,
372     translating the segments into super-segments. */
373 amb 34
374 amb 79 result3=FirstResult(begin);
375    
376     while(result3)
377     {
378 amb 735 if((results->start_node!=result3->node || results->prev_segment!=result3->segment) &&
379 amb 722 !IsFakeNode(result3->node) && IsSuperNode(LookupNode(nodes,result3->node,1)))
380 amb 45 {
381 amb 722 Result *result5=result1;
382 amb 721 index_t superseg=FindSuperSegment(nodes,segments,ways,relations,profile,result3->node,result3->segment);
383 amb 34
384 amb 722 if(superseg!=result3->segment)
385     {
386     result5=InsertResult(results,result3->node,result3->segment);
387    
388     result5->prev=result1;
389     }
390    
391 amb 703 if(!FindResult(results,result3->node,superseg))
392     {
393     result2=InsertResult(results,result3->node,superseg);
394 amb 722 result2->prev=result5;
395 amb 685
396 amb 703 result2->score=result3->score;
397     result2->sortby=result3->score;
398 amb 119
399 amb 703 InsertInQueue(queue,result2);
400 amb 632
401 amb 703 if((result4=FindResult(end,result2->node,result2->segment)))
402 amb 632 {
403 amb 703 if((result2->score+result4->score)<finish_score)
404     {
405     finish_score=result2->score+result4->score;
406     finish_result=result2;
407     }
408 amb 632 }
409     }
410 amb 45 }
411 amb 34
412 amb 79 result3=NextResult(begin,result3);
413     }
414    
415 amb 238 if(begin->number==1)
416     InsertInQueue(queue,result1);
417    
418 amb 95 /* Loop across all nodes in the queue */
419 amb 34
420 amb 236 while((result1=PopFromQueue(queue)))
421 amb 34 {
422 amb 605 index_t node1,seg1;
423 amb 594 Segment *segment;
424 amb 596 index_t turnrelation=NO_RELATION;
425 amb 594
426 amb 680 /* score must be better than current best score */
427 amb 238 if(result1->score>finish_score)
428 amb 119 continue;
429    
430 amb 43 node1=result1->node;
431 amb 605 seg1=result1->segment;
432 amb 34
433 amb 680 /* lookup if a turn restriction applies */
434 amb 700 if(profile->turns && IsTurnRestrictedNode(LookupNode(nodes,node1,1))) /* node1 cannot be a fake node (must be a super-node) */
435 amb 605 turnrelation=FindFirstTurnRelation2(relations,node1,seg1);
436 amb 596
437 amb 680 /* Loop across all segments */
438 amb 34
439 amb 707 segment=FirstSegment(segments,nodes,node1,1); /* node1 cannot be a fake node (must be a super-node) */
440 amb 680
441 amb 34 while(segment)
442     {
443 amb 610 Way *way;
444     Node *node;
445 amb 603 index_t node2,seg2;
446 amb 298 score_t segment_pref,segment_score,cumulative_score;
447     int i;
448 amb 59
449 amb 680 /* must be a super segment */
450 amb 95 if(!IsSuperSegment(segment))
451     goto endloop;
452    
453 amb 680 /* must obey one-way restrictions (unless profile allows) */
454 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
455 amb 64 goto endloop;
456    
457 amb 105 node2=OtherNode(segment,node1);
458 amb 34
459 amb 680 seg2=IndexSegment(segments,segment); /* node2 cannot be a fake node (must be a super-node) */
460 amb 603
461 amb 699 /* must not perform U-turn */
462 amb 680 if(seg1==seg2) /* No fake segments, applies to all profiles */
463 amb 636 goto endloop;
464    
465 amb 680 /* must obey turn relations */
466 amb 605 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1,seg2,profile->allow))
467 amb 596 goto endloop;
468    
469 amb 460 way=LookupWay(ways,segment->way,1);
470 amb 54
471 amb 680 /* transport must be allowed on the highway */
472 amb 82 if(!(way->allow&profile->allow))
473 amb 54 goto endloop;
474    
475 amb 680 /* must obey weight restriction (if exists) */
476 amb 197 if(way->weight && way->weight<profile->weight)
477 amb 135 goto endloop;
478    
479 amb 680 /* must obey height/width/length restriction (if exists) */
480 amb 197 if((way->height && way->height<profile->height) ||
481     (way->width && way->width <profile->width ) ||
482     (way->length && way->length<profile->length))
483 amb 135 goto endloop;
484    
485 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
486    
487     for(i=1;i<Property_Count;i++)
488 amb 460 if(ways->file.props & PROPERTIES(i))
489 amb 307 {
490 amb 406 if(way->props & PROPERTIES(i))
491 amb 307 segment_pref*=profile->props_yes[i];
492     else
493     segment_pref*=profile->props_no[i];
494     }
495 amb 298
496 amb 680 /* profile preferences must allow this highway */
497 amb 298 if(segment_pref==0)
498     goto endloop;
499    
500 amb 680 node=LookupNode(nodes,node2,2); /* node2 cannot be a fake node (must be a super-node) */
501 amb 469
502 amb 680 /* mode of transport must be allowed through node2 */
503 amb 470 if(!(node->allow&profile->allow))
504 amb 469 goto endloop;
505    
506 amb 166 if(option_quickest==0)
507 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
508 amb 166 else
509 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
510 amb 34
511 amb 170 cumulative_score=result1->score+segment_score;
512 amb 166
513 amb 680 /* score must be better than current best score */
514 amb 166 if(cumulative_score>finish_score)
515 amb 34 goto endloop;
516    
517 amb 605 result2=FindResult(results,node2,seg2);
518 amb 42
519 amb 680 if(!result2) /* New end node/segment pair */
520 amb 34 {
521 amb 605 result2=InsertResult(results,node2,seg2);
522     result2->prev=result1;
523 amb 170 result2->score=cumulative_score;
524 amb 34
525 amb 605 if((result3=FindResult(end,node2,seg2)))
526 amb 113 {
527 amb 442 if((result2->score+result3->score)<finish_score)
528     {
529     finish_score=result2->score+result3->score;
530 amb 605 finish_result=result2;
531 amb 442 }
532 amb 113 }
533     else
534 amb 119 {
535 amb 219 double lat,lon;
536 amb 166 distance_t direct;
537    
538 amb 680 GetLatLong(nodes,node2,&lat,&lon); /* node2 cannot be a fake node (must be a super-node) */
539    
540 amb 166 direct=Distance(lat,lon,finish_lat,finish_lon);
541 amb 119
542     if(option_quickest==0)
543 amb 173 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
544 amb 119 else
545 amb 173 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
546 amb 119
547 amb 236 InsertInQueue(queue,result2);
548 amb 119 }
549 amb 34 }
550 amb 605 else if(cumulative_score<result2->score) /* New end node/segment pair is better */
551 amb 34 {
552 amb 605 result2->prev=result1;
553 amb 170 result2->score=cumulative_score;
554 amb 166
555 amb 605 if((result3=FindResult(end,node2,seg2)))
556 amb 34 {
557 amb 166 if((result2->score+result3->score)<finish_score)
558 amb 113 {
559 amb 166 finish_score=result2->score+result3->score;
560 amb 605 finish_result=result2;
561 amb 113 }
562 amb 34 }
563 amb 238 else if(result2->score<finish_score)
564 amb 34 {
565 amb 219 double lat,lon;
566 amb 166 distance_t direct;
567 amb 34
568 amb 680 GetLatLong(nodes,node2,&lat,&lon); /* node2 cannot be a fake node (must be a super-node) */
569    
570 amb 166 direct=Distance(lat,lon,finish_lat,finish_lon);
571    
572     if(option_quickest==0)
573 amb 173 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
574 amb 113 else
575 amb 173 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
576 amb 119
577 amb 238 InsertInQueue(queue,result2);
578 amb 34 }
579     }
580    
581 amb 757 if(!option_quiet && !(results->number%1000))
582 amb 519 printf_middle("Routing: Super-Nodes checked = %d",results->number);
583 amb 34
584 amb 627 endloop:
585    
586 amb 680 segment=NextSegment(segments,segment,node1); /* node1 cannot be a fake node (must be a super-node) */
587 amb 34 }
588     }
589    
590 amb 107 if(!option_quiet)
591 amb 519 printf_last("Routing: Super-Nodes checked = %d",results->number);
592 amb 34
593 amb 236 FreeQueueList(queue);
594    
595 amb 77 /* Check it worked */
596    
597 amb 605 if(!finish_result)
598 amb 77 {
599     FreeResultsList(results);
600     return(NULL);
601     }
602    
603 amb 680 /* Finish off the end part of the route */
604 amb 34
605 amb 616 if(finish_result->node!=end->finish_node)
606     {
607     result3=InsertResult(results,end->finish_node,NO_SEGMENT);
608 amb 605
609 amb 616 result3->prev=finish_result;
610     result3->score=finish_score;
611 amb 605
612 amb 616 finish_result=result3;
613     }
614 amb 605
615 amb 616 FixForwardRoute(results,finish_result);
616    
617 amb 34 return(results);
618     }
619    
620    
621     /*++++++++++++++++++++++++++++++++++++++
622 amb 685 Find the super-segment that represents the route that contains a particular segment.
623    
624     index_t FindSuperSegment Returns the index of the super-segment.
625    
626     Nodes *nodes The set of nodes to use.
627    
628     Segments *segments The set of segments to use.
629    
630     Ways *ways The set of ways to use.
631    
632     Relations *relations The set of relations to use.
633    
634 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
635    
636 amb 685 index_t endnode The super-node that the route ends at.
637    
638     index_t endsegment The segment that the route ends with.
639     ++++++++++++++++++++++++++++++++++++++*/
640    
641 amb 721 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t endnode,index_t endsegment)
642 amb 685 {
643     Segment *segment;
644    
645 amb 699 if(IsFakeSegment(endsegment))
646     endsegment=IndexRealSegment(endsegment);
647    
648 amb 707 segment=LookupSegment(segments,endsegment,2);
649 amb 687
650     if(IsSuperSegment(segment))
651     return(endsegment);
652    
653 amb 685 /* Loop across all segments */
654    
655 amb 710 segment=FirstSegment(segments,nodes,endnode,3); /* endnode cannot be a fake node (must be a super-node) */
656 amb 685
657     while(segment)
658     {
659     if(IsSuperSegment(segment))
660     {
661     Results *results;
662     index_t startnode;
663    
664     startnode=OtherNode(segment,endnode);
665    
666 amb 723 results=FindNormalRoute(nodes,segments,ways,relations,profile,startnode,NO_SEGMENT,endnode);
667 amb 685
668     if(results && results->last_segment==endsegment)
669 amb 798 {
670     FreeResultsList(results);
671 amb 685 return(IndexSegment(segments,segment));
672 amb 798 }
673    
674     if(results)
675     FreeResultsList(results);
676 amb 685 }
677    
678     segment=NextSegment(segments,segment,endnode); /* endnode cannot be a fake node (must be a super-node) */
679     }
680    
681 amb 687 return(endsegment);
682 amb 685 }
683    
684    
685     /*++++++++++++++++++++++++++++++++++++++
686 amb 95 Find all routes from a specified node to any super-node.
687 amb 3
688 amb 126 Results *FindStartRoutes Returns a set of results.
689 amb 31
690     Nodes *nodes The set of nodes to use.
691    
692     Segments *segments The set of segments to use.
693    
694 amb 54 Ways *ways The set of ways to use.
695    
696 amb 542 Relations *relations The set of relations to use.
697    
698 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
699    
700 amb 605 index_t start_node The start node.
701 amb 31
702 amb 605 index_t prev_segment The previous segment before the start node.
703    
704 amb 729 index_t finish_node The finish node.
705    
706     int *nsuper Returns the number of super-nodes seen.
707 amb 31 ++++++++++++++++++++++++++++++++++++++*/
708    
709 amb 734 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t start_node,index_t prev_segment,index_t finish_node,int *nsuper)
710 amb 31 {
711     Results *results;
712 amb 469 Queue *queue;
713     Result *result1,*result2;
714 amb 734 int found_finish=0;
715 amb 31
716 amb 531 /* Create the results and insert the start node */
717 amb 31
718 amb 71 results=NewResultsList(8);
719 amb 31
720 amb 605 results->start_node=start_node;
721     results->prev_segment=prev_segment;
722 amb 165
723 amb 735 result1=InsertResult(results,results->start_node,results->prev_segment);
724 amb 31
725 amb 734 /* Take a shortcut if the first node is a super-node. */
726 amb 531
727 amb 734 if(!IsFakeNode(start_node) && IsSuperNode(LookupNode(nodes,start_node,1)))
728 amb 531 return(results);
729    
730     /* Insert the first node into the queue */
731    
732 amb 236 queue=NewQueueList();
733 amb 31
734 amb 236 InsertInQueue(queue,result1);
735    
736 amb 31 /* Loop across all nodes in the queue */
737    
738 amb 236 while((result1=PopFromQueue(queue)))
739 amb 31 {
740 amb 637 index_t node1,seg1,seg1r;
741 amb 594 Segment *segment;
742 amb 719 index_t turnrelation=NO_RELATION;
743 amb 594
744 amb 43 node1=result1->node;
745 amb 605 seg1=result1->segment;
746 amb 31
747 amb 637 if(IsFakeSegment(seg1))
748     seg1r=IndexRealSegment(seg1);
749     else
750     seg1r=seg1;
751    
752 amb 719 /* lookup if a turn restriction applies */
753     if(profile->turns && !IsFakeNode(node1) && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
754     turnrelation=FindFirstTurnRelation2(relations,node1,seg1r);
755 amb 680
756     /* Loop across all segments */
757    
758 amb 303 if(IsFakeNode(node1))
759     segment=FirstFakeSegment(node1);
760     else
761 amb 707 segment=FirstSegment(segments,nodes,node1,1);
762 amb 31
763     while(segment)
764     {
765 amb 610 Way *way;
766 amb 637 index_t node2,seg2,seg2r;
767 amb 298 score_t segment_pref,segment_score,cumulative_score;
768     int i;
769 amb 59
770 amb 734 node2=OtherNode(segment,node1); /* need this here because we use node2 at the end of the loop */
771    
772 amb 680 /* must be a normal segment */
773 amb 95 if(!IsNormalSegment(segment))
774     goto endloop;
775    
776 amb 680 /* must obey one-way restrictions (unless profile allows) */
777 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
778 amb 64 goto endloop;
779    
780 amb 605 if(IsFakeNode(node1) || IsFakeNode(node2))
781 amb 637 {
782     seg2 =IndexFakeSegment(segment);
783     seg2r=IndexRealSegment(seg2);
784     }
785 amb 605 else
786 amb 637 {
787     seg2 =IndexSegment(segments,segment);
788     seg2r=seg2;
789     }
790 amb 603
791 amb 699 /* must not perform U-turn (unless profile allows) */
792 amb 734 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2))))
793 amb 636 goto endloop;
794    
795 amb 719 /* must obey turn relations */
796     if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1r,seg2r,profile->allow))
797     goto endloop;
798 amb 596
799 amb 460 way=LookupWay(ways,segment->way,1);
800 amb 54
801 amb 680 /* mode of transport must be allowed on the highway */
802 amb 82 if(!(way->allow&profile->allow))
803 amb 54 goto endloop;
804    
805 amb 680 /* must obey weight restriction (if exists) */
806 amb 197 if(way->weight && way->weight<profile->weight)
807 amb 135 goto endloop;
808    
809 amb 680 /* must obey height/width/length restriction (if exists) */
810 amb 197 if((way->height && way->height<profile->height) ||
811     (way->width && way->width <profile->width ) ||
812     (way->length && way->length<profile->length))
813 amb 135 goto endloop;
814    
815 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
816    
817     for(i=1;i<Property_Count;i++)
818 amb 460 if(ways->file.props & PROPERTIES(i))
819 amb 307 {
820 amb 406 if(way->props & PROPERTIES(i))
821 amb 307 segment_pref*=profile->props_yes[i];
822     else
823     segment_pref*=profile->props_no[i];
824     }
825 amb 298
826 amb 680 /* profile preferences must allow this highway */
827 amb 298 if(segment_pref==0)
828     goto endloop;
829    
830 amb 680 /* mode of transport must be allowed through node2 */
831 amb 471 if(!IsFakeNode(node2))
832     {
833 amb 595 Node *node=LookupNode(nodes,node2,2);
834 amb 469
835 amb 471 if(!(node->allow&profile->allow))
836     goto endloop;
837     }
838 amb 469
839 amb 166 if(option_quickest==0)
840 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
841 amb 166 else
842 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
843 amb 59
844 amb 170 cumulative_score=result1->score+segment_score;
845 amb 166
846 amb 605 result2=FindResult(results,node2,seg2);
847 amb 31
848 amb 680 if(!result2) /* New end node/segment combination */
849 amb 31 {
850 amb 605 result2=InsertResult(results,node2,seg2);
851     result2->prev=result1;
852 amb 170 result2->score=cumulative_score;
853 amb 31
854 amb 729 if(!IsFakeNode(node2) && IsSuperNode(LookupNode(nodes,node2,2)))
855     (*nsuper)++;
856    
857 amb 734 if(!IsFakeNode(node2) && !IsSuperNode(LookupNode(nodes,node2,2)))
858 amb 119 {
859 amb 166 result2->sortby=result2->score;
860 amb 236 InsertInQueue(queue,result2);
861 amb 119 }
862 amb 734
863     if(node2==finish_node)
864     found_finish=1;
865 amb 31 }
866 amb 605 else if(cumulative_score<result2->score) /* New end node/segment combination is better */
867 amb 31 {
868 amb 605 result2->prev=result1;
869 amb 170 result2->score=cumulative_score;
870 amb 31
871 amb 734 if(!IsFakeNode(node2) && !IsSuperNode(LookupNode(nodes,node2,2)))
872 amb 31 {
873 amb 166 result2->sortby=result2->score;
874 amb 236 InsertInQueue(queue,result2);
875 amb 31 }
876     }
877    
878     endloop:
879    
880 amb 303 if(IsFakeNode(node1))
881     segment=NextFakeSegment(segment,node1);
882 amb 729 else if(IsFakeNode(node2))
883     segment=NULL; /* cannot call NextSegment() with a fake segment */
884 amb 303 else
885 amb 729 {
886 amb 303 segment=NextSegment(segments,segment,node1);
887 amb 678
888 amb 729 if(!segment && IsFakeNode(finish_node))
889     segment=ExtraFakeSegment(node1,finish_node);
890     }
891 amb 31 }
892     }
893    
894 amb 236 FreeQueueList(queue);
895    
896 amb 112 /* Check it worked */
897    
898 amb 734 if(results->number==1 || (*nsuper==0 && found_finish==0))
899 amb 112 {
900     FreeResultsList(results);
901     return(NULL);
902     }
903    
904 amb 31 return(results);
905 amb 2 }
906    
907    
908     /*++++++++++++++++++++++++++++++++++++++
909 amb 680 Find all routes from any super-node to a specific node (by working backwards from the specific node to all super-nodes).
910 amb 34
911 amb 126 Results *FindFinishRoutes Returns a set of results.
912 amb 34
913     Nodes *nodes The set of nodes to use.
914    
915     Segments *segments The set of segments to use.
916    
917 amb 54 Ways *ways The set of ways to use.
918    
919 amb 542 Relations *relations The set of relations to use.
920    
921 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
922    
923 amb 605 index_t finish_node The finishing node.
924 amb 34 ++++++++++++++++++++++++++++++++++++++*/
925    
926 amb 721 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,index_t finish_node)
927 amb 34 {
928 amb 605 Results *results,*results2;
929 amb 469 Queue *queue;
930 amb 605 Result *result1,*result2,*result3;
931 amb 34
932 amb 531 /* Create the results and insert the finish node */
933 amb 34
934 amb 71 results=NewResultsList(8);
935 amb 34
936 amb 605 results->finish_node=finish_node;
937 amb 165
938 amb 605 result1=InsertResult(results,finish_node,NO_SEGMENT);
939 amb 34
940 amb 531 /* Insert the first node into the queue */
941    
942 amb 236 queue=NewQueueList();
943 amb 34
944 amb 236 InsertInQueue(queue,result1);
945    
946 amb 34 /* Loop across all nodes in the queue */
947    
948 amb 236 while((result1=PopFromQueue(queue)))
949 amb 34 {
950 amb 637 index_t node1,seg1,seg1r;
951 amb 594 Segment *segment;
952 amb 596 index_t turnrelation=NO_RELATION;
953 amb 594
954 amb 43 node1=result1->node;
955 amb 605 seg1=result1->segment;
956 amb 34
957 amb 637 if(IsFakeSegment(seg1))
958     seg1r=IndexRealSegment(seg1);
959     else
960     seg1r=seg1;
961    
962 amb 680 /* lookup if a turn restriction applies */
963 amb 700 if(profile->turns && !IsFakeNode(node1) && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
964 amb 596 turnrelation=FindFirstTurnRelation1(relations,node1); /* working backwards => turn relation sort order doesn't help */
965    
966 amb 680 /* Loop across all segments */
967    
968 amb 303 if(IsFakeNode(node1))
969     segment=FirstFakeSegment(node1);
970     else
971 amb 707 segment=FirstSegment(segments,nodes,node1,1);
972 amb 34
973     while(segment)
974     {
975 amb 610 Way *way;
976 amb 637 index_t node2,seg2,seg2r;
977 amb 298 score_t segment_pref,segment_score,cumulative_score;
978     int i;
979 amb 59
980 amb 680 /* must be a normal segment */
981 amb 632 if((IsFakeNode(node1) || !IsSuperNode(LookupNode(nodes,node1,1))) && !IsNormalSegment(segment))
982 amb 34 goto endloop;
983    
984 amb 680 /* must obey one-way restrictions (unless profile allows) */
985 amb 596 if(profile->oneway && IsOnewayFrom(segment,node1)) /* Disallow oneway from node2 *to* node1 */
986 amb 95 goto endloop;
987    
988 amb 105 node2=OtherNode(segment,node1);
989 amb 64
990 amb 605 if(IsFakeNode(node1) || IsFakeNode(node2))
991 amb 637 {
992     seg2 =IndexFakeSegment(segment);
993     seg2r=IndexRealSegment(seg2);
994     }
995 amb 605 else
996 amb 637 {
997     seg2 =IndexSegment(segments,segment);
998     seg2r=seg2;
999     }
1000 amb 605
1001 amb 699 /* must not perform U-turn (unless profile allows) */
1002 amb 727 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2 || (seg1r==seg2r && IsFakeUTurn(seg1,seg2))))
1003 amb 636 goto endloop;
1004    
1005 amb 680 /* must obey turn relations */
1006 amb 596 if(turnrelation!=NO_RELATION)
1007     {
1008 amb 637 index_t turnrelation2=FindFirstTurnRelation2(relations,node1,seg2r); /* node2 -> node1 -> result1->next->node */
1009 amb 596
1010 amb 637 if(turnrelation2!=NO_RELATION && !IsTurnAllowed(relations,turnrelation2,node1,seg2r,seg1r,profile->allow))
1011 amb 596 goto endloop;
1012     }
1013    
1014 amb 460 way=LookupWay(ways,segment->way,1);
1015 amb 54
1016 amb 680 /* mode of transport must be allowed on the highway */
1017 amb 82 if(!(way->allow&profile->allow))
1018 amb 54 goto endloop;
1019    
1020 amb 680 /* must obey weight restriction (if exists) */
1021 amb 197 if(way->weight && way->weight<profile->weight)
1022 amb 135 goto endloop;
1023    
1024 amb 680 /* must obey height/width/length restriction (if exists) */
1025 amb 197 if((way->height && way->height<profile->height) ||
1026     (way->width && way->width <profile->width ) ||
1027     (way->length && way->length<profile->length))
1028 amb 135 goto endloop;
1029    
1030 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
1031    
1032     for(i=1;i<Property_Count;i++)
1033 amb 460 if(ways->file.props & PROPERTIES(i))
1034 amb 307 {
1035 amb 406 if(way->props & PROPERTIES(i))
1036 amb 307 segment_pref*=profile->props_yes[i];
1037     else
1038     segment_pref*=profile->props_no[i];
1039     }
1040 amb 298
1041 amb 680 /* profile preferences must allow this highway */
1042 amb 298 if(segment_pref==0)
1043     goto endloop;
1044    
1045 amb 680 /* mode of transport must be allowed through node2 */
1046 amb 471 if(!IsFakeNode(node2))
1047     {
1048 amb 595 Node *node=LookupNode(nodes,node2,2);
1049 amb 469
1050 amb 471 if(!(node->allow&profile->allow))
1051     goto endloop;
1052     }
1053 amb 469
1054 amb 166 if(option_quickest==0)
1055 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
1056 amb 166 else
1057 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
1058 amb 59
1059 amb 170 cumulative_score=result1->score+segment_score;
1060 amb 166
1061 amb 605 result2=FindResult(results,node2,seg2);
1062 amb 34
1063 amb 680 if(!result2) /* New end node */
1064 amb 34 {
1065 amb 605 result2=InsertResult(results,node2,seg2);
1066     result2->next=result1; /* working backwards */
1067 amb 170 result2->score=cumulative_score;
1068 amb 34
1069 amb 609 if(IsFakeNode(node1) || (!IsFakeNode(node1) && !IsSuperNode(LookupNode(nodes,node1,1)))) /* Overshoot by one segment */
1070 amb 119 {
1071 amb 166 result2->sortby=result2->score;
1072 amb 236 InsertInQueue(queue,result2);
1073 amb 119 }
1074 amb 34 }
1075 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
1076 amb 34 {
1077 amb 605 result2->next=result1; /* working backwards */
1078 amb 170 result2->score=cumulative_score;
1079 amb 34
1080 amb 609 if(IsFakeNode(node1) || (!IsFakeNode(node1) && !IsSuperNode(LookupNode(nodes,node1,1)))) /* Overshoot by one segment */
1081 amb 34 {
1082 amb 166 result2->sortby=result2->score;
1083 amb 236 InsertInQueue(queue,result2);
1084 amb 34 }
1085     }
1086    
1087     endloop:
1088    
1089 amb 303 if(IsFakeNode(node1))
1090     segment=NextFakeSegment(segment,node1);
1091     else
1092     segment=NextSegment(segments,segment,node1);
1093 amb 34 }
1094     }
1095    
1096 amb 236 FreeQueueList(queue);
1097    
1098 amb 112 /* Check it worked */
1099    
1100     if(results->number==1)
1101     {
1102     FreeResultsList(results);
1103     return(NULL);
1104     }
1105    
1106 amb 605 /* Create a results structure with the node at the end of the segment opposite the start */
1107    
1108     results2=NewResultsList(8);
1109    
1110     results2->finish_node=results->finish_node;
1111    
1112     result3=FirstResult(results);
1113    
1114     while(result3)
1115     {
1116     if(result3->next)
1117     {
1118     result2=InsertResult(results2,result3->next->node,result3->segment);
1119    
1120 amb 616 result2->score=result3->next->score;
1121 amb 605 }
1122    
1123     result3=NextResult(results,result3);
1124     }
1125    
1126     /* Fix up the result->next pointers */
1127    
1128     result3=FirstResult(results);
1129    
1130     while(result3)
1131     {
1132     if(result3->next && result3->next->next)
1133     {
1134     result1=FindResult(results2,result3->next->node,result3->segment);
1135     result2=FindResult(results2,result3->next->next->node,result3->next->segment);
1136    
1137     result1->next=result2;
1138     }
1139    
1140     result3=NextResult(results,result3);
1141     }
1142    
1143     FreeResultsList(results);
1144    
1145     return(results2);
1146 amb 34 }
1147    
1148    
1149     /*++++++++++++++++++++++++++++++++++++++
1150 amb 95 Create an optimum route given the set of super-nodes to follow.
1151 amb 31
1152 amb 58 Results *CombineRoutes Returns the results from joining the super-nodes.
1153 amb 55
1154 amb 680 Nodes *nodes The set of nodes to use.
1155 amb 31
1156     Segments *segments The set of segments to use.
1157    
1158 amb 680 Ways *ways The set of ways to use.
1159 amb 31
1160 amb 542 Relations *relations The set of relations to use.
1161    
1162 amb 721 Profile *profile The profile containing the transport type, speeds and allowed highways.
1163    
1164 amb 722 Results *begin The set of results for the start of the route.
1165    
1166 amb 686 Results *middle The set of results from the super-node route.
1167 amb 31 ++++++++++++++++++++++++++++++++++++++*/
1168    
1169 amb 722 Results *CombineRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Profile *profile,Results *begin,Results *middle)
1170 amb 31 {
1171 amb 686 Result *midres,*comres1;
1172 amb 31 Results *combined;
1173    
1174 amb 71 combined=NewResultsList(64);
1175 amb 31
1176 amb 735 combined->start_node=begin->start_node;
1177     combined->prev_segment=begin->prev_segment;
1178 amb 165
1179 amb 722 /* Insert the start point */
1180 amb 31
1181 amb 686 midres=FindResult(middle,middle->start_node,middle->prev_segment);
1182 amb 31
1183 amb 735 comres1=InsertResult(combined,combined->start_node,combined->prev_segment);
1184 amb 31
1185 amb 722 /* Insert the start of the route */
1186    
1187     if(begin->number>1 && midres->next)
1188     {
1189     Result *begres;
1190    
1191     midres=FindResult(middle,midres->next->node,midres->next->segment);
1192    
1193     begres=FindResult(begin,midres->node,midres->segment);
1194    
1195     FixForwardRoute(begin,begres);
1196    
1197     if(midres->next && midres->next->node==midres->node)
1198     midres=midres->next;
1199    
1200     begres=FindResult(begin,begin->start_node,begin->prev_segment);
1201    
1202     begres=begres->next;
1203    
1204     do
1205     {
1206     Result *comres2;
1207    
1208     comres2=InsertResult(combined,begres->node,begres->segment);
1209    
1210     comres2->score=begres->score+comres1->score;
1211     comres2->prev=comres1;
1212    
1213     begres=begres->next;
1214    
1215     comres1=comres2;
1216     }
1217     while(begres);
1218     }
1219    
1220     /* Sort out the combined route */
1221    
1222 amb 58 do
1223     {
1224 amb 686 Result *result;
1225 amb 594
1226 amb 686 if(midres->next)
1227 amb 31 {
1228 amb 723 Results *results=FindNormalRoute(nodes,segments,ways,relations,profile,comres1->node,comres1->segment,midres->next->node);
1229 amb 31
1230 amb 686 if(!results)
1231 amb 677 return(NULL);
1232    
1233 amb 686 result=FindResult(results,midres->node,comres1->segment);
1234 amb 31
1235 amb 686 result=result->next;
1236 amb 36
1237 amb 605 /*
1238 amb 686 * midres midres->next
1239 amb 605 * = =
1240 amb 686 * ---*----------------------------------* = middle
1241 amb 605 *
1242 amb 686 * ---*----.----.----.----.----.----.----* = results
1243 amb 605 * =
1244 amb 686 * result
1245 amb 605 *
1246     * ---*----.----.----.----.----.----.----* = combined
1247     * = =
1248 amb 686 * comres1 comres2
1249 amb 605 */
1250    
1251 amb 31 do
1252     {
1253 amb 686 Result *comres2;
1254 amb 31
1255 amb 686 comres2=InsertResult(combined,result->node,result->segment);
1256 amb 605
1257 amb 686 comres2->score=result->score+comres1->score;
1258     comres2->prev=comres1;
1259 amb 605
1260 amb 686 result=result->next;
1261    
1262     comres1=comres2;
1263 amb 31 }
1264 amb 686 while(result);
1265 amb 31
1266 amb 686 FreeResultsList(results);
1267 amb 605 }
1268 amb 31
1269 amb 686 midres=midres->next;
1270 amb 31 }
1271 amb 686 while(midres);
1272 amb 31
1273 amb 686 FixForwardRoute(combined,comres1);
1274 amb 605
1275 amb 55 return(combined);
1276 amb 31 }
1277 amb 290
1278    
1279     /*++++++++++++++++++++++++++++++++++++++
1280 amb 605 Fix the forward route (i.e. setup next pointers for forward path from prev nodes on reverse path).
1281 amb 290
1282     Results *results The set of results to update.
1283    
1284 amb 680 Result *finish_result The result for the finish point.
1285 amb 290 ++++++++++++++++++++++++++++++++++++++*/
1286    
1287 amb 605 void FixForwardRoute(Results *results,Result *finish_result)
1288 amb 290 {
1289 amb 605 Result *result2=finish_result;
1290 amb 290
1291 amb 828 /* Erase the old route if there is one */
1292    
1293     if(results->finish_node!=NO_NODE)
1294     {
1295     Result *result1=FirstResult(results);
1296    
1297     while(result1)
1298     {
1299     result1->next=NULL;
1300    
1301     result1=NextResult(results,result1);
1302     }
1303     }
1304    
1305 amb 290 /* Create the forward links for the optimum path */
1306    
1307     do
1308     {
1309 amb 594 Result *result1;
1310    
1311 amb 605 if(result2->prev)
1312 amb 290 {
1313 amb 605 index_t node1=result2->prev->node;
1314     index_t seg1=result2->prev->segment;
1315 amb 290
1316 amb 605 result1=FindResult(results,node1,seg1);
1317 amb 290
1318 amb 712 assert(!result1->next); /* Bugs elsewhere can lead to infinite loop here. */
1319    
1320 amb 605 result1->next=result2;
1321 amb 290
1322     result2=result1;
1323     }
1324     else
1325     result2=NULL;
1326     }
1327     while(result2);
1328    
1329 amb 605 results->finish_node=finish_result->node;
1330     results->last_segment=finish_result->segment;
1331 amb 290 }

Properties

Name Value
cvs:description Route optimiser.