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

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