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 1423 - (show annotations) (download) (as text)
Tue Jun 25 18:17:16 2013 UTC (11 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 15236 byte(s) 
Change the ChooseSuperNodes() and MergeSuperSegments() functions to read through
the file instead of mapping the data to help slim mode (since the nodes in the
first case and segments in the second case are read sequentially).
1 /***************************************
2 Super-Segment data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2013 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
25 #include "types.h"
26 #include "segments.h"
27 #include "ways.h"
28
29 #include "typesx.h"
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 *FindSuperRoutes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match);
43
44
45 /*++++++++++++++++++++++++++++++++++++++
46 Select the super-nodes from the list of nodes.
47
48 NodesX *nodesx The set of nodes to use.
49
50 SegmentsX *segmentsx The set of segments to use.
51
52 WaysX *waysx The set of ways to use.
53 ++++++++++++++++++++++++++++++++++++++*/
54
55 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
56 {
57 index_t i;
58 index_t 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 /* Allocate and set the super-node markers */
68
69 if(!nodesx->super)
70 {
71 nodesx->super=AllocBitMask(nodesx->number);
72
73 logassert(nodesx->super,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */
74
75 SetAllBits(nodesx->super,nodesx->number);
76 }
77
78 /* Map into memory / open the files */
79
80 nodesx->fd=ReOpenFileBuffered(nodesx->filename_tmp);
81
82 #if !SLIM
83 segmentsx->data=MapFile(segmentsx->filename_tmp);
84 waysx->data=MapFile(waysx->filename_tmp);
85 #else
86 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
87 waysx->fd=SlimMapFile(waysx->filename_tmp);
88
89 InvalidateSegmentXCache(segmentsx->cache);
90 InvalidateWayXCache(waysx->cache);
91 #endif
92
93 /* Find super-nodes */
94
95 for(i=0;i<nodesx->number;i++)
96 {
97 NodeX nodex;
98
99 ReadFileBuffered(nodesx->fd,&nodex,sizeof(NodeX));
100
101 if(IsBitSet(nodesx->super,i))
102 {
103 int issuper=0;
104
105 if(nodex.flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
106 issuper=1;
107 else
108 {
109 int count=0,j;
110 Way segmentway[MAX_SEG_PER_NODE];
111 int segmentweight[MAX_SEG_PER_NODE];
112 SegmentX *segmentx=FirstSegmentX(segmentsx,i,1);
113
114 while(segmentx)
115 {
116 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
117 int nsegments;
118
119 /* Segments that are loops count twice */
120
121 logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of information stored. */
122
123 if(segmentx->node1==segmentx->node2)
124 segmentweight[count]=2;
125 else
126 segmentweight[count]=1;
127
128 segmentway[count]=wayx->way;
129
130 /* If the node allows less traffic types than any connecting way then it is super if it allows anything */
131
132 if((wayx->way.allow&nodex.allow)!=wayx->way.allow && nodex.allow!=Transports_None)
133 {
134 issuper=1;
135 break;
136 }
137
138 nsegments=segmentweight[count];
139
140 for(j=0;j<count;j++)
141 if(wayx->way.allow & segmentway[j].allow)
142 {
143 /* If two ways are different in any attribute and there is a type of traffic that can use both then it is super */
144
145 if(WaysCompare(&segmentway[j],&wayx->way))
146 {
147 issuper=1;
148 break;
149 }
150
151 /* If there are two other segments that can be used by the same types of traffic as this one then it is super */
152
153 nsegments+=segmentweight[j];
154 if(nsegments>2)
155 {
156 issuper=1;
157 break;
158 }
159 }
160
161 if(issuper)
162 break;
163
164 segmentx=NextSegmentX(segmentsx,segmentx,i);
165
166 count++;
167 }
168 }
169
170 /* Mark the node as super if it is. */
171
172 if(issuper)
173 nnodes++;
174 else
175 ClearBit(nodesx->super,i);
176 }
177
178 if(!((i+1)%10000))
179 printf_middle("Finding Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,i+1,nnodes);
180 }
181
182 /* Unmap from memory / close the files */
183
184 #if !SLIM
185 segmentsx->data=UnmapFile(segmentsx->data);
186 waysx->data=UnmapFile(waysx->data);
187 #else
188 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
189 waysx->fd=SlimUnmapFile(waysx->fd);
190 #endif
191
192 nodesx->fd=CloseFileBuffered(nodesx->fd);
193
194 /* Print the final message */
195
196 printf_last("Found Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,nodesx->number,nnodes);
197 }
198
199
200 /*++++++++++++++++++++++++++++++++++++++
201 Create the super-segments from the existing segments.
202
203 SegmentsX *CreateSuperSegments Returns the new super segments.
204
205 NodesX *nodesx The set of nodes to use.
206
207 SegmentsX *segmentsx The set of segments to use.
208
209 WaysX *waysx The set of ways to use.
210 ++++++++++++++++++++++++++++++++++++++*/
211
212 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
213 {
214 index_t i;
215 SegmentsX *supersegmentsx;
216 index_t sn=0,ss=0;
217
218 supersegmentsx=NewSegmentList();
219
220 if(segmentsx->number==0 || waysx->number==0)
221 {
222 FinishSegmentList(supersegmentsx);
223
224 return(supersegmentsx);
225 }
226
227 /* Print the start message */
228
229 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
230
231 /* Map into memory / open the files */
232
233 #if !SLIM
234 nodesx->data=MapFile(nodesx->filename_tmp);
235 segmentsx->data=MapFile(segmentsx->filename_tmp);
236 waysx->data=MapFile(waysx->filename_tmp);
237 #else
238 nodesx->fd=SlimMapFile(nodesx->filename_tmp);
239 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
240 waysx->fd=SlimMapFile(waysx->filename_tmp);
241
242 InvalidateNodeXCache(nodesx->cache);
243 InvalidateSegmentXCache(segmentsx->cache);
244 InvalidateWayXCache(waysx->cache);
245 #endif
246
247 /* Create super-segments for each super-node. */
248
249 for(i=0;i<nodesx->number;i++)
250 {
251 if(IsBitSet(nodesx->super,i))
252 {
253 SegmentX *segmentx;
254 int count=0,match;
255 Way prevway[MAX_SEG_PER_NODE];
256
257 segmentx=FirstSegmentX(segmentsx,i,1);
258
259 while(segmentx)
260 {
261 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
262
263 /* Check that this type of way hasn't already been routed */
264
265 match=0;
266
267 if(count>0)
268 {
269 int j;
270
271 for(j=0;j<count;j++)
272 if(!WaysCompare(&prevway[j],&wayx->way))
273 {
274 match=1;
275 break;
276 }
277 }
278
279 logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of history stored. */
280
281 prevway[count++]=wayx->way;
282
283 /* Route the way and store the super-segments. */
284
285 if(!match)
286 {
287 Results *results=FindSuperRoutes(nodesx,segmentsx,waysx,i,&wayx->way);
288 Result *result=FirstResult(results);
289
290 while(result)
291 {
292 if(IsBitSet(nodesx->super,result->node) && result->segment!=NO_SEGMENT)
293 {
294 if(wayx->way.type&Highway_OneWay && result->node!=i)
295 AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
296 else
297 AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
298
299 ss++;
300 }
301
302 result=NextResult(results,result);
303 }
304
305 FreeResultsList(results);
306 }
307
308 segmentx=NextSegmentX(segmentsx,segmentx,i);
309 }
310
311 sn++;
312
313 if(!(sn%10000))
314 printf_middle("Creating Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
315 }
316 }
317
318 FinishSegmentList(supersegmentsx);
319
320 /* Unmap from memory / close the files */
321
322 #if !SLIM
323 nodesx->data=UnmapFile(nodesx->data);
324 segmentsx->data=UnmapFile(segmentsx->data);
325 waysx->data=UnmapFile(waysx->data);
326 #else
327 nodesx->fd=SlimUnmapFile(nodesx->fd);
328 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
329 waysx->fd=SlimUnmapFile(waysx->fd);
330 #endif
331
332 /* Print the final message */
333
334 printf_last("Created Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
335
336 return(supersegmentsx);
337 }
338
339
340 /*++++++++++++++++++++++++++++++++++++++
341 Merge the segments and super-segments into a new segment list.
342
343 SegmentsX *MergeSuperSegments Returns a new set of merged segments.
344
345 SegmentsX *segmentsx The set of segments to use.
346
347 SegmentsX *supersegmentsx The set of super-segments to use.
348 ++++++++++++++++++++++++++++++++++++++*/
349
350 SegmentsX *MergeSuperSegments(SegmentsX *segmentsx,SegmentsX *supersegmentsx)
351 {
352 index_t i,j,lastj;
353 index_t merged=0,added=0;
354 SegmentsX *mergedsegmentsx;
355
356 mergedsegmentsx=NewSegmentList();
357
358 if(segmentsx->number==0)
359 {
360 FinishSegmentList(mergedsegmentsx);
361
362 return(mergedsegmentsx);
363 }
364
365 /* Print the start message */
366
367 printf_first("Merging Segments: Segments=0 Super=0 Merged=0 Added=0");
368
369 /* Open the files */
370
371 segmentsx->fd=ReOpenFileBuffered(segmentsx->filename_tmp);
372 if(supersegmentsx->number>0)
373 supersegmentsx->fd=ReOpenFileBuffered(supersegmentsx->filename_tmp);
374
375 /* Loop through and create a new list of combined segments */
376
377 lastj=-1;
378 j=0;
379
380 for(i=0;i<segmentsx->number;i++)
381 {
382 int super=0;
383 SegmentX segmentx;
384
385 ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX));
386
387 while(j<supersegmentsx->number)
388 {
389 SegmentX supersegmentx;
390
391 if(j!=lastj)
392 {
393 ReadFileBuffered(supersegmentsx->fd,&supersegmentx,sizeof(SegmentX));
394 lastj=j;
395 }
396
397 if(segmentx.node1 ==supersegmentx.node1 &&
398 segmentx.node2 ==supersegmentx.node2 &&
399 segmentx.distance==supersegmentx.distance)
400 {
401 merged++;
402 j++;
403 /* mark as super-segment and normal segment */
404 super=1;
405 break;
406 }
407 else if((segmentx.node1==supersegmentx.node1 &&
408 segmentx.node2==supersegmentx.node2) ||
409 (segmentx.node1==supersegmentx.node1 &&
410 segmentx.node2>supersegmentx.node2) ||
411 (segmentx.node1>supersegmentx.node1))
412 {
413 /* mark as super-segment */
414 AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);
415 added++;
416 j++;
417 }
418 else
419 {
420 /* mark as normal segment */
421 break;
422 }
423 }
424
425 if(super)
426 AppendSegmentList(mergedsegmentsx,segmentx.way,segmentx.node1,segmentx.node2,segmentx.distance|SEGMENT_SUPER|SEGMENT_NORMAL);
427 else
428 AppendSegmentList(mergedsegmentsx,segmentx.way,segmentx.node1,segmentx.node2,segmentx.distance|SEGMENT_NORMAL);
429
430 if(!((i+1)%10000))
431 printf_middle("Merging Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,i+1,j,merged,added);
432 }
433
434 FinishSegmentList(mergedsegmentsx);
435
436 /* Close the files */
437
438 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
439 if(supersegmentsx->number>0)
440 supersegmentsx->fd=CloseFileBuffered(supersegmentsx->fd);
441
442 /* Print the final message */
443
444 printf_last("Merged Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,segmentsx->number,supersegmentsx->number,merged,added);
445
446 return(mergedsegmentsx);
447 }
448
449
450 /*++++++++++++++++++++++++++++++++++++++
451 Find all routes from a specified super-node to any other super-node that follows a certain type of way.
452
453 Results *FindSuperRoutes Returns a set of results.
454
455 NodesX *nodesx The set of nodes to use.
456
457 SegmentsX *segmentsx The set of segments to use.
458
459 WaysX *waysx The set of ways to use.
460
461 node_t start The start node.
462
463 Way *match A template for the type of way that the route must follow.
464 ++++++++++++++++++++++++++++++++++++++*/
465
466 static Results *FindSuperRoutes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match)
467 {
468 Results *results;
469 Queue *queue;
470 Result *result1,*result2;
471 WayX *wayx;
472
473 /* Insert the first node into the queue */
474
475 results=NewResultsList(8);
476 queue=NewQueueList(8);
477
478 result1=InsertResult(results,start,NO_SEGMENT);
479
480 InsertInQueue(queue,result1,0);
481
482 /* Loop across all nodes in the queue */
483
484 while((result1=PopFromQueue(queue)))
485 {
486 index_t node1;
487 SegmentX *segmentx;
488
489 node1=result1->node;
490
491 segmentx=FirstSegmentX(segmentsx,node1,2); /* position 1 is already used */
492
493 while(segmentx)
494 {
495 NodeX *node2x;
496 index_t node2,seg2;
497 distance_t cumulative_distance;
498
499 /* must not be one-way against the direction of travel */
500 if(IsOnewayTo(segmentx,node1))
501 goto endloop;
502
503 seg2=IndexSegmentX(segmentsx,segmentx);
504
505 /* must not be a u-turn */
506 if(result1->segment==seg2)
507 goto endloop;
508
509 wayx=LookupWayX(waysx,segmentx->way,2); /* position 1 is already used */
510
511 /* must be the right type of way */
512 if(WaysCompare(&wayx->way,match))
513 goto endloop;
514
515 node2=OtherNode(segmentx,node1);
516
517 node2x=LookupNodeX(nodesx,node2,2); /* position 1 is already used */
518
519 /* Don't route beyond a node with no access */
520 if(node2x->allow==Transports_None)
521 goto endloop;
522
523 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
524
525 result2=FindResult(results,node2,seg2);
526
527 if(!result2) /* New end node */
528 {
529 result2=InsertResult(results,node2,seg2);
530 result2->prev=result1;
531 result2->score=cumulative_distance;
532
533 /* don't route beyond a super-node. */
534 if(!IsBitSet(nodesx->super,node2))
535 InsertInQueue(queue,result2,cumulative_distance);
536 }
537 else if(cumulative_distance<result2->score)
538 {
539 result2->prev=result1;
540 result2->score=cumulative_distance;
541
542 /* don't route beyond a super-node. */
543 if(!IsBitSet(nodesx->super,node2))
544 InsertInQueue(queue,result2,cumulative_distance);
545 }
546
547 endloop:
548
549 segmentx=NextSegmentX(segmentsx,segmentx,node1);
550 }
551 }
552
553 FreeQueueList(queue);
554
555 return(results);
556 }

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