Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/superx.c
ViewVC logotype

Contents of /trunk/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 643 - (show annotations) (download) (as text)
Sat Feb 26 16:37:14 2011 UTC (14 years ago) by amb
File MIME type: text/x-csrc
File size: 13389 byte(s) 
Go back to the internal structure used (but reverted) during version 1.2
development where each segment is stored only once.  This halves the memory
usage (mmap files or just files) for planetsplitter.  This is allowed because a
new algorithm to create the node to segment indexes makes it simpler now that it
was.  This change is required so that super-node/segment optimisation doesn't
remove mutual loops.  This change doesn't handle turn restrictions yet.
1 /***************************************
2 Super-Segment data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2011 Andrew M. Bishop
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU Affero General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Affero General Public License for more details.
17
18 You should have received a copy of the GNU Affero General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 ***************************************/
21
22
23 #include <stdlib.h>
24 #include <stdio.h>
25
26 #include "ways.h"
27
28 #include "nodesx.h"
29 #include "segmentsx.h"
30 #include "waysx.h"
31 #include "superx.h"
32
33 #include "files.h"
34 #include "logging.h"
35 #include "results.h"
36
37
38 /* Local Functions */
39
40 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);
41
42
43 /*++++++++++++++++++++++++++++++++++++++
44 Select the super-segments from the list of segments.
45
46 NodesX *nodesx The nodes.
47
48 SegmentsX *segmentsx The segments.
49
50 WaysX *waysx The ways.
51 ++++++++++++++++++++++++++++++++++++++*/
52
53 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
54 {
55 index_t i;
56 int nnodes=0;
57
58 if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
59 return;
60
61 /* Print the start message */
62
63 printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
64
65 /* Map into memory / open the files */
66
67 #if !SLIM
68 nodesx->xdata=MapFile(nodesx->filename);
69 segmentsx->xdata=MapFile(segmentsx->filename);
70 waysx->xdata=MapFile(waysx->filename);
71 #else
72 nodesx->fd=ReOpenFile(nodesx->filename);
73 segmentsx->fd=ReOpenFile(segmentsx->filename);
74 waysx->fd=ReOpenFile(waysx->filename);
75 #endif
76
77 /* Find super-nodes */
78
79 for(i=0;i<nodesx->number;i++)
80 {
81 NodeX *nodex=LookupNodeX(nodesx,i,1);
82 int difference=0,nsegments=0;
83 SegmentX *segmentx=NULL;
84 int waycount=0;
85 Way prevway[16];
86
87 segmentx=FirstSegmentX2(segmentsx,i,1);
88
89 while(segmentx)
90 {
91 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
92
93 nsegments++;
94 if(segmentx->node1==segmentx->node2)
95 nsegments+=1; /* The segment is stored once but goes both ways */
96
97 /* If the node allows less traffic types than any connecting way ... */
98
99 if((wayx->way.allow&nodex->allow)!=wayx->way.allow)
100 {
101 difference=1;
102 break;
103 }
104
105 /* If the ways are different in any attribute and there is a type of traffic that can use both ... */
106
107 if(waycount>0)
108 {
109 int j;
110
111 for(j=0;j<waycount;j++)
112 if(WaysCompare(&prevway[j],&wayx->way))
113 if(wayx->way.allow & prevway[j].allow)
114 {
115 difference=1;
116 break;
117 }
118 }
119
120 assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));
121
122 prevway[waycount++]=wayx->way;
123
124 if(difference)
125 break;
126
127 segmentx=NextSegmentX2(segmentsx,segmentx,i,1);
128 }
129
130 /* Store the node if there is a difference in the connected ways that could affect routing. */
131
132 if(difference || nsegments>2 || nodex->flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
133 {
134 nodesx->super[i]++;
135
136 nnodes++;
137 }
138
139 if(!((i+1)%10000))
140 printf_middle("Finding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
141 }
142
143 /* Unmap from memory / close the files */
144
145 #if !SLIM
146 nodesx->xdata=UnmapFile(nodesx->filename);
147 segmentsx->xdata=UnmapFile(segmentsx->filename);
148 waysx->xdata=UnmapFile(waysx->filename);
149 #else
150 nodesx->fd=CloseFile(nodesx->fd);
151 segmentsx->fd=CloseFile(segmentsx->fd);
152 waysx->fd=CloseFile(waysx->fd);
153 #endif
154
155 /* Print the final message */
156
157 printf_last("Found Super-Nodes: Nodes=%d Super-Nodes=%d",nodesx->number,nnodes);
158 }
159
160
161 /*++++++++++++++++++++++++++++++++++++++
162 Create the super-segments.
163
164 SegmentsX *CreateSuperSegments Creates the super segments.
165
166 NodesX *nodesx The nodes.
167
168 SegmentsX *segmentsx The segments.
169
170 WaysX *waysx The ways.
171
172 int iteration The current super-node / super-segment iteration number.
173 ++++++++++++++++++++++++++++++++++++++*/
174
175 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
176 {
177 index_t i;
178 SegmentsX *supersegmentsx;
179 int sn=0,ss=0;
180
181 supersegmentsx=NewSegmentList(0);
182
183 if(segmentsx->number==0 || waysx->number==0)
184 return(supersegmentsx);
185
186 /* Print the start message */
187
188 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
189
190 /* Map into memory / open the files */
191
192 #if !SLIM
193 segmentsx->xdata=MapFile(segmentsx->filename);
194 waysx->xdata=MapFile(waysx->filename);
195 #else
196 segmentsx->fd=ReOpenFile(segmentsx->filename);
197 waysx->fd=ReOpenFile(waysx->filename);
198 #endif
199
200 /* Create super-segments for each super-node. */
201
202 for(i=0;i<nodesx->number;i++)
203 {
204 if(nodesx->super[i]>iteration)
205 {
206 SegmentX *segmentx;
207 int waycount=0,match;
208 Way prevway[16];
209
210 segmentx=FirstSegmentX2(segmentsx,i,1);
211
212 while(segmentx)
213 {
214 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
215
216 /* Check that this type of way hasn't already been routed */
217
218 match=0;
219
220 if(waycount>0)
221 {
222 int j;
223
224 for(j=0;j<waycount;j++)
225 if(!WaysCompare(&prevway[j],&wayx->way))
226 {
227 match=1;
228 break;
229 }
230 }
231
232 assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));
233
234 prevway[waycount++]=wayx->way;
235
236 /* Route the way and store the super-segments. */
237
238 if(!match)
239 {
240 Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
241 Result *result=FirstResult(results);
242
243 while(result)
244 {
245 if(nodesx->super[result->node]>iteration && result->segment!=NO_SEGMENT)
246 {
247 if(wayx->way.type&Way_OneWay && result->node!=i)
248 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
249 else
250 AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
251
252 ss++;
253 }
254
255 result=NextResult(results,result);
256 }
257
258 FreeResultsList(results);
259 }
260
261 segmentx=NextSegmentX2(segmentsx,segmentx,i,1);
262 }
263
264 sn++;
265
266 if(!(sn%10000))
267 printf_middle("Creating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
268 }
269 }
270
271 /* Unmap from memory / close the files */
272
273 #if !SLIM
274 segmentsx->xdata=UnmapFile(segmentsx->filename);
275 waysx->xdata=UnmapFile(waysx->filename);
276 #else
277 segmentsx->fd=CloseFile(segmentsx->fd);
278 waysx->fd=CloseFile(waysx->fd);
279 #endif
280
281 /* Print the final message */
282
283 printf_last("Created Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
284
285 return(supersegmentsx);
286 }
287
288
289 /*++++++++++++++++++++++++++++++++++++++
290 Merge the segments and super-segments into a new segment list.
291
292 SegmentsX* MergeSuperSegments Returns a new set of merged segments.
293
294 SegmentsX* segmentsx The set of segments to process.
295
296 SegmentsX* supersegmentsx The set of super-segments to merge.
297 ++++++++++++++++++++++++++++++++++++++*/
298
299 SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
300 {
301 index_t i,j;
302 int m=0,a=0;
303 SegmentsX* mergedsegmentsx;
304
305 mergedsegmentsx=NewSegmentList(0);
306
307 if(segmentsx->number==0)
308 return(mergedsegmentsx);
309
310 /* Print the start message */
311
312 printf_first("Merging Segments: Segments=0 Super-Segments=0 Merged=0 Added=0");
313
314 /* Map into memory / open the files */
315
316 #if !SLIM
317 segmentsx->xdata=MapFile(segmentsx->filename);
318 if(supersegmentsx->number>0)
319 supersegmentsx->xdata=MapFile(supersegmentsx->filename);
320 #else
321 segmentsx->fd=ReOpenFile(segmentsx->filename);
322 if(supersegmentsx->number>0)
323 supersegmentsx->fd=ReOpenFile(supersegmentsx->filename);
324 #endif
325
326 /* Loop through and create a new list of combined segments */
327
328 for(i=0,j=0;i<segmentsx->number;i++)
329 {
330 int super=0;
331 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
332
333 while(j<supersegmentsx->number)
334 {
335 SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
336
337 if(segmentx->node1 ==supersegmentx->node1 &&
338 segmentx->node2 ==supersegmentx->node2 &&
339 segmentx->distance==supersegmentx->distance)
340 {
341 m++;
342 j++;
343 /* mark as super-segment and normal segment */
344 super=1;
345 break;
346 }
347 else if((segmentx->node1==supersegmentx->node1 &&
348 segmentx->node2==supersegmentx->node2) ||
349 (segmentx->node1==supersegmentx->node1 &&
350 segmentx->node2>supersegmentx->node2) ||
351 (segmentx->node1>supersegmentx->node1))
352 {
353 /* mark as super-segment */
354 AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
355 a++;
356 j++;
357 }
358 else
359 {
360 /* mark as normal segment */
361 break;
362 }
363 }
364
365 if(super)
366 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
367 else
368 AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);
369
370 if(!((i+1)%10000))
371 printf_middle("Merging Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
372 }
373
374 /* Unmap from memory / close the files */
375
376 #if !SLIM
377 segmentsx->xdata=UnmapFile(segmentsx->filename);
378 if(supersegmentsx->number>0)
379 supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
380 #else
381 segmentsx->fd=CloseFile(segmentsx->fd);
382 if(supersegmentsx->number>0)
383 supersegmentsx->fd=CloseFile(supersegmentsx->fd);
384 #endif
385
386 /* Print the final message */
387
388 printf_last("Merged Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",segmentsx->number,supersegmentsx->number,m,a);
389
390 return(mergedsegmentsx);
391 }
392
393
394 /*++++++++++++++++++++++++++++++++++++++
395 Find all routes from a specified node to any node in the specified list that follows a certain type of way.
396
397 Results *FindRoutesWay Returns a set of results.
398
399 NodesX *nodesx The set of nodes to use.
400
401 SegmentsX *segmentsx The set of segments to use.
402
403 WaysX *waysx The set of ways to use.
404
405 node_t start The start node.
406
407 Way *match The way that the route must match.
408
409 int iteration The current super-node / super-segment iteration number.
410 ++++++++++++++++++++++++++++++++++++++*/
411
412 static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
413 {
414 Results *results;
415 Queue *queue;
416 Result *result1,*result2;
417 WayX *wayx;
418
419 /* Insert the first node into the queue */
420
421 results=NewResultsList(8);
422
423 queue=NewQueueList();
424
425 result1=InsertResult(results,start,NO_SEGMENT);
426
427 InsertInQueue(queue,result1);
428
429 /* Loop across all nodes in the queue */
430
431 while((result1=PopFromQueue(queue)))
432 {
433 index_t node1,seg1;
434 SegmentX *segmentx;
435
436 node1=result1->node;
437 seg1=result1->segment;
438
439 segmentx=FirstSegmentX2(segmentsx,node1,2); /* position 1 is already used */
440
441 while(segmentx)
442 {
443 index_t node2,seg2;
444 distance_t cumulative_distance;
445
446 if(segmentx->node1==node1)
447 {
448 if(segmentx->distance&ONEWAY_2TO1)
449 goto endloop;
450
451 node2=segmentx->node2;
452 }
453 else /* if(segmentx->node2==node1) */
454 {
455 if(segmentx->distance&ONEWAY_1TO2)
456 goto endloop;
457
458 node2=segmentx->node1;
459 }
460
461 seg2=IndexSegmentX(segmentsx,segmentx);
462
463 if(result1->prev && result1->prev->node==node2 && node1!=node2)
464 goto endloop;
465
466 wayx=LookupWayX(waysx,segmentx->way,2);
467
468 if(WaysCompare(&wayx->way,match))
469 goto endloop;
470
471 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
472
473 result2=FindResult(results,node2,seg2);
474
475 if(!result2) /* New end node */
476 {
477 result2=InsertResult(results,node2,seg2);
478 result2->prev=result1;
479 result2->score=cumulative_distance;
480 result2->sortby=cumulative_distance;
481
482 if(nodesx->super[node2]<=iteration)
483 InsertInQueue(queue,result2);
484 }
485 else if(cumulative_distance<result2->score)
486 {
487 result2->prev=result1;
488 result2->score=cumulative_distance;
489 result2->sortby=cumulative_distance;
490
491 if(nodesx->super[node2]<=iteration)
492 InsertInQueue(queue,result2);
493 }
494
495 endloop:
496
497 segmentx=NextSegmentX2(segmentsx,segmentx,node1,2);
498 }
499 }
500
501 FreeQueueList(queue);
502
503 return(results);
504 }

Properties

Name Value
cvs:description Super-nodes and super-segments functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root