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

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