git.maemo.org Git - routino/blob - src/optimiser.c

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