yarrg/yppedia-chart-parser

   1 #!/usr/bin/perl
   2
   3 use strict (qw(vars));
   4 use warnings;
   5
   6 use Graph::Undirected;
   7 use Commods;
   8 use CommodsDatabase;
   9
  10 my $ocean= 'Midnight';
  11
  12
  13 my $widists= Graph::Undirected->new();
  14 my $wiarchs= Graph::Undirected->new();
  15 my $wispr;
  16 my $dbspr;
  17 my @wiarchlabels;
  18 my %wiisland2node;
  19 my %winode2island;
  20 my %winode2lines;
  21 my %wiccix2arch;
  22 my $wialldists;
  23 my %wtisland2arch;
  24
  25 my $dbdists= Graph::Undirected->new();
  26 my %dbisland2arch;
  27
  28 my %msgs;
  29 sub pmsg ($$) { push @{ $msgs{$_[0]} }, "$_[0]: $_[1]\n"; }
  30 sub warning ($) { pmsg("warning",$_[0]); }
  31 sub error   ($) { pmsg("error",  $_[0]); }
  32 sub change  ($) { pmsg("change", $_[0]); }
  33 sub print_messages () {
  34     foreach my $k (qw(change warning error)) {
  35         my $m= $msgs{$k};
  36         next unless $m;
  37         print sort @$m or die $!;
  38     }
  39 }
  40 sub progress ($) { print "($_[0])\n"; }
  41
  42 if (@ARGV && $ARGV[0] eq '--debug') {
  43     shift @ARGV;
  44     open DEBUG, ">&STDOUT" or die $!;
  45     select(DEBUG); $|=1;
  46 } else {
  47     open DEBUG, ">/dev/null" or die $!;
  48 }
  49 select(STDOUT); $|=1;
  50
  51 my $parity;
  52 sub nn_xy ($$) {
  53     my ($x,$y) = @_;
  54     my $tp= (0+$x ^ 0+$y) & 1;
  55     defined $parity or $parity=$tp;
  56     $tp==$parity or warning("line $.: parity error $x,$y is $tp not $parity");
  57     my $n= "$_[0],$_[1]";
  58     $winode2lines{$n}{$.}++;
  59     return $n;
  60 }
  61
  62 sub yppedia_chart_parse () {
  63     # We don't even bother with tag soup; instead we do line-oriented parsing.
  64
  65     while (<>) {
  66         s/\<--.*--\>//g;
  67         s/^\s*//; chomp; s/\s+$//; s/\s+/ /g;
  68         s/\<\/?(?:b|em)\>//g;
  69         s/\{\{Chart\ style\|[^{}]*\}\}//g;
  70         next unless m/\{\{/; # only interested in chart template stuff
  71
  72         my ($x,$y, $arch,$island,$solid,$dirn);
  73         my $nn= sub { return nn_xy($x,$y) };
  74
  75         if (($x,$y,$arch) =
  76             m/^\{\{ chart\ label \|(\d+)\|(\d+)\| .*
  77                     \'\[\[ [^][\']* \| (\S+)\ archipelago \]\]\'*\}\}$/xi) {
  78             printf DEBUG "%2d,%-2d arch %s\n", $x,$y,$arch;
  79             push @wiarchlabels, [ $x,$y,$arch ];
  80         } elsif (($x,$y,$island) =
  81             m/^\{\{ chart\ island\ icon \|(\d+)\|(\d+)\|
  82                     ([^| ][^|]*[^| ]) \| .*\}\}$/xi) {
  83             my $n= $nn->();
  84             $wiisland2node{$island}= $n;
  85             $winode2island{$n}= $island;
  86             $widists->add_vertex($n);
  87             $wiarchs->add_vertex($n);
  88             printf DEBUG "%2d,%-2d island %s\n", $x,$y,$island;
  89         } elsif (($solid,$x,$y,$dirn) =
  90             m/^\{\{ chart\ league((?:\ solid)?) \|(\d+)\|(\d+)\|
  91                     ([-\/\\o]) \| .*\}\}$/xi) {
  92             next if $dirn eq 'o';
  93
  94             my ($bx,$by) = ($x,$y);
  95             if ($dirn eq '-') { $bx+=2; }
  96             elsif ($dirn eq '\\') { $bx++; $by++; }
  97             elsif ($dirn eq '/') { $x++; $by++; }
  98             else { die; }
  99
 100             my $nb= nn_xy($bx,$by);
 101             $widists->add_weighted_edge($nn->(), $nb, 1);
 102             $wiarchs->add_edge($nn->(), $nb) if $solid;
 103             $wiarchs->add_edge($nn->(), $nb) if $solid;
 104
 105             printf DEBUG "%2d,%-2d league %-6s %s %s\n", $x,$y,
 106                 $solid?'solid':'dotted', $dirn, $nb;
 107         } elsif (
 108             m/^\{\{ chart\ head \}\}$/xi
 109                  ) {
 110             next;
 111         } else {
 112             warning("line $.: ignoring incomprehensible: $_");
 113         }
 114     }
 115 }
 116
 117 sub database_fetch_ocean () {
 118     my ($row,$sth);
 119     $sth= $dbh->prepare('SELECT islandname, archipelago FROM islands');
 120     $sth->execute();
 121     while ($row= $sth->fetchrow_hashref) {
 122         print DEBUG "database-island $row->{'islandname'}".
 123                      " $row->{'archipelago'}\n";
 124         $dbisland2arch{$row->{'islandname'}}= $row->{'archipelago'};
 125     }
 126     $sth= $dbh->prepare('SELECT dist, a.islandname a, b.islandname b
 127                                 FROM dists
 128                                 JOIN islands AS a ON dists.aiid==a.islandid
 129                                 JOIN islands AS b ON dists.biid==b.islandid');
 130     $sth->execute();
 131     while ($row= $sth->fetchrow_hashref) {
 132         $dbdists->add_weighted_edge($row->{'a'}, $row->{'b'}, $row->{'dist'});
 133     }
 134 }
 135
 136 sub database_graph_spr () {
 137     $dbspr= shortest_path_reduction('db',$dbdists);
 138 }
 139
 140 sub yppedia_graphs_add_shortcuts () {
 141     # We add edges between LPs we know about, as you can chart
 142     # between them.  Yppedia often lacks these edges.
 143     #
 144     foreach my $p ($widists->vertices) {
 145         my ($ax,$ay) = $p =~ m/^(\d+)\,(\d+)$/ or die;
 146         my $add_shortcut= sub {
 147             my $q= sprintf "%d,%d", $ax+$_[0], $ay+$_[1];
 148             return unless $widists->has_vertex($q);
 149             return if $widists->has_edge($p,$q);
 150             printf DEBUG "%-5s league-shortcut %-5s\n", $p, $q;
 151             $widists->add_weighted_edge($p,$q,1);
 152         };
 153         $add_shortcut->( 2,0);
 154         $add_shortcut->(+1,1);
 155         $add_shortcut->(-1,1);
 156     }
 157 }
 158
 159 sub yppedia_graphs_prune_boring () {
 160     # Prune the LP database by eliminating boring intermediate vertices
 161     foreach my $delete ($widists->vertices()) {
 162         next if exists $winode2island{$delete};
 163         my @neigh= $widists->neighbours($delete);
 164         next unless @neigh==2;
 165         my $weight= 0;
 166         map { $weight += $widists->get_edge_weight($delete, $_) } @neigh;
 167         $widists->add_weighted_edge(@neigh, $weight);
 168         $widists->delete_vertex($delete);
 169         printf DEBUG "%-5s elide %5s %-5s %2d\n", $delete, @neigh, $weight;
 170     }
 171 }
 172
 173 sub yppedia_graphs_check () {
 174     # Check that it's connected.
 175     foreach my $cc ($widists->connected_components()) {
 176         next if 2*@$cc > $widists->vertices();
 177         my $m= "disconnected league point(s):";
 178         foreach my $n (@$cc) {
 179             $m .= "\n    LP $n, def. yppedia line(s): ".
 180                 join(',', sort keys %{ $winode2lines{$n} });
 181         }
 182         warning($m);
 183     }
 184 }
 185
 186 sub yppedia_archs_sourceinfo () {
 187     # Assign archipelagoes according to the source-info file
 188     foreach my $arch (sort keys %{ $oceans{$ocean} }) {
 189         foreach my $islename (sort keys %{ $oceans{$ocean}{$arch} }) {
 190             my $islenode= $wiisland2node{$islename};
 191             if (!defined $islenode) {
 192                 error("island $islename in source-info but not in WP map");
 193                 next;
 194             }
 195             my $ccix= $wiarchs->connected_component_by_vertex($islenode);
 196             my $oldarch= $wiccix2arch{$ccix};
 197             error("island in $arch in source-info".
 198                   " connected to $oldarch as well: $islename")
 199                 if defined $oldarch && $oldarch ne $arch;
 200             printf DEBUG "%-5s force-island-arch cc%-2d %-10s %s\n",
 201                 $islenode, $ccix, $arch, $islename;
 202             $wiccix2arch{$ccix}= $arch;
 203         }
 204     }
 205 }
 206
 207 sub yppedia_archs_chart_labels () {
 208     # Assign archipelago labels to groups of islands
 209     #
 210     foreach my $label (@wiarchlabels) {
 211         my ($ax,$ay,$arch) = @$label;
 212         my $best_ccmulti= -1;
 213         my $best_d2= 0;
 214         my $best_n;
 215 #       print DEBUG "$ax,$ay arch-island-search $arch\n";
 216         $ay += 1;  $ax += 2;  # coords are rather to the top left of label
 217         foreach my $vertex ($wiarchs->vertices()) {
 218             next unless exists $winode2island{$vertex};
 219             my $ccix= $wiarchs->connected_component_by_vertex($vertex);
 220             my @cc= $wiarchs->connected_component_by_index($ccix);
 221             my $ccmulti= @cc > 1;
 222             my ($vx,$vy) = split /,/, $vertex;
 223             my $d2= ($vx-$ax)*($vx-$ax) + ($vy-$ay)*($vy-$ay);
 224             my $cmp= $ccmulti <=> $best_ccmulti
 225                 ||   $best_d2 <=> $d2;
 226             printf DEBUG "%2d,%-2d arch-island-search %5s d2=%4d cc%-2d".
 227                          " #cc=%2d ccmulti=%d cmp=%2d %s\n",
 228                 $ax,$ay, $vertex, $d2, $ccix, scalar(@cc), $ccmulti, $cmp,
 229                 $winode2island{$vertex};
 230             next unless $cmp > 0;
 231             $best_n=       $vertex;
 232             $best_d2=      $d2;
 233             $best_ccmulti= $ccmulti;
 234         }
 235         die 'no island vertices?!' unless defined $best_n;
 236         my $ccix= $wiarchs->connected_component_by_vertex($best_n);
 237         printf DEBUG
 238             "%2d,%-2d arch-island-select %-5s d2=%4d cc%-2d     %-10s %s\n",
 239             $ax,$ay, $best_n, $ccix, $best_d2, $arch, $winode2island{$best_n};
 240         my $desc= join "\n", map {
 241             my $in= $winode2island{$_};
 242             "    LP $_". (defined $in ? ", $in" : "");
 243         } sort $wiarchs->connected_component_by_index($ccix);
 244
 245         if (exists $wiccix2arch{$ccix} and $wiccix2arch{$ccix} ne $arch) {
 246             error("archipelago determination failed, wrongly merged:\n".
 247                   "    archipelago $arch\n".
 248                   "    archipelago $wiccix2arch{$ccix}\n".
 249                   $desc);
 250             next;
 251         }
 252         $wiccix2arch{$ccix}= $arch;
 253 #       print "$ccix $arch ::\n$desc\n";
 254     }
 255 }
 256
 257 sub yppedia_archs_fillbynearest() {
 258     # Assign islands not labelled above to archipelagoes.
 259     #
 260     # We do this by, for each connected component (set of islands
 261     # linked by purchaseable charts), searching for the nearest other
 262     # connected component which has already been assigned an arch.
 263     # `Nearest' means shortest distance of unpurchaseable charts, in
 264     # leagues.
 265     #
 266     # we need only consider vertices which weren't `boring intermediate
 267     # vertices' (removed during optimisation as being of order 2)
 268     my @ccs_useful= map {
 269         [ grep { $widists->has_vertex($_) } @$_ ]
 270     } $wiarchs->connected_components();
 271
 272     my @assignments;
 273
 274     foreach my $sourceccix (0..$#ccs_useful) {
 275         next if defined $wiccix2arch{$sourceccix};
 276         next unless $ccs_useful[$sourceccix];
 277
 278         my @sourcecc= $wiarchs->connected_component_by_index($sourceccix);
 279         my @islandnodes= grep { $winode2island{$_} } @sourcecc;
 280         next unless @islandnodes; # don't care, then
 281
 282         foreach my $islandnode (@islandnodes) {
 283             printf DEBUG "%-5s arch-join-need cc%-2d             %s\n",
 284                 $islandnode, $sourceccix, $winode2island{$islandnode};
 285         }
 286         my $best_dist= 9999999;
 287         my ($best_target, $best_targetccix, $best_source);
 288         foreach my $targetccix (0..$#ccs_useful) {
 289             next unless defined $wiccix2arch{$targetccix}; # not helpful
 290             next unless $ccs_useful[$targetccix];
 291             foreach my $target ($wiarchs->
 292                          connected_component_by_index($targetccix)) {
 293                 next unless $widists->has_vertex($target);
 294                 foreach my $source (@sourcecc) {
 295                     my $target_dist= widist($target,$source);
 296                     next unless defined $target_dist;
 297                     next if $target_dist >= $best_dist;
 298                     $best_dist= $target_dist;
 299                     $best_source= $source;
 300                     $best_target= $target;
 301                     $best_targetccix= $targetccix;
 302                 }
 303             }
 304         }
 305         die "no possible target ?!" unless defined $best_target;
 306
 307         my $arch= $wiccix2arch{$best_targetccix};
 308         my $best_island= $winode2island{$best_target};
 309         printf DEBUG "%-5s arch-join-to %-5s dist=%2d cc%-2d  %-10s %s\n",
 310             $best_source, $best_target, $best_dist,
 311             $best_targetccix, $arch,
 312             defined($best_island) ? $best_island : "-";
 313
 314         push @assignments, [ $sourceccix, $arch ];
 315     }
 316     foreach my $assign (@assignments) {
 317         $wiccix2arch{$assign->[0]}= $assign->[1];
 318     }
 319 }
 320
 321 sub yppedia_graph_shortest_paths () {
 322     $wialldists= $widists->APSP_Floyd_Warshall();
 323 }
 324
 325 sub widist ($$) {
 326     my ($p,$q) = @_;
 327     my $pl= $wialldists->path_length($p,$q);
 328 #    die "$p $q" unless defined $pl;
 329 #    my @pv= $wialldists->path_vertices($p,$q);
 330 #    if (@pv == $pl) { return $pl; }
 331 #   printf DEBUG "%-5s PATHLENGTH %-5s pl=%s pv=%s\n", $p,$q,$pl,join('|',@pv);
 332     return $pl;
 333 }
 334
 335 sub winode2arch ($) {
 336     my ($node) = @_;
 337     my $ccix= $wiarchs->connected_component_by_vertex($node);
 338     return $wiccix2arch{$ccix};
 339 }
 340 sub wiisland2arch ($) {
 341     my ($island) = @_;
 342     my $node= $wiisland2node{$island};
 343     die "$island ?" unless defined $node;
 344     return winode2arch($node);
 345 }
 346
 347 sub compare_island_lists () {
 348     foreach my $island (sort keys %dbisland2arch) {
 349         my $node= $wiisland2node{$island};
 350         if (!defined $node) {
 351             error("would delete island: $island");
 352             next;
 353         }
 354         my $wiarch= winode2arch($node);
 355         if (!defined $wiarch) {
 356             error("island has no arch: $island");
 357             next;
 358         }
 359         my $dbarch= $dbisland2arch{$island};
 360         if ($wiarch ne $dbarch) {
 361             change("archipelago change from $dbarch to $wiarch".
 362                    " for island $island");
 363         }
 364     }
 365     foreach my $island (sort keys %wiisland2node) {
 366         my $wtarch= $wtisland2arch{$island};
 367         my $wiarch= wiisland2arch($island);
 368         if (!defined $wtarch) {
 369             error("island from chart not found on ocean page: $island");
 370         } elsif (defined $wiarch and $wtarch ne $wiarch) {
 371             error("island in $wtarch on ocean page but".
 372                   " concluded $wiarch from chart: $island");
 373         }
 374
 375         my $dbarch= $dbisland2arch{$island};
 376         if (!defined $dbarch) {
 377             my $wiarch= wiisland2arch($island);
 378             if (!defined $wiarch) {
 379                 error("new island has no arch: $island");
 380                 next;
 381                 # We check arches of non-new islands above
 382             }
 383             change("island new in $wiarch: $island");
 384         }
 385     }
 386     foreach my $island (sort keys %wtisland2arch) {
 387         my $node= $wiisland2node{$island};
 388         next if defined $node;
 389         error("island on ocean page but not in chart: $island");
 390     }
 391 }
 392
 393 sub shortest_path_reduction ($$) {
 394     my ($what,$g) = @_;
 395     #
 396     # Takes a graph $g (and a string for messages $what) and returns
 397     # a new graph which is the miminal shortest path transient reduction
 398     # of $g.
 399     #
 400     # We also check that the shortest path closure of the intended result
 401     # is the same graph as the input.  Thus the input must itself be
 402     # a shortest path closure; if it isn't, we die.
 403
 404     my $proof=<<'END'; # way to make a big comment
 405
 406     Premises and definitions:
 407
 408     1. F is an undirected weighted graph with positive edge weights.
 409
 410     2. All graphs we will consider have the same vertices as F.
 411
 412     3. G = Closure(F) is the graph of cliques whose edge weights
 413        are the shortest paths in F, one clique for each connected
 414        component in F.
 415
 416     3a. |XY| for vertices X, Y is the weight of the edge XY in G.
 417        If XY is not in G, |XY| is infinite.
 418
 419     4. A `reduction' of G is a subgraph K of G such that Closure(K) = G.
 420        The reduction is `minimal' if there is no strict subgraph K'
 421        of K such that Closure(K') = G.
 422
 423     5. Now each edge of G may be:
 424        - `unnecessary': included in no minimal reductions of G.
 425        - `essential': included in all minimal reductions of G.
 426        - `contingent': included in some but not all.
 427
 428     6. Consider for any edge AC between the vertices A and C,
 429        whether there is any B such that |AB|+|BC| = |AC| ?
 430        (There can be no B such that the sum < |AC| since that would
 431        mean that |AC| wasn't equal to the shortest path length.)
 432
 433     6a. No such B:  AC is therefore the only shortest path from A to C
 434         (since G is not a multigraph).  AC is thus an essential edge.
 435
 436     6b. Some such B: Call all such edges AC `questionable'.
 437
 438     6c. Thus all edges are essential or questionable.
 439
 440     7. Suppose AC is a shortest contingent edge.  AC must be
 441        questionable since it is not essential.  Suppose it is
 442        made questionable by the existence of B such that |AB|+|BC| =
 443        |AC|.  Consider AB and BC.  Since |AB| and |BC| are positive,
 444        |BC| and |AB| must be < |AC| ie AB and BC are shorter than AC.
 445        Since AC is a shortest contingent edge, there must be shortest
 446        paths in G for AB and BC consisting entirely of essential edges.
 447
 448     8. Therefore it is always safe to remove AC since the paths
 449        A..B and B..C will definitely still remain and provide a path
 450        A..B..C with length |AB|+|BC| = |AC|.
 451
 452     9. Thus AC is unnecessary, contradicting the assumption in 7.
 453        There are therefore no shortest contingent edges, and
 454        thus no contingent edges.
 455
 456     10. We can construct a minimal reduction directly: for each edge
 457         AC in G, search for a vertex B such that |AB|+|BC| = |AC|.
 458         If we find none, AC is essential.  If we find one then AC is
 459         not essential and is therefore unnecessary.
 460
 461 END
 462
 463     printf DEBUG "spr %s before %d\n", $what, scalar($g->edges());
 464
 465     my $result= Graph::Undirected->new();
 466     foreach my $edge_ac ($g->edges()) {
 467         my $edgename_ac= join ' .. ', @$edge_ac;
 468         printf DEBUG "spr %s edge %s\n", $what, $edgename_ac;
 469         my $w_ac= $g->get_edge_weight(@$edge_ac);
 470         my $needed= 1;
 471         foreach my $vertex_b ($g->vertices()) {
 472             next if grep { $_ eq $vertex_b } @$edge_ac;
 473             my $w_ab= $g->get_edge_weight($edge_ac->[0], $vertex_b);
 474             next unless defined $w_ab;
 475             next if $w_ab >= $w_ac;
 476             my $w_bc= $g->get_edge_weight($vertex_b, $edge_ac->[1]);
 477             next unless defined $w_ac;
 478             next if $w_ab + $w_bc > $w_ac;
 479             # found path
 480             printf DEBUG "spr %s edge %s unnecessary %s\n",
 481                 $what, $edgename_ac, $vertex_b;
 482             $needed= 0;
 483             last;
 484         }
 485         if ($needed) {
 486             printf DEBUG "spr %s edge %s essential\n", $what, $edgename_ac;
 487             $result->add_weighted_edge(@$edge_ac,$w_ac);
 488         }
 489     }
 490     printf DEBUG "spr %s result %d\n", $what, scalar($result->edges());
 491
 492     my $apsp= $result->APSP_Floyd_Warshall();
 493     foreach my $ia (sort $g->vertices()) {
 494         foreach my $ib (sort $g->vertices()) {
 495             my $din= $g->get_edge_weight($ia,$ib);
 496             my $dout= $apsp->path_length($ia,$ib);
 497             $din= defined($din) ? $din : 'infinity';
 498             $dout= defined($dout) ? $dout : 'infinity';
 499             error("$what spr apsp discrepancy in=$din out=$dout".
 500                   " for $ia .. $ib")
 501                 if $din != $dout;
 502         }
 503     }
 504     return $result;
 505 }
 506
 507 sub yppedia_graph_spr () {
 508     my $base= Graph::Undirected->new();
 509     foreach my $na (sort keys %winode2island) {
 510         my $ia= $winode2island{$na};
 511         foreach my $nb (sort keys %winode2island) {
 512             my $ib= $winode2island{$nb};
 513             $base->add_weighted_edge($ia,$ib, widist($na,$nb));
 514         }
 515     }
 516     $wispr= shortest_path_reduction('wi',$base);
 517 }
 518
 519 sub yppedia_ocean_fetch () {
 520     open OCEAN, '-|', "./yppedia-ocean-scraper", $ocean or die $!;
 521     my $arch;
 522     while (<OCEAN>) {
 523         chomp;
 524         if (m/^ocean /) {
 525             $' eq $ocean or die;
 526         } elsif (m/^  /) {
 527             die unless defined $arch;
 528             $wtisland2arch{$'}= $arch;
 529         } elsif (m/^ /) {
 530             $arch= $';
 531         } else {
 532             die;
 533         }
 534     }
 535     $?=0; $!=0; close OCEAN; $? and die $?; $! and die $!;
 536 }
 537
 538 sub compare_distances () {
 539     foreach my $ia (sort keys %dbisland2arch) {
 540         my $na= $wiisland2node{$ia};
 541         next unless defined $na;
 542         foreach my $ib (sort keys %dbisland2arch) {
 543             next unless $ia le $ib; # do every pair only once
 544             my $dbdist= $dbspr->get_edge_weight($ia,$ib);
 545             my $widist= $wispr->get_edge_weight($ia,$ib);
 546             next unless defined $dbdist || defined $widist;
 547
 548             if (!defined $widist) {
 549                 warning(sprintf "route delete %2d for %s .. %s",
 550                         $dbdist, $ia,$ib);
 551             } elsif (!defined $dbdist) {
 552                 change(sprintf "route new %2d for %s .. %s",
 553                        $widist, $ia,$ib);
 554             } elsif ($dbdist != $widist) {
 555                 change(sprintf "route change %2d to %2d for %s .. %s",
 556                        $dbdist, $widist, $ia,$ib);
 557             }
 558         }
 559     }
 560 }
 561
 562 parse_info_serverside();
 563
 564 progress("reading database");
 565
 566 db_setocean($ocean);
 567 db_connect();
 568 database_fetch_ocean();
 569
 570 progress("computing database spr");         database_graph_spr();
 571
 572 progress("reading yppedia chart");          yppedia_chart_parse();
 573 progress("adding shortcuts");               yppedia_graphs_add_shortcuts();
 574 progress("pruning boring vertices");        yppedia_graphs_prune_boring();
 575 progress("checking yppedia graphs");        yppedia_graphs_check();
 576 progress("setting archs from source-info"); yppedia_archs_sourceinfo();
 577 progress("computing shortest paths");       yppedia_graph_shortest_paths();
 578 progress("setting archs from labels");      yppedia_archs_chart_labels();
 579 progress("setting archs from nearby");      yppedia_archs_fillbynearest();
 580 progress("computing yppedia spr");          yppedia_graph_spr();
 581
 582 progress("fetching yppedia ocean text");    yppedia_ocean_fetch();
 583
 584 progress("comparing islands");              compare_island_lists();
 585 progress("comparing distances");            compare_distances();
 586
 587 print_messages();