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

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