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

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