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