+ foreach my $island (sort keys %dbisland2arch) {
+ my $node= $wiisland2node{$island};
+ if (!defined $node) {
+ error("would delete island: $island");
+ next;
+ }
+ my $wiarch= winode2arch($node);
+ if (!defined $wiarch) {
+ error("island has no arch: $island");
+ next;
+ }
+ my $dbarch= $dbisland2arch{$island};
+ if ($wiarch ne $dbarch) {
+ change("change archipelago from $dbarch to $wiarch".
+ " for island $island");
+ }
+ }
+ foreach my $island (sort keys %wiisland2node) {
+ my $dbarch= $dbisland2arch{$island};
+ if (!defined $dbarch) {
+ my $wiarch= wiisland2arch($island);
+ if (!defined $wiarch) {
+ error("new island has no arch: $island");
+ next;
+ # We check arches of non-new islands above
+ }
+ change("new island in $wiarch: $island");
+ }
+ }
+}
+
+sub shortest_path_reduction ($$) {
+ my ($what,$base) = @_;
+ printf DEBUG "spr %s before %d\n", $what, scalar($base->edges());
+
+ my $result= Graph::Undirected->new();
+ foreach my $edge_ac ($base->edges()) {
+ my $edgename_ac= join '..', @$edge_ac;
+ printf DEBUG "spr %s edge %s\n", $what, $edgename_ac;
+ my $w_ac= $base->get_edge_weight(@$edge_ac);
+ my $needed= 1;
+ foreach my $vertex_b ($base->vertices()) {
+ next if grep { $_ eq $vertex_b } @$edge_ac;
+ my $w_ab= $base->get_edge_weight($edge_ac->[0], $vertex_b);
+ next unless defined $w_ab;
+ next if $w_ab >= $w_ac;
+ my $w_bc= $base->get_edge_weight($vertex_b, $edge_ac->[1]);
+ next unless defined $w_ac;
+ next if $w_ab + $w_bc > $w_ac;
+ # found path
+ printf DEBUG "spr %s edge %s unnecessary %s\n",
+ $what, $edgename_ac, $vertex_b;
+ $needed= 0;
+ last;
+ }
+ if ($needed) {
+ printf DEBUG "spr %s edge %s essential\n", $what, $edgename_ac;
+ $result->add_weighted_edge(@$edge_ac,$w_ac);
+ }
+ }
+ printf DEBUG "spr %s result %d\n", $what, scalar($result->edges());
+
+ my $apsp= $result->APSP_Floyd_Warshall();
+ foreach my $ia (sort $base->vertices()) {
+ foreach my $ib (sort $base->vertices()) {
+ my $din= $base->get_edge_weight($ia,$ib);
+ my $dout= $apsp->path_length($ia,$ib);
+ $din= defined($din) ? $din : 'infinity';
+ $dout= defined($dout) ? $dout : 'infinity';
+ error("$what spr apsp discrepancy in=$din out=$dout for $ia..$ib")
+ if $din != $dout;
+ }
+ }
+ return $result;
+}
+
+sub yppedia_graph_spr () {
+ my $base= Graph::Undirected->new();
+ foreach my $na (sort keys %winode2island) {
+ my $ia= $winode2island{$na};
+ foreach my $nb (sort keys %winode2island) {
+ my $ib= $winode2island{$nb};
+ $base->add_weighted_edge($ia,$ib, widist($na,$nb));
+ }
+ }
+ $wispr= shortest_path_reduction('wi',$base);
+}
+
+sub compare_distances () {
+ foreach my $ia (sort keys %dbisland2arch) {
+ my $na= $wiisland2node{$ia};
+ next unless defined $na;
+ foreach my $ib (sort keys %dbisland2arch) {
+ next unless $ia le $ib; # do every pair only once
+ my $dbdist= $dbspr->get_edge_weight($ia,$ib);
+ my $widist= $wispr->get_edge_weight($ia,$ib);
+ next unless defined $dbdist || defined $widist;
+
+ if (!defined $widist) {
+ warning(sprintf "route delete %2d for %s..%s",
+ $dbdist, $ia,$ib);
+ } elsif (!defined $dbdist) {
+ change(sprintf "route create %2d for %s..%s",
+ $widist, $ia,$ib);
+ } elsif ($dbdist != $widist) {
+ change(sprintf "route change %2d to %2d for %s..%s",
+ $dbdist, $widist, $ia,$ib);
+ }
+ }
+ }