+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);
+}
+