1 /***************************************
2 $Header: /home/amb/routino/src/RCS/superx.c,v 1.38 2010/07/05 19:05:51 amb Exp $
4 Super-Segment data type functions.
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
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.
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.
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 ***************************************/
30 #include "functions.h"
32 #include "segmentsx.h"
40 /*+ The command line '--slim' option. +*/
41 extern int option_slim;
45 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);
48 /*++++++++++++++++++++++++++++++++++++++
49 Select the super-segments from the list of segments.
51 NodesX *nodesx The nodes.
53 SegmentsX *segmentsx The segments.
55 WaysX *waysx The ways.
56 ++++++++++++++++++++++++++++++++++++++*/
58 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
63 /* Check the start conditions */
65 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
67 /* Print the start message */
69 printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
76 segmentsx->xdata=MapFile(segmentsx->filename);
77 waysx->xdata=MapFile(waysx->filename);
80 /* Find super-nodes */
82 for(i=0;i<nodesx->number;i++)
85 index_t index1,index2;
87 index1=IndexFirstSegmentX(segmentsx,i);
89 while(index1!=NO_SEGMENT)
91 SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
92 WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
94 index1=IndexNextSegmentX(segmentsx,index1,i);
97 while(index2!=NO_SEGMENT)
99 SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
100 WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
102 /* If the ways are different in any way and there is a type of traffic that can use both ... */
104 if(WaysCompare(&wayx1->way,&wayx2->way))
105 if(wayx1->way.allow & wayx2->way.allow)
111 index2=IndexNextSegmentX(segmentsx,index2,i);
118 /* Store the node if there is a difference in the connected ways that could affect routing. */
129 printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
134 /* Unmap from memory */
138 segmentsx->xdata=UnmapFile(segmentsx->filename);
139 waysx->xdata=UnmapFile(waysx->filename);
142 /* Print the final message */
144 printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
149 /*++++++++++++++++++++++++++++++++++++++
150 Create the super-segments.
152 SegmentsX *CreateSuperSegments Creates the super segments.
154 NodesX *nodesx The nodes.
156 SegmentsX *segmentsx The segments.
158 WaysX *waysx The ways.
160 int iteration The current super-node / super-segment iteration number.
161 ++++++++++++++++++++++++++++++++++++++*/
163 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
166 SegmentsX *supersegmentsx;
169 /* Check the start conditions */
171 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
173 /* Print the start message */
175 printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
178 /* Map into memory */
182 segmentsx->xdata=MapFile(segmentsx->filename);
183 waysx->xdata=MapFile(waysx->filename);
186 /* Create super-segments for each super-node. */
188 supersegmentsx=NewSegmentList(0);
190 for(i=0;i<nodesx->number;i++)
192 if(nodesx->super[i]>iteration)
196 index=first=IndexFirstSegmentX(segmentsx,i);
198 while(index!=NO_SEGMENT)
200 SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
201 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
203 /* Check that this type of way hasn't already been routed */
207 index_t otherindex=first;
209 while(otherindex!=NO_SEGMENT && otherindex!=index)
211 SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
212 WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
214 if(!WaysCompare(&otherwayx->way,&wayx->way))
220 otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
224 /* Route the way and store the super-segments. */
228 Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
229 Result *result=FirstResult(results);
233 if(result->node!=i && nodesx->super[result->node]>iteration)
235 if(wayx->way.type&Way_OneWay)
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);
241 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
246 result=NextResult(results,result);
249 FreeResultsList(results);
252 index=IndexNextSegmentX(segmentsx,index,i);
259 printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
265 /* Unmap from memory */
269 segmentsx->xdata=UnmapFile(segmentsx->filename);
270 waysx->xdata=UnmapFile(waysx->filename);
273 /* Print the final message */
275 printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
278 return(supersegmentsx);
282 /*++++++++++++++++++++++++++++++++++++++
283 Merge the segments and super-segments into a new segment list.
285 SegmentsX* MergeSuperSegments Returns a new set of merged segments.
287 SegmentsX* segmentsx The set of segments to process.
289 SegmentsX* supersegmentsx The set of super-segments to merge.
290 ++++++++++++++++++++++++++++++++++++++*/
292 SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
296 SegmentsX* mergedsegmentsx;
298 /* Print the start message */
300 printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
303 /* Map into memory */
307 segmentsx->xdata=MapFile(segmentsx->filename);
308 supersegmentsx->xdata=MapFile(supersegmentsx->filename);
311 /* Loop through and create a new list of combined segments */
313 mergedsegmentsx=NewSegmentList(0);
315 for(i=0,j=0;i<segmentsx->number;i++)
318 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
320 while(j<supersegmentsx->number)
322 SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
324 if(segmentx->node1 ==supersegmentx->node1 &&
325 segmentx->node2 ==supersegmentx->node2 &&
326 segmentx->distance==supersegmentx->distance)
330 /* mark as super-segment and normal segment */
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))
340 /* mark as super-segment */
341 AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
347 /* mark as normal segment */
353 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
355 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
359 printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
364 /* Unmap from memory */
368 segmentsx->xdata=UnmapFile(segmentsx->filename);
369 supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
372 /* Print the final message */
374 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
377 return(mergedsegmentsx);
381 /*++++++++++++++++++++++++++++++++++++++
382 Find all routes from a specified node to any node in the specified list that follows a certain type of way.
384 Results *FindRoutesWay Returns a set of results.
386 NodesX *nodesx The set of nodes to use.
388 SegmentsX *segmentsx The set of segments to use.
390 WaysX *waysx The set of ways to use.
392 node_t start The start node.
394 Way *match The way that the route must match.
396 int iteration The current super-node / super-segment iteration number.
397 ++++++++++++++++++++++++++++++++++++++*/
399 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
404 Result *result1,*result2;
408 /* Insert the first node into the queue */
410 results=NewResultsList(8);
412 queue=NewQueueList();
414 result1=InsertResult(results,start);
418 InsertInQueue(queue,result1);
420 /* Loop across all nodes in the queue */
422 while((result1=PopFromQueue(queue)))
426 index=IndexFirstSegmentX(segmentsx,node1);
428 while(index!=NO_SEGMENT)
430 SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
431 distance_t cumulative_distance;
433 if(segmentx->distance&ONEWAY_2TO1)
436 node2=segmentx->node2;
438 if(result1->prev==node2)
441 wayx=LookupWayX(waysx,segmentx->way,2);
443 if(WaysCompare(&wayx->way,match))
446 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
448 result2=FindResult(results,node2);
450 if(!result2) /* New end node */
452 result2=InsertResult(results,node2);
454 result2->next=NO_NODE;
455 result2->score=cumulative_distance;
456 result2->sortby=cumulative_distance;
458 if(nodesx->super[node2]<=iteration)
459 InsertInQueue(queue,result2);
461 else if(cumulative_distance<result2->score)
464 result2->score=cumulative_distance;
465 result2->sortby=cumulative_distance;
467 if(nodesx->super[node2]<=iteration)
468 InsertInQueue(queue,result2);
473 index=IndexNextSegmentX(segmentsx,index,node1);
477 FreeQueueList(queue);