Routino SVN Repository Browser

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

ViewVC logotype

Annotation of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 519 - (hide annotations) (download) (as text)
Sat Nov 13 14:22:28 2010 UTC (14 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 24522 byte(s)
Add an option to make the output more suitable for a log file.

1 amb 2 /***************************************
2 amb 519 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.94 2010-11-13 14:22:28 amb Exp $
3 amb 2
4     Routing optimiser.
5 amb 151
6     Part of the Routino routing software.
7 amb 2 ******************/ /******************
8 amb 412 This file Copyright 2008-2010 Andrew M. Bishop
9 amb 2
10 amb 151 This program is free software: you can redistribute it and/or modify
11     it under the terms of the GNU Affero General Public License as published by
12     the Free Software Foundation, either version 3 of the License, or
13     (at your option) any later version.
14    
15     This program is distributed in the hope that it will be useful,
16     but WITHOUT ANY WARRANTY; without even the implied warranty of
17     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18     GNU Affero General Public License for more details.
19    
20     You should have received a copy of the GNU Affero General Public License
21     along with this program. If not, see <http://www.gnu.org/licenses/>.
22 amb 2 ***************************************/
23    
24    
25 amb 109 #include <stdio.h>
26 amb 2
27 amb 96 #include "types.h"
28 amb 109 #include "nodes.h"
29     #include "segments.h"
30     #include "ways.h"
31 amb 449
32 amb 519 #include "logging.h"
33 amb 449 #include "functions.h"
34 amb 28 #include "results.h"
35 amb 2
36 amb 26
37 amb 113 /*+ The option not to print any progress information. +*/
38 amb 107 extern int option_quiet;
39 amb 2
40 amb 113 /*+ The option to calculate the quickest route insted of the shortest. +*/
41     extern int option_quickest;
42 amb 31
43 amb 113
44 amb 2 /*++++++++++++++++++++++++++++++++++++++
45 amb 238 Find the optimum route between two nodes not passing through a super-node.
46 amb 2
47 amb 238 Results *FindNormalRoute Returns a set of results.
48 amb 26
49     Nodes *nodes The set of nodes to use.
50    
51     Segments *segments The set of segments to use.
52    
53 amb 54 Ways *ways The set of ways to use.
54    
55 amb 96 index_t start The start node.
56 amb 2
57 amb 96 index_t finish The finish node.
58 amb 54
59 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
60 amb 2 ++++++++++++++++++++++++++++++++++++++*/
61    
62 amb 238 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,index_t start,index_t finish,Profile *profile)
63 amb 2 {
64 amb 31 Results *results;
65 amb 469 Queue *queue;
66 amb 96 index_t node1,node2;
67 amb 166 score_t finish_score;
68 amb 219 double finish_lat,finish_lon;
69 amb 469 Result *result1,*result2;
70     Node *node;
71 amb 2 Segment *segment;
72 amb 469 Way *way;
73 amb 2
74 amb 10 /* Set up the finish conditions */
75    
76 amb 176 finish_score=INF_SCORE;
77 amb 10
78 amb 303 if(IsFakeNode(finish))
79     GetFakeLatLong(finish,&finish_lat,&finish_lon);
80     else
81     GetLatLong(nodes,finish,&finish_lat,&finish_lon);
82 amb 119
83 amb 165 /* Create the list of results and insert the first node into the queue */
84 amb 2
85 amb 238 results=NewResultsList(8);
86 amb 2
87 amb 165 results->start=start;
88     results->finish=finish;
89    
90 amb 31 result1=InsertResult(results,start);
91 amb 28
92 amb 166 ZeroResult(result1);
93 amb 2
94 amb 236 queue=NewQueueList();
95 amb 2
96 amb 236 InsertInQueue(queue,result1);
97    
98 amb 2 /* Loop across all nodes in the queue */
99    
100 amb 236 while((result1=PopFromQueue(queue)))
101 amb 2 {
102 amb 238 if(result1->score>finish_score)
103 amb 119 continue;
104    
105 amb 43 node1=result1->node;
106 amb 2
107 amb 303 if(IsFakeNode(node1))
108     segment=FirstFakeSegment(node1);
109     else
110     segment=FirstSegment(segments,nodes,node1);
111 amb 2
112     while(segment)
113     {
114 amb 298 score_t segment_pref,segment_score,cumulative_score;
115     int i;
116 amb 59
117 amb 303 node2=OtherNode(segment,node1); /* need this here because we use node2 later */
118    
119 amb 95 if(!IsNormalSegment(segment))
120 amb 90 goto endloop;
121    
122 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
123 amb 64 goto endloop;
124    
125 amb 113 if(result1->prev==node2)
126 amb 64 goto endloop;
127    
128 amb 303 if(node2!=finish && !IsFakeNode(node2) && IsSuperNode(nodes,node2))
129 amb 238 goto endloop;
130    
131 amb 460 way=LookupWay(ways,segment->way,1);
132 amb 54
133 amb 82 if(!(way->allow&profile->allow))
134 amb 54 goto endloop;
135    
136 amb 168 if(!profile->highway[HIGHWAY(way->type)])
137 amb 75 goto endloop;
138    
139 amb 197 if(way->weight && way->weight<profile->weight)
140 amb 135 goto endloop;
141    
142 amb 197 if((way->height && way->height<profile->height) ||
143     (way->width && way->width <profile->width ) ||
144     (way->length && way->length<profile->length))
145 amb 135 goto endloop;
146    
147 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
148    
149     for(i=1;i<Property_Count;i++)
150 amb 460 if(ways->file.props & PROPERTIES(i))
151 amb 307 {
152 amb 406 if(way->props & PROPERTIES(i))
153 amb 307 segment_pref*=profile->props_yes[i];
154     else
155     segment_pref*=profile->props_no[i];
156     }
157 amb 298
158     if(segment_pref==0)
159     goto endloop;
160    
161 amb 471 if(!IsFakeNode(node2))
162     {
163     node=LookupNode(nodes,node2,1);
164 amb 469
165 amb 471 if(!(node->allow&profile->allow))
166     goto endloop;
167     }
168 amb 469
169 amb 166 if(option_quickest==0)
170 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
171 amb 166 else
172 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
173 amb 59
174 amb 170 cumulative_score=result1->score+segment_score;
175 amb 166
176     if(cumulative_score>finish_score)
177 amb 2 goto endloop;
178    
179 amb 42 result2=FindResult(results,node2);
180    
181 amb 2 if(!result2) /* New end node */
182     {
183 amb 31 result2=InsertResult(results,node2);
184 amb 113 result2->prev=node1;
185 amb 176 result2->next=NO_NODE;
186 amb 170 result2->score=cumulative_score;
187 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
188     result2->segment=IndexFakeSegment(segment);
189     else
190     result2->segment=IndexSegment(segments,segment);
191 amb 2
192     if(node2==finish)
193     {
194 amb 170 finish_score=cumulative_score;
195 amb 2 }
196     else
197 amb 119 {
198 amb 238 result2->sortby=result2->score;
199 amb 166
200 amb 236 InsertInQueue(queue,result2);
201 amb 119 }
202 amb 2 }
203 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
204 amb 2 {
205 amb 166 result2->prev=node1;
206 amb 170 result2->score=cumulative_score;
207 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
208     result2->segment=IndexFakeSegment(segment);
209     else
210     result2->segment=IndexSegment(segments,segment);
211 amb 166
212     if(node2==finish)
213 amb 2 {
214 amb 166 finish_score=cumulative_score;
215 amb 2 }
216 amb 166 else
217     {
218 amb 238 result2->sortby=result2->score;
219 amb 2
220 amb 238 if(result2->score<finish_score)
221 amb 236 InsertInQueue(queue,result2);
222 amb 2 }
223     }
224    
225     endloop:
226    
227 amb 303 if(IsFakeNode(node1))
228     segment=NextFakeSegment(segment,node1);
229     else if(IsFakeNode(node2))
230     segment=NULL; /* cannot call NextSegment() with a fake segment */
231     else
232     {
233     segment=NextSegment(segments,segment,node1);
234    
235     if(!segment && IsFakeNode(finish))
236     segment=ExtraFakeSegment(node1,finish);
237     }
238 amb 2 }
239     }
240    
241 amb 236 FreeQueueList(queue);
242    
243 amb 77 /* Check it worked */
244    
245 amb 290 if(!FindResult(results,finish))
246 amb 77 {
247     FreeResultsList(results);
248     return(NULL);
249     }
250    
251 amb 290 FixForwardRoute(results,finish);
252 amb 31
253     return(results);
254 amb 2 }
255    
256    
257     /*++++++++++++++++++++++++++++++++++++++
258 amb 238 Find the optimum route between two nodes where the start and end are a set of pre-routed super-nodes.
259 amb 34
260 amb 238 Results *FindMiddleRoute Returns a set of results.
261 amb 34
262 amb 95 Nodes *nodes The set of nodes to use.
263 amb 34
264 amb 95 Segments *segments The set of segments to use.
265 amb 34
266 amb 95 Ways *ways The set of ways to use.
267 amb 54
268 amb 34 Results *begin The initial portion of the route.
269    
270     Results *end The final portion of the route.
271 amb 54
272 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
273 amb 34 ++++++++++++++++++++++++++++++++++++++*/
274    
275 amb 238 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Results *begin,Results *end,Profile *profile)
276 amb 34 {
277     Results *results;
278 amb 469 Queue *queue;
279 amb 96 index_t node1,node2;
280 amb 435 index_t end_prev;
281 amb 166 score_t finish_score;
282 amb 219 double finish_lat,finish_lon;
283 amb 469 Result *result1,*result2,*result3;
284     Node *node;
285 amb 34 Segment *segment;
286 amb 469 Way *way;
287 amb 34
288 amb 227 if(!option_quiet)
289 amb 519 printf_first("Routing: Super-Nodes checked = 0");
290 amb 227
291 amb 34 /* Set up the finish conditions */
292    
293 amb 302 finish_score=INF_DISTANCE;
294 amb 435 end_prev=NO_NODE;
295 amb 34
296 amb 303 if(IsFakeNode(end->finish))
297     GetFakeLatLong(end->finish,&finish_lat,&finish_lon);
298     else
299     GetLatLong(nodes,end->finish,&finish_lat,&finish_lon);
300 amb 119
301 amb 165 /* Create the list of results and insert the first node into the queue */
302 amb 34
303 amb 441 results=NewResultsList(2048);
304 amb 34
305 amb 165 results->start=begin->start;
306     results->finish=end->finish;
307 amb 34
308 amb 165 result1=InsertResult(results,begin->start);
309     result3=FindResult(begin,begin->start);
310    
311 amb 81 *result1=*result3;
312 amb 34
313 amb 236 queue=NewQueueList();
314    
315 amb 34 /* Insert the finish points of the beginning part of the path into the queue */
316    
317 amb 79 result3=FirstResult(begin);
318    
319     while(result3)
320     {
321 amb 303 if(result3->node!=begin->start && !IsFakeNode(result3->node) && IsSuperNode(nodes,result3->node))
322 amb 45 {
323 amb 238 result2=InsertResult(results,result3->node);
324 amb 34
325 amb 238 *result2=*result3;
326 amb 34
327 amb 238 result2->prev=begin->start;
328 amb 119
329 amb 238 result2->sortby=result2->score;
330 amb 34
331 amb 236 InsertInQueue(queue,result2);
332 amb 45 }
333 amb 34
334 amb 79 result3=NextResult(begin,result3);
335     }
336    
337 amb 238 if(begin->number==1)
338     InsertInQueue(queue,result1);
339    
340 amb 95 /* Loop across all nodes in the queue */
341 amb 34
342 amb 236 while((result1=PopFromQueue(queue)))
343 amb 34 {
344 amb 238 if(result1->score>finish_score)
345 amb 119 continue;
346    
347 amb 43 node1=result1->node;
348 amb 34
349 amb 435 segment=FirstSegment(segments,nodes,node1);
350 amb 34
351     while(segment)
352     {
353 amb 298 score_t segment_pref,segment_score,cumulative_score;
354     int i;
355 amb 59
356 amb 95 if(!IsSuperSegment(segment))
357     goto endloop;
358    
359 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
360 amb 64 goto endloop;
361    
362 amb 105 node2=OtherNode(segment,node1);
363 amb 34
364 amb 113 if(result1->prev==node2)
365 amb 64 goto endloop;
366    
367 amb 460 way=LookupWay(ways,segment->way,1);
368 amb 54
369 amb 82 if(!(way->allow&profile->allow))
370 amb 54 goto endloop;
371    
372 amb 168 if(!profile->highway[HIGHWAY(way->type)])
373 amb 75 goto endloop;
374    
375 amb 197 if(way->weight && way->weight<profile->weight)
376 amb 135 goto endloop;
377    
378 amb 197 if((way->height && way->height<profile->height) ||
379     (way->width && way->width <profile->width ) ||
380     (way->length && way->length<profile->length))
381 amb 135 goto endloop;
382    
383 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
384    
385     for(i=1;i<Property_Count;i++)
386 amb 460 if(ways->file.props & PROPERTIES(i))
387 amb 307 {
388 amb 406 if(way->props & PROPERTIES(i))
389 amb 307 segment_pref*=profile->props_yes[i];
390     else
391     segment_pref*=profile->props_no[i];
392     }
393 amb 298
394     if(segment_pref==0)
395     goto endloop;
396    
397 amb 469 node=LookupNode(nodes,node2,1);
398    
399 amb 470 if(!(node->allow&profile->allow))
400 amb 469 goto endloop;
401    
402 amb 166 if(option_quickest==0)
403 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
404 amb 166 else
405 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
406 amb 34
407 amb 170 cumulative_score=result1->score+segment_score;
408 amb 166
409     if(cumulative_score>finish_score)
410 amb 34 goto endloop;
411    
412 amb 42 result2=FindResult(results,node2);
413    
414 amb 34 if(!result2) /* New end node */
415     {
416     result2=InsertResult(results,node2);
417 amb 113 result2->prev=node1;
418 amb 176 result2->next=NO_NODE;
419 amb 170 result2->score=cumulative_score;
420 amb 457 result2->segment=IndexSegment(segments,segment);
421 amb 34
422 amb 113 if((result3=FindResult(end,node2)))
423     {
424 amb 442 if((result2->score+result3->score)<finish_score)
425     {
426     finish_score=result2->score+result3->score;
427     end_prev=node2;
428     }
429 amb 113 }
430     else
431 amb 119 {
432 amb 219 double lat,lon;
433 amb 166 distance_t direct;
434    
435 amb 435 GetLatLong(nodes,node2,&lat,&lon);
436 amb 166 direct=Distance(lat,lon,finish_lat,finish_lon);
437 amb 119
438     if(option_quickest==0)
439 amb 173 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
440 amb 119 else
441 amb 173 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
442 amb 119
443 amb 236 InsertInQueue(queue,result2);
444 amb 119 }
445 amb 34 }
446 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
447 amb 34 {
448 amb 166 result2->prev=node1;
449 amb 170 result2->score=cumulative_score;
450 amb 457 result2->segment=IndexSegment(segments,segment);
451 amb 166
452     if((result3=FindResult(end,node2)))
453 amb 34 {
454 amb 166 if((result2->score+result3->score)<finish_score)
455 amb 113 {
456 amb 166 finish_score=result2->score+result3->score;
457 amb 435 end_prev=node2;
458 amb 113 }
459 amb 34 }
460 amb 238 else if(result2->score<finish_score)
461 amb 34 {
462 amb 219 double lat,lon;
463 amb 166 distance_t direct;
464 amb 34
465 amb 435 GetLatLong(nodes,node2,&lat,&lon);
466 amb 166 direct=Distance(lat,lon,finish_lat,finish_lon);
467    
468     if(option_quickest==0)
469 amb 173 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
470 amb 113 else
471 amb 173 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
472 amb 119
473 amb 238 InsertInQueue(queue,result2);
474 amb 34 }
475     }
476    
477     endloop:
478    
479 amb 107 if(!option_quiet && !(results->number%10000))
480 amb 519 printf_middle("Routing: Super-Nodes checked = %d",results->number);
481 amb 34
482 amb 435 segment=NextSegment(segments,segment,node1);
483 amb 34 }
484     }
485    
486 amb 107 if(!option_quiet)
487 amb 519 printf_last("Routing: Super-Nodes checked = %d",results->number);
488 amb 34
489     /* Finish off the end part of the route. */
490    
491 amb 435 if(!FindResult(results,end->finish) && end_prev!=NO_NODE)
492 amb 47 {
493 amb 165 result2=InsertResult(results,end->finish);
494     result3=FindResult(end,end->finish);
495 amb 34
496 amb 81 *result2=*result3;
497 amb 47
498 amb 435 result2->prev=end_prev;
499     result2->score=finish_score;
500 amb 47 }
501 amb 34
502 amb 236 FreeQueueList(queue);
503    
504 amb 77 /* Check it worked */
505    
506 amb 435 if(end_prev==NO_NODE)
507 amb 77 {
508     FreeResultsList(results);
509     return(NULL);
510     }
511    
512 amb 290 FixForwardRoute(results,end->finish);
513 amb 34
514     return(results);
515     }
516    
517    
518     /*++++++++++++++++++++++++++++++++++++++
519 amb 95 Find all routes from a specified node to any super-node.
520 amb 3
521 amb 126 Results *FindStartRoutes Returns a set of results.
522 amb 31
523     Nodes *nodes The set of nodes to use.
524    
525     Segments *segments The set of segments to use.
526    
527 amb 54 Ways *ways The set of ways to use.
528    
529 amb 96 index_t start The start node.
530 amb 31
531 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
532 amb 31 ++++++++++++++++++++++++++++++++++++++*/
533    
534 amb 126 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t start,Profile *profile)
535 amb 31 {
536     Results *results;
537 amb 469 Queue *queue;
538 amb 96 index_t node1,node2;
539 amb 469 Result *result1,*result2;
540     Node *node;
541 amb 31 Segment *segment;
542 amb 469 Way *way;
543 amb 31
544     /* Insert the first node into the queue */
545    
546 amb 71 results=NewResultsList(8);
547 amb 31
548 amb 165 results->start=start;
549    
550 amb 31 result1=InsertResult(results,start);
551    
552 amb 166 ZeroResult(result1);
553 amb 31
554 amb 236 queue=NewQueueList();
555 amb 31
556 amb 236 InsertInQueue(queue,result1);
557    
558 amb 31 /* Loop across all nodes in the queue */
559    
560 amb 236 while((result1=PopFromQueue(queue)))
561 amb 31 {
562 amb 43 node1=result1->node;
563 amb 31
564 amb 303 if(IsFakeNode(node1))
565     segment=FirstFakeSegment(node1);
566     else
567     segment=FirstSegment(segments,nodes,node1);
568 amb 31
569     while(segment)
570     {
571 amb 298 score_t segment_pref,segment_score,cumulative_score;
572     int i;
573 amb 59
574 amb 95 if(!IsNormalSegment(segment))
575     goto endloop;
576    
577 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
578 amb 64 goto endloop;
579    
580 amb 105 node2=OtherNode(segment,node1);
581 amb 31
582 amb 113 if(result1->prev==node2)
583 amb 64 goto endloop;
584    
585 amb 460 way=LookupWay(ways,segment->way,1);
586 amb 54
587 amb 82 if(!(way->allow&profile->allow))
588 amb 54 goto endloop;
589    
590 amb 168 if(!profile->highway[HIGHWAY(way->type)])
591 amb 75 goto endloop;
592    
593 amb 197 if(way->weight && way->weight<profile->weight)
594 amb 135 goto endloop;
595    
596 amb 197 if((way->height && way->height<profile->height) ||
597     (way->width && way->width <profile->width ) ||
598     (way->length && way->length<profile->length))
599 amb 135 goto endloop;
600    
601 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
602    
603     for(i=1;i<Property_Count;i++)
604 amb 460 if(ways->file.props & PROPERTIES(i))
605 amb 307 {
606 amb 406 if(way->props & PROPERTIES(i))
607 amb 307 segment_pref*=profile->props_yes[i];
608     else
609     segment_pref*=profile->props_no[i];
610     }
611 amb 298
612     if(segment_pref==0)
613     goto endloop;
614    
615 amb 471 if(!IsFakeNode(node2))
616     {
617     node=LookupNode(nodes,node2,1);
618 amb 469
619 amb 471 if(!(node->allow&profile->allow))
620     goto endloop;
621     }
622 amb 469
623 amb 166 if(option_quickest==0)
624 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
625 amb 166 else
626 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
627 amb 59
628 amb 170 cumulative_score=result1->score+segment_score;
629 amb 166
630 amb 31 result2=FindResult(results,node2);
631    
632     if(!result2) /* New end node */
633     {
634     result2=InsertResult(results,node2);
635 amb 113 result2->prev=node1;
636 amb 176 result2->next=NO_NODE;
637 amb 170 result2->score=cumulative_score;
638 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
639     result2->segment=IndexFakeSegment(segment);
640     else
641     result2->segment=IndexSegment(segments,segment);
642 amb 31
643 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
644 amb 119 {
645 amb 166 result2->sortby=result2->score;
646 amb 236 InsertInQueue(queue,result2);
647 amb 119 }
648 amb 31 }
649 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
650 amb 31 {
651 amb 166 result2->prev=node1;
652 amb 170 result2->score=cumulative_score;
653 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
654     result2->segment=IndexFakeSegment(segment);
655     else
656     result2->segment=IndexSegment(segments,segment);
657 amb 31
658 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
659 amb 31 {
660 amb 166 result2->sortby=result2->score;
661 amb 236 InsertInQueue(queue,result2);
662 amb 31 }
663     }
664    
665     endloop:
666    
667 amb 303 if(IsFakeNode(node1))
668     segment=NextFakeSegment(segment,node1);
669     else
670     segment=NextSegment(segments,segment,node1);
671 amb 31 }
672     }
673    
674 amb 236 FreeQueueList(queue);
675    
676 amb 112 /* Check it worked */
677    
678     if(results->number==1)
679     {
680     FreeResultsList(results);
681     return(NULL);
682     }
683    
684 amb 31 return(results);
685 amb 2 }
686    
687    
688     /*++++++++++++++++++++++++++++++++++++++
689 amb 95 Find all routes from any super-node to a specific node.
690 amb 34
691 amb 126 Results *FindFinishRoutes Returns a set of results.
692 amb 34
693     Nodes *nodes The set of nodes to use.
694    
695     Segments *segments The set of segments to use.
696    
697 amb 54 Ways *ways The set of ways to use.
698    
699 amb 96 index_t finish The finishing node.
700 amb 54
701 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
702 amb 34 ++++++++++++++++++++++++++++++++++++++*/
703    
704 amb 126 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
705 amb 34 {
706     Results *results;
707 amb 469 Queue *queue;
708 amb 96 index_t node1,node2;
709 amb 469 Result *result1,*result2;
710     Node *node;
711 amb 34 Segment *segment;
712 amb 469 Way *way;
713 amb 34
714     /* Insert the first node into the queue */
715    
716 amb 71 results=NewResultsList(8);
717 amb 34
718 amb 165 results->finish=finish;
719    
720 amb 34 result1=InsertResult(results,finish);
721    
722 amb 166 ZeroResult(result1);
723 amb 34
724 amb 236 queue=NewQueueList();
725 amb 34
726 amb 236 InsertInQueue(queue,result1);
727    
728 amb 34 /* Loop across all nodes in the queue */
729    
730 amb 236 while((result1=PopFromQueue(queue)))
731 amb 34 {
732 amb 43 node1=result1->node;
733 amb 34
734 amb 303 if(IsFakeNode(node1))
735     segment=FirstFakeSegment(node1);
736     else
737     segment=FirstSegment(segments,nodes,node1);
738 amb 34
739     while(segment)
740     {
741 amb 298 score_t segment_pref,segment_score,cumulative_score;
742     int i;
743 amb 59
744 amb 104 if(!IsNormalSegment(segment))
745 amb 34 goto endloop;
746    
747 amb 105 if(profile->oneway && IsOnewayFrom(segment,node1))
748 amb 95 goto endloop;
749    
750 amb 105 node2=OtherNode(segment,node1);
751 amb 64
752 amb 113 if(result1->next==node2)
753 amb 64 goto endloop;
754    
755 amb 460 way=LookupWay(ways,segment->way,1);
756 amb 54
757 amb 82 if(!(way->allow&profile->allow))
758 amb 54 goto endloop;
759    
760 amb 168 if(!profile->highway[HIGHWAY(way->type)])
761 amb 75 goto endloop;
762    
763 amb 197 if(way->weight && way->weight<profile->weight)
764 amb 135 goto endloop;
765    
766 amb 197 if((way->height && way->height<profile->height) ||
767     (way->width && way->width <profile->width ) ||
768     (way->length && way->length<profile->length))
769 amb 135 goto endloop;
770    
771 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
772    
773     for(i=1;i<Property_Count;i++)
774 amb 460 if(ways->file.props & PROPERTIES(i))
775 amb 307 {
776 amb 406 if(way->props & PROPERTIES(i))
777 amb 307 segment_pref*=profile->props_yes[i];
778     else
779     segment_pref*=profile->props_no[i];
780     }
781 amb 298
782     if(segment_pref==0)
783     goto endloop;
784    
785 amb 471 if(!IsFakeNode(node2))
786     {
787     node=LookupNode(nodes,node2,1);
788 amb 469
789 amb 471 if(!(node->allow&profile->allow))
790     goto endloop;
791     }
792 amb 469
793 amb 166 if(option_quickest==0)
794 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
795 amb 166 else
796 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
797 amb 59
798 amb 170 cumulative_score=result1->score+segment_score;
799 amb 166
800 amb 34 result2=FindResult(results,node2);
801    
802     if(!result2) /* New end node */
803     {
804     result2=InsertResult(results,node2);
805 amb 176 result2->prev=NO_NODE;
806 amb 113 result2->next=node1;
807 amb 170 result2->score=cumulative_score;
808 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
809     result2->segment=IndexFakeSegment(segment);
810     else
811     result2->segment=IndexSegment(segments,segment);
812 amb 34
813 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
814 amb 119 {
815 amb 166 result2->sortby=result2->score;
816 amb 236 InsertInQueue(queue,result2);
817 amb 119 }
818 amb 34 }
819 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
820 amb 34 {
821 amb 166 result2->next=node1;
822 amb 170 result2->score=cumulative_score;
823 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
824     result2->segment=IndexFakeSegment(segment);
825     else
826     result2->segment=IndexSegment(segments,segment);
827 amb 34
828 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
829 amb 34 {
830 amb 166 result2->sortby=result2->score;
831 amb 236 InsertInQueue(queue,result2);
832 amb 34 }
833     }
834    
835     endloop:
836    
837 amb 303 if(IsFakeNode(node1))
838     segment=NextFakeSegment(segment,node1);
839     else
840     segment=NextSegment(segments,segment,node1);
841 amb 34 }
842     }
843    
844 amb 236 FreeQueueList(queue);
845    
846 amb 112 /* Check it worked */
847    
848     if(results->number==1)
849     {
850     FreeResultsList(results);
851     return(NULL);
852     }
853    
854 amb 34 return(results);
855     }
856    
857    
858     /*++++++++++++++++++++++++++++++++++++++
859 amb 95 Create an optimum route given the set of super-nodes to follow.
860 amb 31
861 amb 58 Results *CombineRoutes Returns the results from joining the super-nodes.
862 amb 55
863 amb 58 Results *results The set of results from the super-nodes.
864 amb 31
865     Nodes *nodes The list of nodes.
866    
867     Segments *segments The set of segments to use.
868    
869     Ways *ways The list of ways.
870    
871 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
872 amb 31 ++++++++++++++++++++++++++++++++++++++*/
873    
874 amb 165 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
875 amb 31 {
876     Result *result1,*result2,*result3,*result4;
877     Results *combined;
878    
879 amb 71 combined=NewResultsList(64);
880 amb 31
881 amb 165 combined->start=results->start;
882     combined->finish=results->finish;
883    
884 amb 113 /* Sort out the combined route */
885 amb 31
886 amb 165 result1=FindResult(results,results->start);
887 amb 31
888 amb 165 result3=InsertResult(combined,results->start);
889 amb 31
890 amb 166 ZeroResult(result3);
891 amb 36
892 amb 58 do
893     {
894 amb 176 if(result1->next!=NO_NODE)
895 amb 31 {
896 amb 238 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
897 amb 31
898     result2=FindResult(results2,result1->node);
899    
900 amb 113 result3->next=result2->next;
901 amb 36
902 amb 113 result2=FindResult(results2,result2->next);
903 amb 36
904 amb 31 do
905     {
906 amb 58 result4=InsertResult(combined,result2->node);
907 amb 31
908 amb 113 *result4=*result2;
909 amb 170 result4->score+=result3->score;
910 amb 31
911 amb 176 if(result2->next!=NO_NODE)
912 amb 113 result2=FindResult(results2,result2->next);
913 amb 31 else
914     result2=NULL;
915     }
916     while(result2);
917    
918     FreeResultsList(results2);
919    
920 amb 113 result1=FindResult(results,result1->next);
921 amb 58
922     result3=result4;
923 amb 31 }
924     else
925     result1=NULL;
926     }
927     while(result1);
928    
929 amb 55 return(combined);
930 amb 31 }
931 amb 290
932    
933     /*++++++++++++++++++++++++++++++++++++++
934     Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
935    
936     Results *results The set of results to update.
937    
938     index_t finish The finish point.
939     ++++++++++++++++++++++++++++++++++++++*/
940    
941     void FixForwardRoute(Results *results,index_t finish)
942     {
943     Result *result2=FindResult(results,finish);
944     Result *result1;
945    
946     /* Create the forward links for the optimum path */
947    
948     do
949     {
950     if(result2->prev!=NO_NODE)
951     {
952     index_t node1=result2->prev;
953    
954     result1=FindResult(results,node1);
955    
956     result1->next=result2->node;
957    
958     result2=result1;
959     }
960     else
961     result2=NULL;
962     }
963     while(result2);
964    
965     results->finish=finish;
966     }

Properties

Name Value
cvs:description Route optimiser.