Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/superx.c
Parent Directory
|
Revision Log
Revision 544 -
(hide annotations)
(download)
(as text)
Sat Dec 18 19:17:26 2010 UTC (14 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 12507 byte(s)
Sat Dec 18 19:17:26 2010 UTC (14 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 12507 byte(s)
Duplicate the IndexFirstSegmentX() and IndexNextSegmentX() functions to create two distinct one for use at different times.
1 | amb | 110 | /*************************************** |
2 | amb | 544 | $Header: /home/amb/CVS/routino/src/superx.c,v 1.46 2010-12-18 19:17:26 amb Exp $ |
3 | amb | 110 | |
4 | Super-Segment data type functions. | ||
5 | amb | 151 | |
6 | Part of the Routino routing software. | ||
7 | amb | 110 | ******************/ /****************** |
8 | amb | 326 | This file Copyright 2008-2010 Andrew M. Bishop |
9 | amb | 110 | |
10 | amb | 151 | This program is free software: you can redistribute it and/or modify |
11 | it under the terms of the GNU Affero General Public License as published by | ||
12 | the Free Software Foundation, either version 3 of the License, or | ||
13 | (at your option) any later version. | ||
14 | |||
15 | This program is distributed in the hope that it will be useful, | ||
16 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
18 | GNU Affero General Public License for more details. | ||
19 | |||
20 | You should have received a copy of the GNU Affero General Public License | ||
21 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
22 | amb | 110 | ***************************************/ |
23 | |||
24 | |||
25 | #include <stdlib.h> | ||
26 | #include <stdio.h> | ||
27 | |||
28 | amb | 449 | #include "ways.h" |
29 | |||
30 | amb | 110 | #include "nodesx.h" |
31 | #include "segmentsx.h" | ||
32 | #include "waysx.h" | ||
33 | #include "superx.h" | ||
34 | |||
35 | amb | 449 | #include "files.h" |
36 | amb | 519 | #include "logging.h" |
37 | amb | 449 | #include "results.h" |
38 | amb | 110 | |
39 | amb | 449 | |
40 | amb | 228 | /* Local Functions */ |
41 | |||
42 | static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration); | ||
43 | |||
44 | |||
45 | amb | 110 | /*++++++++++++++++++++++++++++++++++++++ |
46 | Select the super-segments from the list of segments. | ||
47 | |||
48 | NodesX *nodesx The nodes. | ||
49 | |||
50 | SegmentsX *segmentsx The segments. | ||
51 | |||
52 | WaysX *waysx The ways. | ||
53 | ++++++++++++++++++++++++++++++++++++++*/ | ||
54 | |||
55 | amb | 214 | void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx) |
56 | amb | 110 | { |
57 | amb | 214 | index_t i; |
58 | amb | 229 | int nnodes=0; |
59 | amb | 110 | |
60 | amb | 510 | if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0) |
61 | amb | 508 | return; |
62 | |||
63 | amb | 275 | /* Print the start message */ |
64 | |||
65 | amb | 519 | printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0"); |
66 | amb | 227 | |
67 | amb | 275 | /* Map into memory */ |
68 | |||
69 | amb | 452 | #if !SLIM |
70 | amb | 469 | nodesx->xdata=MapFile(nodesx->filename); |
71 | amb | 452 | segmentsx->xdata=MapFile(segmentsx->filename); |
72 | waysx->xdata=MapFile(waysx->filename); | ||
73 | #endif | ||
74 | amb | 257 | |
75 | amb | 110 | /* Find super-nodes */ |
76 | |||
77 | amb | 229 | for(i=0;i<nodesx->number;i++) |
78 | amb | 110 | { |
79 | amb | 469 | NodeX *nodex=LookupNodeX(nodesx,i,1); |
80 | amb | 434 | int difference=0; |
81 | index_t index1,index2; | ||
82 | amb | 110 | |
83 | amb | 544 | index1=IndexFirstSegmentX2(segmentsx,i); |
84 | amb | 229 | |
85 | amb | 434 | while(index1!=NO_SEGMENT) |
86 | amb | 110 | { |
87 | amb | 434 | SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1); |
88 | amb | 279 | WayX *wayx1=LookupWayX(waysx,segmentx1->way,1); |
89 | amb | 110 | |
90 | amb | 544 | index1=IndexNextSegmentX2(segmentsx,index1,i); |
91 | amb | 434 | index2=index1; |
92 | amb | 229 | |
93 | amb | 469 | /* If the node allows less traffic types than any connecting way ... */ |
94 | |||
95 | if((wayx1->way.allow&nodex->allow)!=wayx1->way.allow) | ||
96 | { | ||
97 | difference=1; | ||
98 | break; | ||
99 | } | ||
100 | |||
101 | amb | 434 | while(index2!=NO_SEGMENT) |
102 | amb | 110 | { |
103 | amb | 434 | SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2); |
104 | amb | 279 | WayX *wayx2=LookupWayX(waysx,segmentx2->way,2); |
105 | amb | 110 | |
106 | amb | 469 | /* If the ways are different in any attribute and there is a type of traffic that can use both ... */ |
107 | amb | 110 | |
108 | amb | 434 | if(WaysCompare(&wayx1->way,&wayx2->way)) |
109 | if(wayx1->way.allow & wayx2->way.allow) | ||
110 | { | ||
111 | difference=1; | ||
112 | break; | ||
113 | } | ||
114 | |||
115 | amb | 544 | index2=IndexNextSegmentX2(segmentsx,index2,i); |
116 | amb | 110 | } |
117 | |||
118 | amb | 434 | if(difference) |
119 | break; | ||
120 | } | ||
121 | amb | 110 | |
122 | amb | 434 | /* Store the node if there is a difference in the connected ways that could affect routing. */ |
123 | amb | 110 | |
124 | amb | 434 | if(difference) |
125 | { | ||
126 | nodesx->super[i]++; | ||
127 | |||
128 | nnodes++; | ||
129 | amb | 110 | } |
130 | |||
131 | if(!((i+1)%10000)) | ||
132 | amb | 519 | printf_middle("Finding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes); |
133 | amb | 110 | } |
134 | |||
135 | amb | 275 | /* Unmap from memory */ |
136 | |||
137 | amb | 452 | #if !SLIM |
138 | amb | 469 | nodesx->xdata=UnmapFile(nodesx->filename); |
139 | amb | 452 | segmentsx->xdata=UnmapFile(segmentsx->filename); |
140 | waysx->xdata=UnmapFile(waysx->filename); | ||
141 | #endif | ||
142 | amb | 275 | |
143 | /* Print the final message */ | ||
144 | |||
145 | amb | 519 | printf_last("Found Super-Nodes: Nodes=%d Super-Nodes=%d",nodesx->number,nnodes); |
146 | amb | 110 | } |
147 | |||
148 | |||
149 | /*++++++++++++++++++++++++++++++++++++++ | ||
150 | Create the super-segments. | ||
151 | |||
152 | SegmentsX *CreateSuperSegments Creates the super segments. | ||
153 | |||
154 | NodesX *nodesx The nodes. | ||
155 | |||
156 | SegmentsX *segmentsx The segments. | ||
157 | |||
158 | WaysX *waysx The ways. | ||
159 | |||
160 | int iteration The current super-node / super-segment iteration number. | ||
161 | ++++++++++++++++++++++++++++++++++++++*/ | ||
162 | |||
163 | SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration) | ||
164 | { | ||
165 | amb | 214 | index_t i; |
166 | amb | 110 | SegmentsX *supersegmentsx; |
167 | amb | 227 | int sn=0,ss=0; |
168 | amb | 110 | |
169 | amb | 508 | supersegmentsx=NewSegmentList(0); |
170 | |||
171 | amb | 510 | if(segmentsx->number==0 || waysx->number==0) |
172 | amb | 508 | return(supersegmentsx); |
173 | |||
174 | amb | 275 | /* Print the start message */ |
175 | |||
176 | amb | 519 | printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0"); |
177 | amb | 227 | |
178 | amb | 275 | /* Map into memory */ |
179 | |||
180 | amb | 452 | #if !SLIM |
181 | segmentsx->xdata=MapFile(segmentsx->filename); | ||
182 | waysx->xdata=MapFile(waysx->filename); | ||
183 | #endif | ||
184 | amb | 257 | |
185 | amb | 275 | /* Create super-segments for each super-node. */ |
186 | |||
187 | amb | 110 | for(i=0;i<nodesx->number;i++) |
188 | { | ||
189 | amb | 249 | if(nodesx->super[i]>iteration) |
190 | amb | 110 | { |
191 | amb | 275 | index_t index,first; |
192 | amb | 110 | |
193 | amb | 544 | index=first=IndexFirstSegmentX2(segmentsx,i); |
194 | amb | 110 | |
195 | amb | 275 | while(index!=NO_SEGMENT) |
196 | amb | 110 | { |
197 | amb | 275 | SegmentX *segmentx=LookupSegmentX(segmentsx,index,1); |
198 | amb | 279 | WayX *wayx=LookupWayX(waysx,segmentx->way,1); |
199 | amb | 110 | |
200 | /* Check that this type of way hasn't already been routed */ | ||
201 | |||
202 | amb | 256 | if(index!=first) |
203 | amb | 110 | { |
204 | amb | 275 | index_t otherindex=first; |
205 | amb | 110 | |
206 | amb | 275 | while(otherindex!=NO_SEGMENT && otherindex!=index) |
207 | amb | 110 | { |
208 | amb | 275 | SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2); |
209 | amb | 279 | WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2); |
210 | amb | 110 | |
211 | amb | 262 | if(!WaysCompare(&otherwayx->way,&wayx->way)) |
212 | amb | 110 | { |
213 | amb | 204 | wayx=NULL; |
214 | amb | 110 | break; |
215 | } | ||
216 | |||
217 | amb | 544 | otherindex=IndexNextSegmentX2(segmentsx,otherindex,i); |
218 | amb | 110 | } |
219 | } | ||
220 | |||
221 | /* Route the way and store the super-segments. */ | ||
222 | |||
223 | amb | 204 | if(wayx) |
224 | amb | 110 | { |
225 | amb | 279 | Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration); |
226 | amb | 110 | Result *result=FirstResult(results); |
227 | |||
228 | while(result) | ||
229 | { | ||
230 | amb | 279 | if(result->node!=i && nodesx->super[result->node]>iteration) |
231 | amb | 110 | { |
232 | amb | 262 | if(wayx->way.type&Way_OneWay) |
233 | amb | 277 | { |
234 | amb | 279 | AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2); |
235 | AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)|ONEWAY_2TO1); | ||
236 | amb | 277 | } |
237 | amb | 172 | else |
238 | amb | 279 | AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)); |
239 | amb | 216 | |
240 | amb | 229 | ss++; |
241 | amb | 110 | } |
242 | |||
243 | result=NextResult(results,result); | ||
244 | } | ||
245 | |||
246 | FreeResultsList(results); | ||
247 | } | ||
248 | |||
249 | amb | 544 | index=IndexNextSegmentX2(segmentsx,index,i); |
250 | amb | 110 | } |
251 | amb | 227 | |
252 | sn++; | ||
253 | amb | 110 | |
254 | amb | 229 | if(!(sn%10000)) |
255 | amb | 519 | printf_middle("Creating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss); |
256 | amb | 110 | } |
257 | } | ||
258 | |||
259 | amb | 275 | /* Unmap from memory */ |
260 | |||
261 | amb | 452 | #if !SLIM |
262 | segmentsx->xdata=UnmapFile(segmentsx->filename); | ||
263 | waysx->xdata=UnmapFile(waysx->filename); | ||
264 | #endif | ||
265 | amb | 275 | |
266 | /* Print the final message */ | ||
267 | |||
268 | amb | 519 | printf_last("Created Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss); |
269 | amb | 110 | |
270 | return(supersegmentsx); | ||
271 | } | ||
272 | |||
273 | |||
274 | /*++++++++++++++++++++++++++++++++++++++ | ||
275 | amb | 256 | Merge the segments and super-segments into a new segment list. |
276 | amb | 110 | |
277 | amb | 256 | SegmentsX* MergeSuperSegments Returns a new set of merged segments. |
278 | |||
279 | amb | 110 | SegmentsX* segmentsx The set of segments to process. |
280 | |||
281 | SegmentsX* supersegmentsx The set of super-segments to merge. | ||
282 | ++++++++++++++++++++++++++++++++++++++*/ | ||
283 | |||
284 | amb | 256 | SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx) |
285 | amb | 110 | { |
286 | amb | 216 | index_t i,j; |
287 | int m=0,a=0; | ||
288 | amb | 256 | SegmentsX* mergedsegmentsx; |
289 | amb | 110 | |
290 | amb | 508 | mergedsegmentsx=NewSegmentList(0); |
291 | |||
292 | amb | 510 | if(segmentsx->number==0 || supersegmentsx->number==0) |
293 | amb | 508 | return(mergedsegmentsx); |
294 | |||
295 | amb | 275 | /* Print the start message */ |
296 | |||
297 | amb | 519 | printf_first("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0"); |
298 | amb | 227 | |
299 | amb | 275 | /* Map into memory */ |
300 | |||
301 | amb | 452 | #if !SLIM |
302 | segmentsx->xdata=MapFile(segmentsx->filename); | ||
303 | supersegmentsx->xdata=MapFile(supersegmentsx->filename); | ||
304 | #endif | ||
305 | amb | 275 | |
306 | /* Loop through and create a new list of combined segments */ | ||
307 | |||
308 | amb | 216 | for(i=0,j=0;i<segmentsx->number;i++) |
309 | amb | 110 | { |
310 | amb | 256 | int super=0; |
311 | amb | 275 | SegmentX *segmentx=LookupSegmentX(segmentsx,i,1); |
312 | amb | 256 | |
313 | amb | 110 | while(j<supersegmentsx->number) |
314 | { | ||
315 | amb | 275 | SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1); |
316 | amb | 256 | |
317 | if(segmentx->node1 ==supersegmentx->node1 && | ||
318 | segmentx->node2 ==supersegmentx->node2 && | ||
319 | segmentx->distance==supersegmentx->distance) | ||
320 | amb | 110 | { |
321 | amb | 257 | m++; |
322 | j++; | ||
323 | amb | 256 | /* mark as super-segment and normal segment */ |
324 | super=1; | ||
325 | amb | 110 | break; |
326 | } | ||
327 | amb | 256 | else if((segmentx->node1==supersegmentx->node1 && |
328 | segmentx->node2==supersegmentx->node2) || | ||
329 | (segmentx->node1==supersegmentx->node1 && | ||
330 | segmentx->node2>supersegmentx->node2) || | ||
331 | (segmentx->node1>supersegmentx->node1)) | ||
332 | amb | 110 | { |
333 | amb | 256 | /* mark as super-segment */ |
334 | AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER); | ||
335 | amb | 216 | a++; |
336 | j++; | ||
337 | amb | 110 | } |
338 | else | ||
339 | amb | 257 | { |
340 | /* mark as normal segment */ | ||
341 | amb | 110 | break; |
342 | amb | 257 | } |
343 | amb | 110 | } |
344 | |||
345 | amb | 256 | if(super) |
346 | AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL); | ||
347 | else | ||
348 | AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL); | ||
349 | amb | 208 | |
350 | amb | 110 | if(!((i+1)%10000)) |
351 | amb | 519 | printf_middle("Merging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a); |
352 | amb | 110 | } |
353 | |||
354 | amb | 275 | /* Unmap from memory */ |
355 | |||
356 | amb | 452 | #if !SLIM |
357 | segmentsx->xdata=UnmapFile(segmentsx->filename); | ||
358 | supersegmentsx->xdata=UnmapFile(supersegmentsx->filename); | ||
359 | #endif | ||
360 | amb | 275 | |
361 | /* Print the final message */ | ||
362 | |||
363 | amb | 519 | printf_last("Merged: Segments=%d Super-Segments=%d Merged=%d Added=%d",segmentsx->number,supersegmentsx->number,m,a); |
364 | amb | 256 | |
365 | return(mergedsegmentsx); | ||
366 | amb | 110 | } |
367 | |||
368 | |||
369 | /*++++++++++++++++++++++++++++++++++++++ | ||
370 | Find all routes from a specified node to any node in the specified list that follows a certain type of way. | ||
371 | |||
372 | Results *FindRoutesWay Returns a set of results. | ||
373 | |||
374 | NodesX *nodesx The set of nodes to use. | ||
375 | |||
376 | SegmentsX *segmentsx The set of segments to use. | ||
377 | |||
378 | WaysX *waysx The set of ways to use. | ||
379 | |||
380 | node_t start The start node. | ||
381 | |||
382 | amb | 203 | Way *match The way that the route must match. |
383 | amb | 110 | |
384 | int iteration The current super-node / super-segment iteration number. | ||
385 | ++++++++++++++++++++++++++++++++++++++*/ | ||
386 | |||
387 | amb | 228 | static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration) |
388 | amb | 110 | { |
389 | Results *results; | ||
390 | amb | 236 | Queue *queue; |
391 | amb | 110 | index_t node1,node2; |
392 | Result *result1,*result2; | ||
393 | amb | 275 | index_t index; |
394 | amb | 204 | WayX *wayx; |
395 | amb | 110 | |
396 | /* Insert the first node into the queue */ | ||
397 | |||
398 | results=NewResultsList(8); | ||
399 | |||
400 | amb | 236 | queue=NewQueueList(); |
401 | |||
402 | amb | 110 | result1=InsertResult(results,start); |
403 | |||
404 | amb | 166 | ZeroResult(result1); |
405 | amb | 110 | |
406 | amb | 236 | InsertInQueue(queue,result1); |
407 | amb | 110 | |
408 | /* Loop across all nodes in the queue */ | ||
409 | |||
410 | amb | 236 | while((result1=PopFromQueue(queue))) |
411 | amb | 110 | { |
412 | node1=result1->node; | ||
413 | |||
414 | amb | 544 | index=IndexFirstSegmentX2(segmentsx,node1); |
415 | amb | 110 | |
416 | amb | 275 | while(index!=NO_SEGMENT) |
417 | amb | 110 | { |
418 | amb | 279 | SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */ |
419 | amb | 113 | distance_t cumulative_distance; |
420 | |||
421 | amb | 275 | if(segmentx->distance&ONEWAY_2TO1) |
422 | goto endloop; | ||
423 | amb | 110 | |
424 | amb | 275 | node2=segmentx->node2; |
425 | amb | 110 | |
426 | amb | 113 | if(result1->prev==node2) |
427 | amb | 110 | goto endloop; |
428 | |||
429 | amb | 279 | wayx=LookupWayX(waysx,segmentx->way,2); |
430 | amb | 110 | |
431 | amb | 262 | if(WaysCompare(&wayx->way,match)) |
432 | amb | 110 | goto endloop; |
433 | |||
434 | amb | 256 | cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance); |
435 | amb | 110 | |
436 | result2=FindResult(results,node2); | ||
437 | |||
438 | if(!result2) /* New end node */ | ||
439 | { | ||
440 | result2=InsertResult(results,node2); | ||
441 | amb | 113 | result2->prev=node1; |
442 | amb | 176 | result2->next=NO_NODE; |
443 | amb | 172 | result2->score=cumulative_distance; |
444 | amb | 166 | result2->sortby=cumulative_distance; |
445 | amb | 110 | |
446 | amb | 279 | if(nodesx->super[node2]<=iteration) |
447 | amb | 236 | InsertInQueue(queue,result2); |
448 | amb | 110 | } |
449 | amb | 172 | else if(cumulative_distance<result2->score) |
450 | amb | 110 | { |
451 | amb | 166 | result2->prev=node1; |
452 | amb | 172 | result2->score=cumulative_distance; |
453 | amb | 166 | result2->sortby=cumulative_distance; |
454 | amb | 110 | |
455 | amb | 279 | if(nodesx->super[node2]<=iteration) |
456 | amb | 236 | InsertInQueue(queue,result2); |
457 | amb | 110 | } |
458 | |||
459 | endloop: | ||
460 | |||
461 | amb | 544 | index=IndexNextSegmentX2(segmentsx,index,node1); |
462 | amb | 110 | } |
463 | } | ||
464 | |||
465 | amb | 236 | FreeQueueList(queue); |
466 | |||
467 | amb | 110 | return(results); |
468 | } |
Properties
Name | Value |
---|---|
cvs:description | Super-nodes and super-segments functions. |