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

Properties

Name Value
cvs:description Route optimiser.