Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/superx.c
Parent Directory
|
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)
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. |