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

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