- /* 'distances' will hold the final results. */
- create table distances (
- a varchar(40) not null references islands(name),
- b varchar(40) not null references islands(name),
- distance int not null,
- primary key (a,b) );
-
- /* Create a rule such that insertion into the distances table is only
- possible if a shorter route or a new route is being recorded; all other
- inserts are ignored. */
-
- create or replace rule update_only_if_shorter as
- on insert to distances
- where ((new.a,new.b) in (select a,b from distances))
- do instead
- update distances set distance=(case when new.distance<=distance then
- new.distance else distance end)
- where a=new.a and b=new.b;
-
- /* Start by copying manually entered routes into distances */
- insert into distances (select a,b,distance from routes);
- /* Also all the reverse routes */
- insert into distances (select b,a,distance from routes);
- /* Also all the null routes */
- insert into distances (select distinct a,a,0 from routes);
- insert into distances (select distinct b,b,0 from routes);
-
- /* Now extend the distances table by computing new routes */
- insert into distances (select source.a,dest.b,
- min(source.distance+dest.distance)
- from distances source,distances dest
- where source.b=dest.a group by source.a,dest.b);
-
- /* Repeat that query until no new routes are added (i.e. select count(*)
- from distances; returns the same value after the query as it does before) */
+ sub distance_set_propagate ($$$$) {
+ my ($lev, $start, $upto, $start2upto) = @_;
+ $allroutes->{$start}{$upto}= $start2upto;
+ push @propqueue, [ $lev, $start, $upto ];
+ }
+
+ sub distance_propagate_now {
+ my ($lev, $start, $upto) = @_;
+ my $startref= $allroutes->{$start};
+ my $start2upto= $startref->{$upto};
+ my $uptoref= $allroutes->{$upto};
+
+ for my $next (keys %$uptoref) {
+ next if $next eq $upto;
+ my $unext= $uptoref->{$next};
+ next unless defined $unext;
+ distance_update("${lev}p", $start, $next, $start2upto + $unext);
+ }
+ }
+
+ sub distance_update ($$$$) {
+ my ($lev, $x, $y, $newdist) = @_;
+ distance_update_one("${lev}x",$x,$y,$newdist);
+ distance_update_one("${lev}y",$y,$x,$newdist);
+ }
+
+ sub distance_update_one ($$$$) {
+ my ($lev, $x, $y, $newdist) = @_;
+ my $xref= $allroutes->{$x};
+ my $currently= $xref->{$y};
+ return if defined($currently) and $currently <= $newdist;
+ distance_set_propagate("${lev}o",$x,$y,$newdist);
+ }
+
+ foreach my $xn (keys %$allroutes) {
+ my $routes= $allroutes->{$xn};
+ distance_set_propagate('0', $xn, $xn, 0);
+ foreach my $yn (keys %$routes) {
+ distance_set_propagate('0', $yn, $yn, 0);
+ distance_set_propagate('X', $xn, $yn, $routes->{$yn});
+ distance_set_propagate('Y', $yn, $xn, $routes->{$yn});
+ }
+ }
+ my $ref;
+ while ($ref= shift @propqueue) {
+ distance_propagate_now(@$ref);
+ }
+
+ db_doall(<<END)
+ DELETE FROM dists;
+END
+ ;
+ my $sth= $dbh->prepare(<<'END')
+ INSERT INTO dists VALUES
+ ((SELECT islandid FROM islands WHERE islandname == ?),
+ (SELECT islandid FROM islands WHERE islandname == ?),
+ ?);
+END
+ ;
+ foreach my $xn (keys %$allroutes) {
+ my $routes= $allroutes->{$xn};
+ foreach my $yn (keys %$routes) {
+ $sth->execute($xn, $yn, $routes->{$yn});
+ }
+ }
+ $dbh->commit();
+
+ # select ia.islandname, ib.islandname,dists.dist from dists, islands as ia on dists.aiid = ia.islandid, islands as ib on dists.biid = ib.islandid order by ia.islandname, ib.islandname;
+}
+
+__DATA__