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