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