1 /***************************************
2 $Header: /home/amb/routino/src/RCS/superx.c,v 1.45 2010/11/13 14:22:28 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 ***************************************/
31 #include "segmentsx.h"
42 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);
45 /*++++++++++++++++++++++++++++++++++++++
46 Select the super-segments from the list of segments.
48 NodesX *nodesx The nodes.
50 SegmentsX *segmentsx The segments.
52 WaysX *waysx The ways.
53 ++++++++++++++++++++++++++++++++++++++*/
55 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
60 if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
63 /* Print the start message */
65 printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
70 nodesx->xdata=MapFile(nodesx->filename);
71 segmentsx->xdata=MapFile(segmentsx->filename);
72 waysx->xdata=MapFile(waysx->filename);
75 /* Find super-nodes */
77 for(i=0;i<nodesx->number;i++)
79 NodeX *nodex=LookupNodeX(nodesx,i,1);
81 index_t index1,index2;
83 index1=IndexFirstSegmentX(segmentsx,i);
85 while(index1!=NO_SEGMENT)
87 SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
88 WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
90 index1=IndexNextSegmentX(segmentsx,index1,i);
93 /* If the node allows less traffic types than any connecting way ... */
95 if((wayx1->way.allow&nodex->allow)!=wayx1->way.allow)
101 while(index2!=NO_SEGMENT)
103 SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
104 WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
106 /* If the ways are different in any attribute and there is a type of traffic that can use both ... */
108 if(WaysCompare(&wayx1->way,&wayx2->way))
109 if(wayx1->way.allow & wayx2->way.allow)
115 index2=IndexNextSegmentX(segmentsx,index2,i);
122 /* Store the node if there is a difference in the connected ways that could affect routing. */
132 printf_middle("Finding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
135 /* Unmap from memory */
138 nodesx->xdata=UnmapFile(nodesx->filename);
139 segmentsx->xdata=UnmapFile(segmentsx->filename);
140 waysx->xdata=UnmapFile(waysx->filename);
143 /* Print the final message */
145 printf_last("Found Super-Nodes: Nodes=%d Super-Nodes=%d",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 supersegmentsx=NewSegmentList(0);
171 if(segmentsx->number==0 || waysx->number==0)
172 return(supersegmentsx);
174 /* Print the start message */
176 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
178 /* Map into memory */
181 segmentsx->xdata=MapFile(segmentsx->filename);
182 waysx->xdata=MapFile(waysx->filename);
185 /* Create super-segments for each super-node. */
187 for(i=0;i<nodesx->number;i++)
189 if(nodesx->super[i]>iteration)
193 index=first=IndexFirstSegmentX(segmentsx,i);
195 while(index!=NO_SEGMENT)
197 SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
198 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
200 /* Check that this type of way hasn't already been routed */
204 index_t otherindex=first;
206 while(otherindex!=NO_SEGMENT && otherindex!=index)
208 SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
209 WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
211 if(!WaysCompare(&otherwayx->way,&wayx->way))
217 otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
221 /* Route the way and store the super-segments. */
225 Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
226 Result *result=FirstResult(results);
230 if(result->node!=i && nodesx->super[result->node]>iteration)
232 if(wayx->way.type&Way_OneWay)
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);
238 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
243 result=NextResult(results,result);
246 FreeResultsList(results);
249 index=IndexNextSegmentX(segmentsx,index,i);
255 printf_middle("Creating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
259 /* Unmap from memory */
262 segmentsx->xdata=UnmapFile(segmentsx->filename);
263 waysx->xdata=UnmapFile(waysx->filename);
266 /* Print the final message */
268 printf_last("Created Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
270 return(supersegmentsx);
274 /*++++++++++++++++++++++++++++++++++++++
275 Merge the segments and super-segments into a new segment list.
277 SegmentsX* MergeSuperSegments Returns a new set of merged segments.
279 SegmentsX* segmentsx The set of segments to process.
281 SegmentsX* supersegmentsx The set of super-segments to merge.
282 ++++++++++++++++++++++++++++++++++++++*/
284 SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
288 SegmentsX* mergedsegmentsx;
290 mergedsegmentsx=NewSegmentList(0);
292 if(segmentsx->number==0 || supersegmentsx->number==0)
293 return(mergedsegmentsx);
295 /* Print the start message */
297 printf_first("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
299 /* Map into memory */
302 segmentsx->xdata=MapFile(segmentsx->filename);
303 supersegmentsx->xdata=MapFile(supersegmentsx->filename);
306 /* Loop through and create a new list of combined segments */
308 for(i=0,j=0;i<segmentsx->number;i++)
311 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
313 while(j<supersegmentsx->number)
315 SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
317 if(segmentx->node1 ==supersegmentx->node1 &&
318 segmentx->node2 ==supersegmentx->node2 &&
319 segmentx->distance==supersegmentx->distance)
323 /* mark as super-segment and normal segment */
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))
333 /* mark as super-segment */
334 AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
340 /* mark as normal segment */
346 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
348 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
351 printf_middle("Merging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
354 /* Unmap from memory */
357 segmentsx->xdata=UnmapFile(segmentsx->filename);
358 supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
361 /* Print the final message */
363 printf_last("Merged: Segments=%d Super-Segments=%d Merged=%d Added=%d",segmentsx->number,supersegmentsx->number,m,a);
365 return(mergedsegmentsx);
369 /*++++++++++++++++++++++++++++++++++++++
370 Find all routes from a specified node to any node in the specified list that follows a certain type of way.
372 Results *FindRoutesWay Returns a set of results.
374 NodesX *nodesx The set of nodes to use.
376 SegmentsX *segmentsx The set of segments to use.
378 WaysX *waysx The set of ways to use.
380 node_t start The start node.
382 Way *match The way that the route must match.
384 int iteration The current super-node / super-segment iteration number.
385 ++++++++++++++++++++++++++++++++++++++*/
387 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
392 Result *result1,*result2;
396 /* Insert the first node into the queue */
398 results=NewResultsList(8);
400 queue=NewQueueList();
402 result1=InsertResult(results,start);
406 InsertInQueue(queue,result1);
408 /* Loop across all nodes in the queue */
410 while((result1=PopFromQueue(queue)))
414 index=IndexFirstSegmentX(segmentsx,node1);
416 while(index!=NO_SEGMENT)
418 SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
419 distance_t cumulative_distance;
421 if(segmentx->distance&ONEWAY_2TO1)
424 node2=segmentx->node2;
426 if(result1->prev==node2)
429 wayx=LookupWayX(waysx,segmentx->way,2);
431 if(WaysCompare(&wayx->way,match))
434 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
436 result2=FindResult(results,node2);
438 if(!result2) /* New end node */
440 result2=InsertResult(results,node2);
442 result2->next=NO_NODE;
443 result2->score=cumulative_distance;
444 result2->sortby=cumulative_distance;
446 if(nodesx->super[node2]<=iteration)
447 InsertInQueue(queue,result2);
449 else if(cumulative_distance<result2->score)
452 result2->score=cumulative_distance;
453 result2->sortby=cumulative_distance;
455 if(nodesx->super[node2]<=iteration)
456 InsertInQueue(queue,result2);
461 index=IndexNextSegmentX(segmentsx,index,node1);
465 FreeQueueList(queue);