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