Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/optimiser.c
ViewVC logotype

Contents of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 33 - (show annotations) (download) (as text)
Sun Jan 11 09:42:26 2009 UTC (16 years, 2 months ago) by amb
File MIME type: text/x-csrc
File size: 19858 byte(s) 
Replace Junction with SuperNode.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.11 2009-01-11 09:42:26 amb Exp $
3
4 Routing optimiser.
5 ******************/ /******************
6 Written by Andrew M. Bishop
7
8 This file Copyright 2008,2009 Andrew M. Bishop
9 It may be distributed under the GNU Public License, version 2, or
10 any higher version. See section COPYING of the GNU Public license
11 for conditions under which this file may be redistributed.
12 ***************************************/
13
14
15 #include <assert.h>
16 #include <string.h>
17 #include <stdlib.h>
18
19 #include "nodes.h"
20 #include "ways.h"
21 #include "segments.h"
22 #include "results.h"
23 #include "functions.h"
24
25
26 #define INCREMENT 1024
27 #define NBINS 256
28
29
30 /*+ A queue results. +*/
31 typedef struct _Queue
32 {
33 uint32_t alloced; /*+ The amount of space allocated for results in the array +*/
34 uint32_t number; /*+ The number of occupied results in the array +*/
35 Result *queue[1024]; /*+ An array of results whose size is not
36 necessarily limited to 1024 (i.e. may
37 overflow the end of this structure). +*/
38 }
39 Queue;
40
41
42 /*+ The queue of nodes. +*/
43 Queue *OSMQueue=NULL;
44
45 /*+ Print the progress? +*/
46 int print_progress=1;
47
48
49 /* Functions */
50
51 static void insert_in_queue(Result *result);
52
53
54 /*++++++++++++++++++++++++++++++++++++++
55 Find the optimum route between two nodes.
56
57 Results *FindRoute Returns a set of results.
58
59 Nodes *nodes The set of nodes to use.
60
61 Segments *segments The set of segments to use.
62
63 node_t start The start node.
64
65 node_t finish The finish node.
66 ++++++++++++++++++++++++++++++++++++++*/
67
68 Results *FindRoute(Nodes *nodes,Segments *segments,node_t start,node_t finish)
69 {
70 Results *results;
71 Node *Start,*Finish;
72 node_t node2;
73 Node *Node1,*Node2;
74 HalfResult shortest1,quickest1;
75 HalfResult shortest2,quickest2;
76 HalfResult shortestfinish,quickestfinish;
77 distance_t totalcrow,crow;
78 Result *result1,*result2;
79 Segment *segment;
80 int nresults=0;
81
82 /* Set up the finish conditions */
83
84 shortestfinish.distance=~0;
85 shortestfinish.duration=~0;
86 quickestfinish.distance=~0;
87 quickestfinish.duration=~0;
88
89 /* Work out the distance as the crow flies */
90
91 Start=FindNode(nodes,start);
92 Finish=FindNode(nodes,finish);
93
94 totalcrow=Distance(Start,Finish);
95
96 /* Insert the first node into the queue */
97
98 results=NewResultsList();
99
100 result1=InsertResult(results,start);
101
102 result1->node=start;
103 result1->Node=Start;
104 result1->shortest.Prev=NULL;
105 result1->shortest.distance=0;
106 result1->shortest.duration=0;
107 result1->quickest.Prev=NULL;
108 result1->quickest.distance=0;
109 result1->quickest.duration=0;
110
111 insert_in_queue(result1);
112
113 /* Loop across all nodes in the queue */
114
115 while(OSMQueue->number>0)
116 {
117 result1=OSMQueue->queue[--OSMQueue->number];
118 Node1=result1->Node;
119 shortest1.distance=result1->shortest.distance;
120 shortest1.duration=result1->shortest.duration;
121 quickest1.distance=result1->quickest.distance;
122 quickest1.duration=result1->quickest.duration;
123
124 segment=FindFirstSegment(segments,Node1->id);
125
126 while(segment)
127 {
128 node2=segment->node2;
129
130 if(segment->distance==(distance_short_t)~0 ||
131 segment->duration==(distance_short_t)~0)
132 goto endloop;
133
134 shortest2.distance=shortest1.distance+segment->distance;
135 shortest2.duration=shortest1.duration+segment->duration;
136 quickest2.distance=quickest1.distance+segment->distance;
137 quickest2.duration=quickest1.duration+segment->duration;
138
139 result2=FindResult(results,node2);
140 if(result2)
141 Node2=result2->Node;
142 else
143 Node2=FindNode(nodes,node2);
144
145 crow=Distance(Node2,Finish);
146
147 if((crow+shortest2.distance)>(km_to_distance(10)+1.4*totalcrow))
148 goto endloop;
149
150 if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration)
151 goto endloop;
152
153 if(!result2) /* New end node */
154 {
155 result2=InsertResult(results,node2);
156 result2->node=node2;
157 result2->Node=Node2;
158 result2->shortest.Prev=Node1;
159 result2->shortest.distance=shortest2.distance;
160 result2->shortest.duration=shortest2.duration;
161 result2->quickest.Prev=Node1;
162 result2->quickest.distance=quickest2.distance;
163 result2->quickest.duration=quickest2.duration;
164
165 nresults++;
166
167 if(node2==finish)
168 {
169 shortestfinish.distance=shortest2.distance;
170 shortestfinish.duration=shortest2.duration;
171 quickestfinish.distance=quickest2.distance;
172 quickestfinish.duration=quickest2.duration;
173 }
174 else
175 insert_in_queue(result2);
176 }
177 else
178 {
179 if(shortest2.distance<result2->shortest.distance ||
180 (shortest2.distance==result2->shortest.distance &&
181 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
182 {
183 result2->shortest.Prev=Node1;
184 result2->shortest.distance=shortest2.distance;
185 result2->shortest.duration=shortest2.duration;
186
187 if(node2==finish)
188 {
189 shortestfinish.distance=shortest2.distance;
190 shortestfinish.duration=shortest2.duration;
191 }
192 else
193 insert_in_queue(result2);
194 }
195
196 if(quickest2.duration<result2->quickest.duration ||
197 (quickest2.duration==result2->quickest.duration &&
198 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
199 {
200 result2->quickest.Prev=Node1;
201 result2->quickest.distance=quickest2.distance;
202 result2->quickest.duration=quickest2.duration;
203
204 if(node2==finish)
205 {
206 quickestfinish.distance=quickest2.distance;
207 quickestfinish.duration=quickest2.duration;
208 }
209 else
210 insert_in_queue(result2);
211 }
212 }
213
214 endloop:
215
216 segment=FindNextSegment(segments,segment);
217 }
218
219 if(print_progress && !(nresults%1000))
220 {
221 printf("\rRouting: End Nodes=%d Queue=%d Journey=%.1fkm,%.0fmin ",nresults,OSMQueue->number,
222 distance_to_km(shortest2.distance),duration_to_minutes(quickest2.duration));
223 fflush(stdout);
224 }
225 }
226
227 if(print_progress)
228 {
229 printf("\rRouted: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",nresults,
230 distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration),
231 distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration));
232 fflush(stdout);
233 }
234
235 /* Reverse the results */
236
237 result2=FindResult(results,finish);
238
239 do
240 {
241 if(result2->shortest.Prev)
242 {
243 node_t node1=result2->shortest.Prev->id;
244
245 result1=FindResult(results,node1);
246
247 result1->shortest.Next=result2->Node;
248
249 result2=result1;
250 }
251 else
252 result2=NULL;
253 }
254 while(result2);
255
256 result2=FindResult(results,finish);
257
258 do
259 {
260 if(result2->quickest.Prev)
261 {
262 node_t node1=result2->quickest.Prev->id;
263
264 result1=FindResult(results,node1);
265
266 result1->quickest.Next=result2->Node;
267
268 result2=result1;
269 }
270 else
271 result2=NULL;
272 }
273 while(result2);
274
275 return(results);
276 }
277
278
279 /*++++++++++++++++++++++++++++++++++++++
280 Print the optimum route between two nodes.
281
282 Results *Results The set of results to print.
283
284 Nodes *nodes The list of nodes.
285
286 Segments *segments The set of segments to use.
287
288 Ways *ways The list of ways.
289
290 node_t start The start node.
291
292 node_t finish The finish node.
293 ++++++++++++++++++++++++++++++++++++++*/
294
295 void PrintRoute(Results *results,Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish)
296 {
297 FILE *file;
298 Result *result;
299
300 /* Print the result for the shortest route */
301
302 file=fopen("shortest.txt","w");
303
304 result=FindResult(results,start);
305
306 do
307 {
308 if(result->shortest.Next)
309 {
310 Segment *segment;
311 Way *way;
312
313 segment=FindFirstSegment(segments,result->Node->id);
314 while(segment->node2!=result->shortest.Next->id)
315 segment=FindNextSegment(segments,segment);
316
317 way=FindWay(ways,segment->way);
318
319 fprintf(file,"%9.5f %9.5f %9d %5.3f %5.2f %3d %s\n",result->Node->latitude,result->Node->longitude,result->node,
320 distance_to_km(segment->distance),duration_to_minutes(segment->duration),
321 (way->limit?way->limit:way->speed),WayName(ways,way));
322
323 result=FindResult(results,result->shortest.Next->id);
324 }
325 else
326 {
327 fprintf(file,"%9.5f %9.5f %9d\n",result->Node->latitude,result->Node->longitude,result->node);
328
329 result=NULL;
330 }
331 }
332 while(result);
333
334 fclose(file);
335
336 /* Print the result for the quickest route */
337
338 file=fopen("quickest.txt","w");
339
340 result=FindResult(results,start);
341
342 do
343 {
344 if(result->quickest.Next)
345 {
346 Segment *segment;
347 Way *way;
348
349 segment=FindFirstSegment(segments,result->Node->id);
350 while(segment->node2!=result->quickest.Next->id)
351 segment=FindNextSegment(segments,segment);
352
353 way=FindWay(ways,segment->way);
354
355 fprintf(file,"%9.5f %9.5f %9d %5.3f %5.2f %3d %s\n",result->Node->latitude,result->Node->longitude,result->node,
356 distance_to_km(segment->distance),duration_to_minutes(segment->duration),
357 (way->limit?way->limit:way->speed),WayName(ways,way));
358
359 result=FindResult(results,result->quickest.Next->id);
360 }
361 else
362 {
363 fprintf(file,"%9.5f %9.5f %9d\n",result->Node->latitude,result->Node->longitude,result->node);
364
365 result=NULL;
366 }
367 }
368 while(result);
369
370 fclose(file);
371 }
372
373
374 /*++++++++++++++++++++++++++++++++++++++
375 Find all routes from a specified node to any node in the specified list.
376
377 Results *FindRoute2 Returns a set of results.
378
379 Nodes *nodes The set of nodes to use.
380
381 Segments *segments The set of segments to use.
382
383 node_t start The start node.
384
385 Nodes *finish The finishing nodes.
386 ++++++++++++++++++++++++++++++++++++++*/
387
388 Results *FindRoutes(Nodes *nodes,Segments *segments,node_t start,Nodes *finish)
389 {
390 Results *results;
391 Node *Start;
392 node_t node2;
393 Node *Node1,*Node2;
394 HalfResult shortest1,quickest1;
395 HalfResult shortest2,quickest2;
396 Result *result1,*result2;
397 Segment *segment;
398 int nresults=0;
399
400 Start=FindNode(nodes,start);
401
402 /* Insert the first node into the queue */
403
404 results=NewResultsList();
405
406 result1=InsertResult(results,start);
407
408 result1->node=start;
409 result1->Node=Start;
410 result1->shortest.Prev=NULL;
411 result1->shortest.Next=NULL;
412 result1->shortest.distance=0;
413 result1->shortest.duration=0;
414 result1->quickest.Prev=NULL;
415 result1->quickest.Next=NULL;
416 result1->quickest.distance=0;
417 result1->quickest.duration=0;
418
419 insert_in_queue(result1);
420
421 /* Loop across all nodes in the queue */
422
423 while(OSMQueue->number>0)
424 {
425 result1=OSMQueue->queue[--OSMQueue->number];
426 Node1=result1->Node;
427 shortest1.distance=result1->shortest.distance;
428 shortest1.duration=result1->shortest.duration;
429 quickest1.distance=result1->quickest.distance;
430 quickest1.duration=result1->quickest.duration;
431
432 segment=FindFirstSegment(segments,Node1->id);
433
434 while(segment)
435 {
436 node2=segment->node2;
437 Node2=FindNode(nodes,node2);
438
439 if(segment->distance==(distance_short_t)~0 ||
440 segment->duration==(distance_short_t)~0)
441 goto endloop;
442
443 shortest2.distance=shortest1.distance+segment->distance;
444 shortest2.duration=shortest1.duration+segment->duration;
445 quickest2.distance=quickest1.distance+segment->distance;
446 quickest2.duration=quickest1.duration+segment->duration;
447
448 result2=FindResult(results,node2);
449
450 if(!result2) /* New end node */
451 {
452 result2=InsertResult(results,node2);
453 result2->node=node2;
454 result2->Node=Node2;
455 result2->shortest.Prev=Node1;
456 result2->shortest.Next=NULL;
457 result2->shortest.distance=shortest2.distance;
458 result2->shortest.duration=shortest2.duration;
459 result2->quickest.Prev=Node1;
460 result2->quickest.Next=NULL;
461 result2->quickest.distance=quickest2.distance;
462 result2->quickest.duration=quickest2.duration;
463
464 nresults++;
465
466 if(!FindNode(finish,node2))
467 insert_in_queue(result2);
468 }
469 else
470 {
471 if(shortest2.distance<result2->shortest.distance ||
472 (shortest2.distance==result2->shortest.distance &&
473 shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
474 {
475 result2->shortest.Prev=Node1;
476 result2->shortest.distance=shortest2.distance;
477 result2->shortest.duration=shortest2.duration;
478
479 if(!FindNode(finish,node2))
480 insert_in_queue(result2);
481 }
482
483 if(quickest2.duration<result2->quickest.duration ||
484 (quickest2.duration==result2->quickest.duration &&
485 quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
486 {
487 result2->quickest.Prev=Node1;
488 result2->quickest.distance=quickest2.distance;
489 result2->quickest.duration=quickest2.duration;
490
491 if(!FindNode(finish,node2))
492 insert_in_queue(result2);
493 }
494 }
495
496 endloop:
497
498 segment=FindNextSegment(segments,segment);
499 }
500 }
501
502 return(results);
503 }
504
505
506 /*++++++++++++++++++++++++++++++++++++++
507 Print the optimum route between two nodes.
508
509 Results *Results The set of results to print.
510
511 Nodes *nodes The list of nodes.
512
513 Segments *segments The set of segments to use.
514
515 Ways *ways The list of ways.
516
517 Nodes *supernodes The list of supernodes.
518
519 Segments *supersegments The list of supersegments.
520
521 node_t start The start node.
522
523 node_t finish The finish node.
524 ++++++++++++++++++++++++++++++++++++++*/
525
526 void PrintRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,Segments *supersegments,node_t start,node_t finish)
527 {
528 Result *result1,*result2,*result3,*result4;
529 Results *combined;
530
531 combined=NewResultsList();
532
533 print_progress=0;
534
535 /* Sort out the shortest */
536
537 result1=FindResult(results,start);
538
539 do
540 {
541 result3=InsertResult(combined,result1->node);
542
543 result3->node=result1->node;
544 result3->Node=result1->Node;
545 result3->shortest=result1->shortest;
546
547 if(result1->shortest.Next)
548 {
549 Results *results2=FindRoute(nodes,segments,result1->node,result1->shortest.Next->id);
550
551 result2=FindResult(results2,result1->node);
552
553 do
554 {
555 if(result2->shortest.Prev && result2->shortest.Prev->id==result3->node)
556 result3->shortest.Next=result2->Node;
557
558 if(result2->shortest.Prev && result2->shortest.Next)
559 {
560 result4=InsertResult(combined,result2->node);
561
562 result4->node=result2->node;
563 result4->Node=result2->Node;
564 result4->shortest=result2->shortest;
565 }
566
567 if(result2->shortest.Next)
568 result2=FindResult(results2,result2->shortest.Next->id);
569 else
570 result2=NULL;
571 }
572 while(result2);
573
574 FreeResultsList(results2);
575
576 result1=FindResult(results,result1->shortest.Next->id);
577 }
578 else
579 result1=NULL;
580 }
581 while(result1);
582
583 /* Sort out the quickest */
584
585 result1=FindResult(results,start);
586
587 do
588 {
589 result3=FindResult(combined,result1->node);
590
591 if(!result3)
592 result3=InsertResult(combined,result1->node);
593
594 result3->node=result1->node;
595 result3->Node=result1->Node;
596 result3->quickest=result1->quickest;
597
598 if(result1->quickest.Next)
599 {
600 Results *results2=FindRoute(nodes,segments,result1->node,result1->quickest.Next->id);
601
602 result2=FindResult(results2,result1->node);
603
604 do
605 {
606 if(result2->quickest.Prev && result2->quickest.Prev->id==result3->node)
607 result3->quickest.Next=result2->Node;
608
609 if(result2->quickest.Prev && result2->quickest.Next)
610 {
611 result4=FindResult(combined,result2->node);
612
613 if(!result4)
614 result4=InsertResult(combined,result2->node);
615
616 result4->node=result2->node;
617 result4->Node=result2->Node;
618 result4->quickest=result2->quickest;
619 }
620
621 if(result2->quickest.Next)
622 result2=FindResult(results2,result2->quickest.Next->id);
623 else
624 result2=NULL;
625 }
626 while(result2);
627
628 FreeResultsList(results2);
629
630 result1=FindResult(results,result1->quickest.Next->id);
631 }
632 else
633 result1=NULL;
634 }
635 while(result1);
636
637 /* Now print out the result normally */
638
639 print_progress=1;
640
641 PrintRoute(combined,nodes,segments,ways,start,finish);
642 }
643
644
645 /*++++++++++++++++++++++++++++++++++++++
646 Insert an item into the queue in the right order.
647
648 Result *result The result to insert into the queue.
649 ++++++++++++++++++++++++++++++++++++++*/
650
651 static void insert_in_queue(Result *result)
652 {
653 int start;
654 int end;
655 int mid;
656 int insert=-1;
657
658 /* Check that the whole thing is allocated. */
659
660 if(!OSMQueue)
661 {
662 OSMQueue=(Queue*)malloc(sizeof(Queue)-sizeof(OSMQueue->queue)+INCREMENT*sizeof(Result*));
663
664 OSMQueue->alloced=INCREMENT;
665 OSMQueue->number=0;
666 }
667
668 /* Check that the arrays have enough space. */
669
670 if(OSMQueue->number==OSMQueue->alloced)
671 {
672 OSMQueue->alloced+=INCREMENT;
673 OSMQueue=(Queue*)realloc((void*)OSMQueue,sizeof(Queue)-sizeof(OSMQueue->queue)+OSMQueue->alloced*sizeof(Result*));
674 }
675
676 /* Binary search - search key may not match, new insertion point required
677 *
678 * # <- start | Check mid and move start or end if it doesn't match
679 * # |
680 * # | Since there may not be an exact match we must set end=mid
681 * # <- mid | or start=mid because we know that mid doesn't match.
682 * # |
683 * # | Eventually end=start+1 and the insertion point is before
684 * # <- end | end (since it cannot be before the initial start or end).
685 */
686
687 start=0;
688 end=OSMQueue->number-1;
689
690 if(OSMQueue->number==0) /* There is nothing in the queue */
691 insert=start;
692 else if(result->shortest.distance>OSMQueue->queue[start]->shortest.distance) /* Check key is not before start */
693 insert=start;
694 else if(result->shortest.distance<OSMQueue->queue[end]->shortest.distance) /* Check key is not after end */
695 insert=end+1;
696 else
697 {
698 do
699 {
700 mid=(start+end)/2; /* Choose mid point */
701
702 if(OSMQueue->queue[mid]->shortest.distance>result->shortest.distance) /* Mid point is too low */
703 start=mid;
704 else if(OSMQueue->queue[mid]->shortest.distance<result->shortest.distance) /* Mid point is too high */
705 end=mid;
706 else /* Mid point is correct */
707 {
708 if(OSMQueue->queue[mid]==result)
709 return;
710
711 insert=mid;
712 break;
713 }
714 }
715 while((end-start)>1);
716
717 if(insert==-1)
718 insert=end;
719 }
720
721 /* Shuffle the array up */
722
723 if(insert!=OSMQueue->number)
724 memmove(&OSMQueue->queue[insert+1],&OSMQueue->queue[insert],(OSMQueue->number-insert)*sizeof(Result*));
725
726 /* Insert the new entry */
727
728 OSMQueue->queue[insert]=result;
729
730 OSMQueue->number++;
731 }

Properties

Name Value
cvs:description Route optimiser.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root