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 531 - (hide annotations) (download) (as text)
Sat Nov 27 14:43:55 2010 UTC (14 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 24897 byte(s)
Move some of the complexity from router.c to optimiser.c.

1 amb 2 /***************************************
2 amb 531 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.95 2010-11-27 14:43:55 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 amb 531 /* Create the results and insert the start node */
545 amb 31
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 531 /* Take a shortcut if the first node is a super-node. */
555    
556     if(!IsFakeNode(start) && IsSuperNode(nodes,start))
557     return(results);
558    
559     /* Insert the first node into the queue */
560    
561 amb 236 queue=NewQueueList();
562 amb 31
563 amb 236 InsertInQueue(queue,result1);
564    
565 amb 31 /* Loop across all nodes in the queue */
566    
567 amb 236 while((result1=PopFromQueue(queue)))
568 amb 31 {
569 amb 43 node1=result1->node;
570 amb 31
571 amb 303 if(IsFakeNode(node1))
572     segment=FirstFakeSegment(node1);
573     else
574     segment=FirstSegment(segments,nodes,node1);
575 amb 31
576     while(segment)
577     {
578 amb 298 score_t segment_pref,segment_score,cumulative_score;
579     int i;
580 amb 59
581 amb 95 if(!IsNormalSegment(segment))
582     goto endloop;
583    
584 amb 105 if(profile->oneway && IsOnewayTo(segment,node1))
585 amb 64 goto endloop;
586    
587 amb 105 node2=OtherNode(segment,node1);
588 amb 31
589 amb 113 if(result1->prev==node2)
590 amb 64 goto endloop;
591    
592 amb 460 way=LookupWay(ways,segment->way,1);
593 amb 54
594 amb 82 if(!(way->allow&profile->allow))
595 amb 54 goto endloop;
596    
597 amb 168 if(!profile->highway[HIGHWAY(way->type)])
598 amb 75 goto endloop;
599    
600 amb 197 if(way->weight && way->weight<profile->weight)
601 amb 135 goto endloop;
602    
603 amb 197 if((way->height && way->height<profile->height) ||
604     (way->width && way->width <profile->width ) ||
605     (way->length && way->length<profile->length))
606 amb 135 goto endloop;
607    
608 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
609    
610     for(i=1;i<Property_Count;i++)
611 amb 460 if(ways->file.props & PROPERTIES(i))
612 amb 307 {
613 amb 406 if(way->props & PROPERTIES(i))
614 amb 307 segment_pref*=profile->props_yes[i];
615     else
616     segment_pref*=profile->props_no[i];
617     }
618 amb 298
619     if(segment_pref==0)
620     goto endloop;
621    
622 amb 471 if(!IsFakeNode(node2))
623     {
624     node=LookupNode(nodes,node2,1);
625 amb 469
626 amb 471 if(!(node->allow&profile->allow))
627     goto endloop;
628     }
629 amb 469
630 amb 166 if(option_quickest==0)
631 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
632 amb 166 else
633 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
634 amb 59
635 amb 170 cumulative_score=result1->score+segment_score;
636 amb 166
637 amb 31 result2=FindResult(results,node2);
638    
639     if(!result2) /* New end node */
640     {
641     result2=InsertResult(results,node2);
642 amb 113 result2->prev=node1;
643 amb 176 result2->next=NO_NODE;
644 amb 170 result2->score=cumulative_score;
645 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
646     result2->segment=IndexFakeSegment(segment);
647     else
648     result2->segment=IndexSegment(segments,segment);
649 amb 31
650 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
651 amb 119 {
652 amb 166 result2->sortby=result2->score;
653 amb 236 InsertInQueue(queue,result2);
654 amb 119 }
655 amb 31 }
656 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
657 amb 31 {
658 amb 166 result2->prev=node1;
659 amb 170 result2->score=cumulative_score;
660 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
661     result2->segment=IndexFakeSegment(segment);
662     else
663     result2->segment=IndexSegment(segments,segment);
664 amb 31
665 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
666 amb 31 {
667 amb 166 result2->sortby=result2->score;
668 amb 236 InsertInQueue(queue,result2);
669 amb 31 }
670     }
671    
672     endloop:
673    
674 amb 303 if(IsFakeNode(node1))
675     segment=NextFakeSegment(segment,node1);
676     else
677     segment=NextSegment(segments,segment,node1);
678 amb 31 }
679     }
680    
681 amb 236 FreeQueueList(queue);
682    
683 amb 112 /* Check it worked */
684    
685     if(results->number==1)
686     {
687     FreeResultsList(results);
688     return(NULL);
689     }
690    
691 amb 31 return(results);
692 amb 2 }
693    
694    
695     /*++++++++++++++++++++++++++++++++++++++
696 amb 95 Find all routes from any super-node to a specific node.
697 amb 34
698 amb 126 Results *FindFinishRoutes Returns a set of results.
699 amb 34
700     Nodes *nodes The set of nodes to use.
701    
702     Segments *segments The set of segments to use.
703    
704 amb 54 Ways *ways The set of ways to use.
705    
706 amb 96 index_t finish The finishing node.
707 amb 54
708 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
709 amb 34 ++++++++++++++++++++++++++++++++++++++*/
710    
711 amb 126 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,index_t finish,Profile *profile)
712 amb 34 {
713     Results *results;
714 amb 469 Queue *queue;
715 amb 96 index_t node1,node2;
716 amb 469 Result *result1,*result2;
717     Node *node;
718 amb 34 Segment *segment;
719 amb 469 Way *way;
720 amb 34
721 amb 531 /* Create the results and insert the finish node */
722 amb 34
723 amb 71 results=NewResultsList(8);
724 amb 34
725 amb 165 results->finish=finish;
726    
727 amb 34 result1=InsertResult(results,finish);
728    
729 amb 166 ZeroResult(result1);
730 amb 34
731 amb 531 /* Take a shortcut if the first node is a super-node. */
732    
733     if(!IsFakeNode(finish) && IsSuperNode(nodes,finish))
734     return(results);
735    
736     /* Insert the first node into the queue */
737    
738 amb 236 queue=NewQueueList();
739 amb 34
740 amb 236 InsertInQueue(queue,result1);
741    
742 amb 34 /* Loop across all nodes in the queue */
743    
744 amb 236 while((result1=PopFromQueue(queue)))
745 amb 34 {
746 amb 43 node1=result1->node;
747 amb 34
748 amb 303 if(IsFakeNode(node1))
749     segment=FirstFakeSegment(node1);
750     else
751     segment=FirstSegment(segments,nodes,node1);
752 amb 34
753     while(segment)
754     {
755 amb 298 score_t segment_pref,segment_score,cumulative_score;
756     int i;
757 amb 59
758 amb 104 if(!IsNormalSegment(segment))
759 amb 34 goto endloop;
760    
761 amb 105 if(profile->oneway && IsOnewayFrom(segment,node1))
762 amb 95 goto endloop;
763    
764 amb 105 node2=OtherNode(segment,node1);
765 amb 64
766 amb 113 if(result1->next==node2)
767 amb 64 goto endloop;
768    
769 amb 460 way=LookupWay(ways,segment->way,1);
770 amb 54
771 amb 82 if(!(way->allow&profile->allow))
772 amb 54 goto endloop;
773    
774 amb 168 if(!profile->highway[HIGHWAY(way->type)])
775 amb 75 goto endloop;
776    
777 amb 197 if(way->weight && way->weight<profile->weight)
778 amb 135 goto endloop;
779    
780 amb 197 if((way->height && way->height<profile->height) ||
781     (way->width && way->width <profile->width ) ||
782     (way->length && way->length<profile->length))
783 amb 135 goto endloop;
784    
785 amb 298 segment_pref=profile->highway[HIGHWAY(way->type)];
786    
787     for(i=1;i<Property_Count;i++)
788 amb 460 if(ways->file.props & PROPERTIES(i))
789 amb 307 {
790 amb 406 if(way->props & PROPERTIES(i))
791 amb 307 segment_pref*=profile->props_yes[i];
792     else
793     segment_pref*=profile->props_no[i];
794     }
795 amb 298
796     if(segment_pref==0)
797     goto endloop;
798    
799 amb 471 if(!IsFakeNode(node2))
800     {
801     node=LookupNode(nodes,node2,1);
802 amb 469
803 amb 471 if(!(node->allow&profile->allow))
804     goto endloop;
805     }
806 amb 469
807 amb 166 if(option_quickest==0)
808 amb 298 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
809 amb 166 else
810 amb 298 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
811 amb 59
812 amb 170 cumulative_score=result1->score+segment_score;
813 amb 166
814 amb 34 result2=FindResult(results,node2);
815    
816     if(!result2) /* New end node */
817     {
818     result2=InsertResult(results,node2);
819 amb 176 result2->prev=NO_NODE;
820 amb 113 result2->next=node1;
821 amb 170 result2->score=cumulative_score;
822 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
823     result2->segment=IndexFakeSegment(segment);
824     else
825     result2->segment=IndexSegment(segments,segment);
826 amb 34
827 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
828 amb 119 {
829 amb 166 result2->sortby=result2->score;
830 amb 236 InsertInQueue(queue,result2);
831 amb 119 }
832 amb 34 }
833 amb 166 else if(cumulative_score<result2->score) /* New end node is better */
834 amb 34 {
835 amb 166 result2->next=node1;
836 amb 170 result2->score=cumulative_score;
837 amb 457 if(IsFakeNode(node1) || IsFakeNode(node2))
838     result2->segment=IndexFakeSegment(segment);
839     else
840     result2->segment=IndexSegment(segments,segment);
841 amb 34
842 amb 303 if(!IsFakeNode(node2) && !IsSuperNode(nodes,node2))
843 amb 34 {
844 amb 166 result2->sortby=result2->score;
845 amb 236 InsertInQueue(queue,result2);
846 amb 34 }
847     }
848    
849     endloop:
850    
851 amb 303 if(IsFakeNode(node1))
852     segment=NextFakeSegment(segment,node1);
853     else
854     segment=NextSegment(segments,segment,node1);
855 amb 34 }
856     }
857    
858 amb 236 FreeQueueList(queue);
859    
860 amb 112 /* Check it worked */
861    
862     if(results->number==1)
863     {
864     FreeResultsList(results);
865     return(NULL);
866     }
867    
868 amb 34 return(results);
869     }
870    
871    
872     /*++++++++++++++++++++++++++++++++++++++
873 amb 95 Create an optimum route given the set of super-nodes to follow.
874 amb 31
875 amb 58 Results *CombineRoutes Returns the results from joining the super-nodes.
876 amb 55
877 amb 58 Results *results The set of results from the super-nodes.
878 amb 31
879     Nodes *nodes The list of nodes.
880    
881     Segments *segments The set of segments to use.
882    
883     Ways *ways The list of ways.
884    
885 amb 82 Profile *profile The profile containing the transport type, speeds and allowed highways.
886 amb 31 ++++++++++++++++++++++++++++++++++++++*/
887    
888 amb 165 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Profile *profile)
889 amb 31 {
890     Result *result1,*result2,*result3,*result4;
891     Results *combined;
892    
893 amb 71 combined=NewResultsList(64);
894 amb 31
895 amb 165 combined->start=results->start;
896     combined->finish=results->finish;
897    
898 amb 113 /* Sort out the combined route */
899 amb 31
900 amb 165 result1=FindResult(results,results->start);
901 amb 31
902 amb 165 result3=InsertResult(combined,results->start);
903 amb 31
904 amb 166 ZeroResult(result3);
905 amb 36
906 amb 58 do
907     {
908 amb 176 if(result1->next!=NO_NODE)
909 amb 31 {
910 amb 238 Results *results2=FindNormalRoute(nodes,segments,ways,result1->node,result1->next,profile);
911 amb 31
912     result2=FindResult(results2,result1->node);
913    
914 amb 113 result3->next=result2->next;
915 amb 36
916 amb 113 result2=FindResult(results2,result2->next);
917 amb 36
918 amb 31 do
919     {
920 amb 58 result4=InsertResult(combined,result2->node);
921 amb 31
922 amb 113 *result4=*result2;
923 amb 170 result4->score+=result3->score;
924 amb 31
925 amb 176 if(result2->next!=NO_NODE)
926 amb 113 result2=FindResult(results2,result2->next);
927 amb 31 else
928     result2=NULL;
929     }
930     while(result2);
931    
932     FreeResultsList(results2);
933    
934 amb 113 result1=FindResult(results,result1->next);
935 amb 58
936     result3=result4;
937 amb 31 }
938     else
939     result1=NULL;
940     }
941     while(result1);
942    
943 amb 55 return(combined);
944 amb 31 }
945 amb 290
946    
947     /*++++++++++++++++++++++++++++++++++++++
948     Fx the forward route (i.e. setup next nodes for forward path from prev nodes on reverse path).
949    
950     Results *results The set of results to update.
951    
952     index_t finish The finish point.
953     ++++++++++++++++++++++++++++++++++++++*/
954    
955     void FixForwardRoute(Results *results,index_t finish)
956     {
957     Result *result2=FindResult(results,finish);
958     Result *result1;
959    
960     /* Create the forward links for the optimum path */
961    
962     do
963     {
964     if(result2->prev!=NO_NODE)
965     {
966     index_t node1=result2->prev;
967    
968     result1=FindResult(results,node1);
969    
970     result1->next=result2->node;
971    
972     result2=result1;
973     }
974     else
975     result2=NULL;
976     }
977     while(result2);
978    
979     results->finish=finish;
980     }

Properties

Name Value
cvs:description Route optimiser.