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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/superx.c,v 1.38 2010/07/05 19:05:51 amb Exp $
   3
   4  Super-Segment data type functions.
   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 <assert.h>
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28
  29 #include "results.h"
  30 #include "functions.h"
  31 #include "nodesx.h"
  32 #include "segmentsx.h"
  33 #include "waysx.h"
  34 #include "superx.h"
  35 #include "ways.h"
  36
  37
  38 /* Variables */
  39
  40 /*+ The command line '--slim' option. +*/
  41 extern int option_slim;
  42
  43 /* Local Functions */
  44
  45 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);
  46
  47
  48 /*++++++++++++++++++++++++++++++++++++++
  49   Select the super-segments from the list of segments.
  50
  51   NodesX *nodesx The nodes.
  52
  53   SegmentsX *segmentsx The segments.
  54
  55   WaysX *waysx The ways.
  56   ++++++++++++++++++++++++++++++++++++++*/
  57
  58 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
  59 {
  60  index_t i;
  61  int nnodes=0;
  62
  63  /* Check the start conditions */
  64
  65  assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
  66
  67  /* Print the start message */
  68
  69  printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
  70  fflush(stdout);
  71
  72  /* Map into memory */
  73
  74  if(!option_slim)
  75    {
  76     segmentsx->xdata=MapFile(segmentsx->filename);
  77     waysx->xdata=MapFile(waysx->filename);
  78    }
  79
  80  /* Find super-nodes */
  81
  82  for(i=0;i<nodesx->number;i++)
  83    {
  84     int difference=0;
  85     index_t index1,index2;
  86
  87     index1=IndexFirstSegmentX(segmentsx,i);
  88
  89     while(index1!=NO_SEGMENT)
  90       {
  91        SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
  92        WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
  93
  94        index1=IndexNextSegmentX(segmentsx,index1,i);
  95        index2=index1;
  96
  97        while(index2!=NO_SEGMENT)
  98          {
  99           SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
 100           WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
 101
 102           /* If the ways are different in any way and there is a type of traffic that can use both ... */
 103
 104           if(WaysCompare(&wayx1->way,&wayx2->way))
 105              if(wayx1->way.allow & wayx2->way.allow)
 106                {
 107                 difference=1;
 108                 break;
 109                }
 110
 111           index2=IndexNextSegmentX(segmentsx,index2,i);
 112          }
 113
 114        if(difference)
 115           break;
 116       }
 117
 118     /* Store the node if there is a difference in the connected ways that could affect routing. */
 119
 120     if(difference)
 121       {
 122        nodesx->super[i]++;
 123
 124        nnodes++;
 125       }
 126
 127     if(!((i+1)%10000))
 128       {
 129        printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
 130        fflush(stdout);
 131       }
 132    }
 133
 134  /* Unmap from memory */
 135
 136  if(!option_slim)
 137    {
 138     segmentsx->xdata=UnmapFile(segmentsx->filename);
 139     waysx->xdata=UnmapFile(waysx->filename);
 140    }
 141
 142  /* Print the final message */
 143
 144  printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d  \n",nodesx->number,nnodes);
 145  fflush(stdout);
 146 }
 147
 148
 149 /*++++++++++++++++++++++++++++++++++++++
 150   Create the super-segments.
 151
 152   SegmentsX *CreateSuperSegments Creates the super segments.
 153
 154   NodesX *nodesx The nodes.
 155
 156   SegmentsX *segmentsx The segments.
 157
 158   WaysX *waysx The ways.
 159
 160   int iteration The current super-node / super-segment iteration number.
 161   ++++++++++++++++++++++++++++++++++++++*/
 162
 163 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
 164 {
 165  index_t i;
 166  SegmentsX *supersegmentsx;
 167  int sn=0,ss=0;
 168
 169  /* Check the start conditions */
 170
 171  assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
 172
 173  /* Print the start message */
 174
 175  printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
 176  fflush(stdout);
 177
 178  /* Map into memory */
 179
 180  if(!option_slim)
 181    {
 182     segmentsx->xdata=MapFile(segmentsx->filename);
 183     waysx->xdata=MapFile(waysx->filename);
 184    }
 185
 186  /* Create super-segments for each super-node. */
 187
 188  supersegmentsx=NewSegmentList(0);
 189
 190  for(i=0;i<nodesx->number;i++)
 191    {
 192     if(nodesx->super[i]>iteration)
 193       {
 194        index_t index,first;
 195
 196        index=first=IndexFirstSegmentX(segmentsx,i);
 197
 198        while(index!=NO_SEGMENT)
 199          {
 200           SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
 201           WayX *wayx=LookupWayX(waysx,segmentx->way,1);
 202
 203           /* Check that this type of way hasn't already been routed */
 204
 205           if(index!=first)
 206             {
 207              index_t otherindex=first;
 208
 209              while(otherindex!=NO_SEGMENT && otherindex!=index)
 210                {
 211                 SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
 212                 WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
 213
 214                 if(!WaysCompare(&otherwayx->way,&wayx->way))
 215                   {
 216                    wayx=NULL;
 217                    break;
 218                   }
 219
 220                 otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
 221                }
 222             }
 223
 224           /* Route the way and store the super-segments. */
 225
 226           if(wayx)
 227             {
 228              Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
 229              Result *result=FirstResult(results);
 230
 231              while(result)
 232                {
 233                 if(result->node!=i && nodesx->super[result->node]>iteration)
 234                   {
 235                    if(wayx->way.type&Way_OneWay)
 236                      {
 237                       AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
 238                       AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);
 239                      }
 240                    else
 241                       AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
 242
 243                    ss++;
 244                   }
 245
 246                 result=NextResult(results,result);
 247                }
 248
 249              FreeResultsList(results);
 250             }
 251
 252           index=IndexNextSegmentX(segmentsx,index,i);
 253          }
 254
 255        sn++;
 256
 257        if(!(sn%10000))
 258          {
 259           printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
 260           fflush(stdout);
 261          }
 262       }
 263    }
 264
 265  /* Unmap from memory */
 266
 267  if(!option_slim)
 268    {
 269     segmentsx->xdata=UnmapFile(segmentsx->filename);
 270     waysx->xdata=UnmapFile(waysx->filename);
 271    }
 272
 273  /* Print the final message */
 274
 275  printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
 276  fflush(stdout);
 277
 278  return(supersegmentsx);
 279 }
 280
 281
 282 /*++++++++++++++++++++++++++++++++++++++
 283   Merge the segments and super-segments into a new segment list.
 284
 285   SegmentsX* MergeSuperSegments Returns a new set of merged segments.
 286
 287   SegmentsX* segmentsx The set of segments to process.
 288
 289   SegmentsX* supersegmentsx The set of super-segments to merge.
 290   ++++++++++++++++++++++++++++++++++++++*/
 291
 292 SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
 293 {
 294  index_t i,j;
 295  int m=0,a=0;
 296  SegmentsX* mergedsegmentsx;
 297
 298  /* Print the start message */
 299
 300  printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
 301  fflush(stdout);
 302
 303  /* Map into memory */
 304
 305  if(!option_slim)
 306    {
 307     segmentsx->xdata=MapFile(segmentsx->filename);
 308     supersegmentsx->xdata=MapFile(supersegmentsx->filename);
 309    }
 310
 311  /* Loop through and create a new list of combined segments */
 312
 313  mergedsegmentsx=NewSegmentList(0);
 314
 315  for(i=0,j=0;i<segmentsx->number;i++)
 316    {
 317     int super=0;
 318     SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
 319
 320     while(j<supersegmentsx->number)
 321       {
 322        SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
 323
 324        if(segmentx->node1   ==supersegmentx->node1 &&
 325           segmentx->node2   ==supersegmentx->node2 &&
 326           segmentx->distance==supersegmentx->distance)
 327          {
 328           m++;
 329           j++;
 330           /* mark as super-segment and normal segment */
 331           super=1;
 332           break;
 333          }
 334        else if((segmentx->node1==supersegmentx->node1 &&
 335                 segmentx->node2==supersegmentx->node2) ||
 336                (segmentx->node1==supersegmentx->node1 &&
 337                 segmentx->node2>supersegmentx->node2) ||
 338                (segmentx->node1>supersegmentx->node1))
 339          {
 340           /* mark as super-segment */
 341           AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
 342           a++;
 343           j++;
 344          }
 345        else
 346          {
 347           /* mark as normal segment */
 348           break;
 349          }
 350       }
 351
 352     if(super)
 353        AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
 354     else
 355        AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
 356
 357     if(!((i+1)%10000))
 358       {
 359        printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
 360        fflush(stdout);
 361       }
 362    }
 363
 364  /* Unmap from memory */
 365
 366  if(!option_slim)
 367    {
 368     segmentsx->xdata=UnmapFile(segmentsx->filename);
 369     supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
 370    }
 371
 372  /* Print the final message */
 373
 374  printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
 375  fflush(stdout);
 376
 377  return(mergedsegmentsx);
 378 }
 379
 380
 381 /*++++++++++++++++++++++++++++++++++++++
 382   Find all routes from a specified node to any node in the specified list that follows a certain type of way.
 383
 384   Results *FindRoutesWay Returns a set of results.
 385
 386   NodesX *nodesx The set of nodes to use.
 387
 388   SegmentsX *segmentsx The set of segments to use.
 389
 390   WaysX *waysx The set of ways to use.
 391
 392   node_t start The start node.
 393
 394   Way *match The way that the route must match.
 395
 396   int iteration The current super-node / super-segment iteration number.
 397   ++++++++++++++++++++++++++++++++++++++*/
 398
 399 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
 400 {
 401  Results *results;
 402  Queue *queue;
 403  index_t node1,node2;
 404  Result *result1,*result2;
 405  index_t index;
 406  WayX *wayx;
 407
 408  /* Insert the first node into the queue */
 409
 410  results=NewResultsList(8);
 411
 412  queue=NewQueueList();
 413
 414  result1=InsertResult(results,start);
 415
 416  ZeroResult(result1);
 417
 418  InsertInQueue(queue,result1);
 419
 420  /* Loop across all nodes in the queue */
 421
 422  while((result1=PopFromQueue(queue)))
 423    {
 424     node1=result1->node;
 425
 426     index=IndexFirstSegmentX(segmentsx,node1);
 427
 428     while(index!=NO_SEGMENT)
 429       {
 430        SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
 431        distance_t cumulative_distance;
 432
 433        if(segmentx->distance&ONEWAY_2TO1)
 434           goto endloop;
 435
 436        node2=segmentx->node2;
 437
 438        if(result1->prev==node2)
 439           goto endloop;
 440
 441        wayx=LookupWayX(waysx,segmentx->way,2);
 442
 443        if(WaysCompare(&wayx->way,match))
 444           goto endloop;
 445
 446        cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
 447
 448        result2=FindResult(results,node2);
 449
 450        if(!result2)                         /* New end node */
 451          {
 452           result2=InsertResult(results,node2);
 453           result2->prev=node1;
 454           result2->next=NO_NODE;
 455           result2->score=cumulative_distance;
 456           result2->sortby=cumulative_distance;
 457
 458           if(nodesx->super[node2]<=iteration)
 459              InsertInQueue(queue,result2);
 460          }
 461        else if(cumulative_distance<result2->score)
 462          {
 463           result2->prev=node1;
 464           result2->score=cumulative_distance;
 465           result2->sortby=cumulative_distance;
 466
 467           if(nodesx->super[node2]<=iteration)
 468              InsertInQueue(queue,result2);
 469          }
 470
 471       endloop:
 472
 473        index=IndexNextSegmentX(segmentsx,index,node1);
 474       }
 475    }
 476
 477  FreeQueueList(queue);
 478
 479  return(results);
 480 }