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

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