source: subversion/applications/utils/gary68/routing.pl @ 26424

Last change on this file since 26424 was 18370, checked in by gary68, 10 years ago

routing

  • Property svn:executable set to *
File size: 3.1 KB
Line 
1#
2#
3# Copyright (C) 2009, Gerhard Schwanz
4#
5# This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the
6# Free Software Foundation; either version 3 of the License, or (at your option) any later version.
7#
8# This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
10#
11# You should have received a copy of the GNU General Public License along with this program; if not, see <http://www.gnu.org/licenses/>
12#
13
14use strict ;
15use warnings ;
16
17use OSM::osm 4.0 ;
18
19my $programName = "routing.pl" ;
20my $usage = $programName . " file.rou node1 node2" ; 
21my $version = "1.0" ;
22
23#
24# ENTER INFORMATION IN THIS SECTION
25# ---------------------------------
26#
27
28my $root ;
29my $node1 ;
30my $node2 ;
31
32my $infinity = "inf";
33my %dist ;
34my %edge ;
35my %prev ;
36my @s ;
37my %usedNodes ;
38my @unsolved ;
39
40my $rouName ; 
41
42my $time0 ; my $time1 ;
43
44# get parameter
45
46$rouName = shift||'';
47if (!$rouName)
48{
49        die (print $usage, "\n");
50}
51
52$node1 = shift||'';
53if (!$node1)
54{
55        die (print $usage, "\n");
56}
57
58$node2 = shift||'';
59if (!$node2)
60{
61        die (print $usage, "\n");
62}
63
64
65print "\n$programName $version for file $rouName\n" ;
66
67$time0 = time() ;
68
69
70
71$root = $node1 ;
72
73my $rouFile ;
74my $line ;
75open ($rouFile, "<", $rouName) or die ("can't open input file!") ;
76while ($line = <$rouFile>) {
77
78        my ($n1, $n2, $d) = ($line =~ /^\s*(\d+)\s+(\d+)\s+([\d\.]+)/ ) ;
79        if ((defined $n1) and (defined $n2) and (defined $d)) {
80                # print "$n1, $n2, $d\n" ;
81                $usedNodes{$n1} = 1 ;
82                $usedNodes{$n2} = 1 ;
83                $edge{$n1}{$n2} = $d ;
84        }
85
86}
87close ($rouFile) ;
88
89
90# DIJKSTRA
91print "dijkstra running...\n" ;
92
93# init unsolved nodes array
94foreach my $node (keys %usedNodes) { push @unsolved, $node ; }
95
96# alg
97# all dist = infinity
98foreach my $n (keys %usedNodes) { 
99        $dist{$n} = $infinity ; 
100        $prev{$n}=$n ; 
101}
102
103$dist{$root} = 0;
104
105# loop while we have unsolved nodes
106
107my $finished = 0 ;
108
109while (@unsolved and !$finished) {
110        print scalar (@unsolved), "\n" ;
111        my ($n, $n2) ;
112        @unsolved = sort byDistance @unsolved;
113        push @s, $n = shift @unsolved;
114
115        if ($n == $node2) { $finished = 1 ; }
116
117        foreach $n2 (keys %{$edge{$n}}) {
118                if (($dist{$n2} eq $infinity) ||
119                        ($dist{$n2} > ($dist{$n} + $edge{$n}{$n2}) )) {
120                        $dist{$n2} = $dist{$n} + $edge{$n}{$n2} ;
121                        $prev{$n2} = $n;
122                }
123        }
124}
125
126if ($dist{$node2} ne $infinity) {
127        print "distance to destination = ", $dist{$node2}, "\n" ;
128        print "route to destination\n" ;
129        my $act = $node2 ;
130        while ($prev{$act} != $node1) {
131                print $prev{$act}, " " ;
132                $act = $prev{$act}
133        }
134}
135else {
136        print "DESTINATION UNREACHABLE\n" ;
137}
138
139
140
141$time1 = time() ;
142print "\n$programName finished after ", stringTimeSpent ($time1-$time0), "\n\n" ;
143
144
145
146sub byDistance {
147   $dist{$a} eq $infinity ? +1 :
148   $dist{$b} eq $infinity ? -1 :
149       $dist{$a} <=> $dist{$b};
150}
Note: See TracBrowser for help on using the repository browser.