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 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)
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. |