chiark / gitweb /
Use unionfind=>0 since that works.
authorIan Jackson <ian@liberator.relativity.greenend.org.uk>
Thu, 20 Aug 2009 19:24:05 +0000 (20:24 +0100)
committerIan Jackson <ian@liberator.relativity.greenend.org.uk>
Thu, 20 Aug 2009 19:24:05 +0000 (20:24 +0100)
See https://rt.cpan.org/Public/Bug/Display.html?id=31068
and Debian bug just submitted.

yarrg/graph-pm-bug-demo.pl [deleted file]
yarrg/test-yppedia-chart
yarrg/yppedia-chart-parser

diff --git a/yarrg/graph-pm-bug-demo.pl b/yarrg/graph-pm-bug-demo.pl
deleted file mode 100755 (executable)
index 7a10def..0000000
+++ /dev/null
@@ -1,277 +0,0 @@
-#!/usr/bin/perl
-use strict (qw(vars));
-use warnings;
-use Graph::Undirected;
-
-sub test_with ($) {
-    my ($g) = @_;
-    $g->add_vertex('18_1');
-    $g->add_vertex('25_4');
-    $g->add_vertex('23_2');
-    $g->add_vertex('25_4');
-    $g->add_vertex('22_7');
-    $g->add_vertex('17_6');
-    $g->add_vertex('18_11');
-    $g->add_vertex('27_12');
-    $g->add_edge('24_3','25_4');
-    $g->add_edge('23_2','24_3');
-    $g->add_edge('25_4','24_5');
-    $g->add_edge('24_5','23_6');
-    $g->add_edge('23_6','22_7');
-    $g->add_edge('17_6','19_6');
-    $g->add_edge('19_6','20_7');
-    $g->add_edge('20_7','22_7');
-    $g->add_edge('19_10','18_11');
-    $g->add_edge('20_9','19_10');
-    $g->add_edge('21_8','20_9');
-    $g->add_edge('22_7','21_8');
-    $g->add_edge('18_11','20_11');
-    $g->add_edge('20_11','22_11');
-    $g->add_edge('22_11','24_11');
-    $g->add_edge('24_11','25_12');
-    $g->add_edge('25_12','27_12');
-    $g->add_edge('22_7','23_8');
-    $g->add_edge('23_8','24_9');
-    $g->add_edge('24_9','25_10');
-    $g->add_edge('25_10','26_11');
-    $g->add_edge('26_11','27_12');
-    $g->add_edge('27_12','28_13');
-    $g->add_edge('28_13','29_14');
-    $g->add_edge('29_14','30_15');
-    $g->add_edge('30_15','31_16');
-    $g->add_edge('31_16','32_17');
-    $g->add_edge('32_17','33_18');
-    $g->add_vertex('6_23');
-    $g->add_vertex('1_26');
-    $g->add_vertex('2_19');
-    $g->add_vertex('10_25');
-    $g->add_vertex('7_18');
-    $g->add_vertex('6_29');
-    $g->add_vertex('12_21');
-    $g->add_edge('12_21','11_22');
-    $g->add_edge('9_22','11_22');
-    $g->add_edge('9_22','8_23');
-    $g->add_edge('6_23','8_23');
-    $g->add_edge('2_25','1_26');
-    $g->add_edge('3_24','2_25');
-    $g->add_edge('3_24','5_24');
-    $g->add_edge('6_23','5_24');
-    $g->add_edge('5_22','6_23');
-    $g->add_edge('4_21','5_22');
-    $g->add_edge('3_20','4_21');
-    $g->add_edge('2_19','3_20');
-    $g->add_edge('6_23','7_24');
-    $g->add_edge('7_24','8_25');
-    $g->add_edge('8_25','10_25');
-    $g->add_edge('7_28','6_29');
-    $g->add_edge('8_27','7_28');
-    $g->add_edge('9_26','8_27');
-    $g->add_edge('10_25','9_26');
-    $g->add_vertex('17_30');
-    $g->add_vertex('18_35');
-    $g->add_vertex('23_38');
-    $g->add_vertex('18_43');
-    $g->add_vertex('25_44');
-    $g->add_vertex('27_40');
-    $g->add_vertex('26_31');
-    $g->add_edge('17_30','16_31');
-    $g->add_edge('16_31','17_32');
-    $g->add_edge('17_32','16_33');
-    $g->add_edge('16_33','17_34');
-    $g->add_edge('17_34','18_35');
-    $g->add_edge('17_30','19_30');
-    $g->add_edge('19_30','21_30');
-    $g->add_edge('21_30','23_30');
-    $g->add_edge('23_30','24_31');
-    $g->add_edge('24_31','26_31');
-    $g->add_edge('18_35','19_36');
-    $g->add_edge('19_36','20_37');
-    $g->add_edge('20_37','21_38');
-    $g->add_edge('21_38','23_38');
-    $g->add_edge('23_38','22_39');
-    $g->add_edge('22_39','21_40');
-    $g->add_edge('21_40','20_41');
-    $g->add_edge('20_41','19_42');
-    $g->add_edge('19_42','18_43');
-    $g->add_edge('18_43','20_43');
-    $g->add_edge('20_43','22_43');
-    $g->add_edge('22_43','23_44');
-    $g->add_edge('23_44','25_44');
-    $g->add_edge('26_43','25_44');
-    $g->add_edge('27_42','26_43');
-    $g->add_edge('26_41','27_42');
-    $g->add_edge('27_40','26_41');
-    $g->add_edge('23_38','24_39');
-    $g->add_edge('24_39','25_40');
-    $g->add_edge('25_40','27_40');
-    $g->add_edge('24_37','23_38');
-    $g->add_edge('25_36','24_37');
-    $g->add_edge('26_35','25_36');
-    $g->add_edge('25_34','26_35');
-    $g->add_edge('26_33','25_34');
-    $g->add_edge('25_32','26_33');
-    $g->add_edge('26_31','25_32');
-    $g->add_vertex('33_18');
-    $g->add_vertex('38_19');
-    $g->add_vertex('42_21');
-    $g->add_vertex('38_25');
-    $g->add_vertex('43_26');
-    $g->add_vertex('33_26');
-    $g->add_vertex('37_30');
-    $g->add_edge('33_26','34_27');
-    $g->add_edge('34_27','35_28');
-    $g->add_edge('35_28','36_29');
-    $g->add_edge('36_29','37_30');
-    $g->add_edge('33_26','35_26');
-    $g->add_edge('35_26','37_26');
-    $g->add_edge('38_25','37_26');
-    $g->add_edge('32_25','33_26');
-    $g->add_edge('33_24','32_25');
-    $g->add_edge('32_23','33_24');
-    $g->add_edge('33_22','32_23');
-    $g->add_edge('32_21','33_22');
-    $g->add_edge('33_20','32_21');
-    $g->add_edge('32_19','33_20');
-    $g->add_edge('33_18','32_19');
-    $g->add_edge('33_18','35_18');
-    $g->add_edge('35_18','36_19');
-    $g->add_edge('36_19','38_19');
-    $g->add_edge('38_19','39_20');
-    $g->add_edge('39_20','40_21');
-    $g->add_edge('40_21','42_21');
-    $g->add_edge('37_24','38_25');
-    $g->add_edge('36_23','37_24');
-    $g->add_edge('35_22','36_23');
-    $g->add_edge('34_21','35_22');
-    $g->add_edge('33_20','34_21');
-    $g->add_edge('39_24','38_25');
-    $g->add_edge('40_23','39_24');
-    $g->add_edge('41_22','40_23');
-    $g->add_edge('42_21','41_22');
-    $g->add_edge('38_29','37_30');
-    $g->add_edge('39_28','38_29');
-    $g->add_edge('40_27','39_28');
-    $g->add_edge('40_27','42_27');
-    $g->add_edge('43_26','42_27');
-    $g->add_edge('38_25','40_25');
-    $g->add_edge('40_25','41_26');
-    $g->add_edge('41_26','43_26');
-    $g->add_vertex('49_12');
-    $g->add_vertex('47_8');
-    $g->add_vertex('55_14');
-    $g->add_vertex('44_11');
-    $g->add_vertex('57_10');
-    $g->add_vertex('52_9');
-    $g->add_vertex('59_16');
-    $g->add_edge('44_11','46_11');
-    $g->add_edge('46_11','47_12');
-    $g->add_edge('47_12','49_12');
-    $g->add_edge('50_11','49_12');
-    $g->add_edge('51_10','50_11');
-    $g->add_edge('52_9','51_10');
-    $g->add_edge('49_12','50_13');
-    $g->add_edge('50_13','52_13');
-    $g->add_edge('52_13','53_14');
-    $g->add_edge('53_14','55_14');
-    $g->add_vertex('31_52');
-    $g->add_vertex('31_58');
-    $g->add_vertex('35_60');
-    $g->add_vertex('37_58');
-    $g->add_vertex('38_53');
-    $g->add_vertex('44_51');
-    $g->add_vertex('42_55');
-    $g->add_vertex('43_58');
-    $g->add_edge('31_52','30_53');
-    $g->add_edge('30_53','31_54');
-    $g->add_edge('31_54','30_55');
-    $g->add_edge('30_55','31_56');
-    $g->add_edge('31_56','30_57');
-    $g->add_edge('30_57','31_58');
-    $g->add_edge('31_58','32_59');
-    $g->add_edge('32_59','33_60');
-    $g->add_edge('33_60','35_60');
-    $g->add_edge('36_59','35_60');
-    $g->add_edge('37_58','36_59');
-    $g->add_edge('31_52','33_52');
-    $g->add_edge('33_52','35_52');
-    $g->add_edge('35_52','36_53');
-    $g->add_edge('36_53','38_53');
-    $g->add_edge('38_57','37_58');
-    $g->add_edge('37_56','38_57');
-    $g->add_edge('38_55','37_56');
-    $g->add_edge('37_54','38_55');
-    $g->add_edge('38_53','37_54');
-    $g->add_edge('37_58','39_58');
-    $g->add_edge('39_58','41_58');
-    $g->add_edge('41_58','43_58');
-    $g->add_edge('38_53','40_53');
-    $g->add_edge('41_52','40_53');
-    $g->add_edge('41_52','43_52');
-    $g->add_edge('44_51','43_52');
-    $g->add_vertex('51_32');
-    $g->add_vertex('62_33');
-    $g->add_vertex('57_36');
-    $g->add_vertex('53_38');
-    $g->add_vertex('47_42');
-    $g->add_vertex('48_45');
-    $g->add_vertex('54_43');
-    $g->add_vertex('58_45');
-    $g->add_edge('48_41','47_42');
-    $g->add_edge('49_40','48_41');
-    $g->add_edge('50_39','49_40');
-    $g->add_edge('50_39','52_39');
-    $g->add_edge('53_38','52_39');
-    $g->add_edge('54_37','53_38');
-    $g->add_edge('54_37','56_37');
-    $g->add_edge('57_36','56_37');
-    $g->add_edge('52_37','53_38');
-    $g->add_edge('51_36','52_37');
-    $g->add_edge('50_35','51_36');
-    $g->add_edge('51_34','50_35');
-    $g->add_edge('50_33','51_34');
-    $g->add_edge('51_32','50_33');
-    $g->add_edge('51_32','52_33');
-    $g->add_edge('52_33','53_34');
-    $g->add_edge('53_34','54_35');
-    $g->add_edge('54_35','55_36');
-    $g->add_edge('55_36','57_36');
-    $g->add_vertex('2_53');
-    $g->add_vertex('2_57');
-    $g->add_vertex('3_60');
-    $g->add_vertex('8_61');
-    $g->add_vertex('9_58');
-    $g->add_vertex('7_54');
-    $g->add_vertex('9_50');
-    $g->add_vertex('12_53');
-    $g->add_edge('9_50','10_51');
-    $g->add_edge('10_51','11_52');
-    $g->add_edge('11_52','12_53');
-    $g->add_edge('9_50','8_51');
-    $g->add_edge('8_51','9_52');
-    $g->add_edge('9_52','8_53');
-    $g->add_edge('8_53','7_54');
-    $g->add_edge('2_53','4_53');
-    $g->add_edge('4_53','5_54');
-    $g->add_edge('5_54','7_54');
-    $g->add_edge('7_54','9_54');
-    $g->add_edge('9_54','11_54');
-    $g->add_edge('12_53','11_54');
-    $g->add_edge('7_54','6_55');
-    $g->add_edge('6_55','7_56');
-    $g->add_edge('7_56','8_57');
-    $g->add_edge('8_57','9_58');
-
-    my $v1= '32_17';
-    my $v2= '33_18';
-    printf "has_edge=%d ccbv1=%d ccbv2=%d same_conn_comp=%d\n",
-       $g->has_edge($v1,$v2),
-       $g->connected_component_by_vertex($v1),
-       $g->connected_component_by_vertex($v2),
-       $g->same_connected_components($v1,$v2);
-};
-
-foreach my $uf (qw(0 1)) {
-    print "unionfind $uf ";
-    my $thisg= Graph::Undirected->new(unionfind => $uf);
-    test_with($thisg);
-}
index fa4059c..08c3fbf 100644 (file)
 {{Chart league|28|11|o|gray}}
  <!--Interarches-->
 <!--Jorvik-Turtle-->
-{{Chart league solid|27|12|\|gold}}
-{{Chart league solid|28|13|\|gold}}
-{{Chart league solid|29|14|\|gold}}
-{{Chart league solid|30|15|\|gold}}
-{{Chart league solid|31|16|\|gold}}
-{{Chart league solid|32|17|\|gold}}
+{{Chart league|27|12|\|gold}}
+{{Chart league|28|13|\|gold}}
+{{Chart league|29|14|\|gold}}
+{{Chart league|30|15|\|gold}}
+{{Chart league|31|16|\|gold}}
+{{Chart league|32|17|\|gold}}
 <!--Luthien-Nuptial-->
 {{Chart league|17|11|/|gold}}
 {{Chart league|17|12|\|gold}}
index 8bcf3c9..8b5c508 100755 (executable)
@@ -8,7 +8,7 @@ use Graph::Undirected;
 use CommodsDatabase;
 
 my $widists= Graph::Undirected->new();
-my $wiarchs= Graph::Undirected->new(unionfind => 1);
+my $wiarchs= Graph::Undirected->new();
 my @wiarchlabels;
 my %wiisland2node;
 my %winode2island;
@@ -32,8 +32,8 @@ sub error ($) {
     $errors++;
 }
 
-open PO, ">/dev/null" or die $!;
-#open PO, ">&STDOUT" or die $!;
+#open PO, ">/dev/null" or die $!;
+open PO, ">&STDOUT" or die $!;
 select(PO); $|=1;
 select(STDOUT); $|=1;
 
@@ -74,7 +74,7 @@ sub parse_yppedia_map () {
            $winode2island{$n}= $island;
            $widists->add_vertex($n);
            $wiarchs->add_vertex($n);
-print "\$g->add_vertex('$n');\n";
+#print "\$g->add_vertex('$n');\n";
            printf PO "%d,%d island %s\n", $x,$y,$island;
        } elsif (($solid,$x,$y,$dirn) =
            m/^\{\{ chart\ league((?:\ solid)?) \|(\d+)\|(\d+)\|
@@ -90,7 +90,7 @@ print "\$g->add_vertex('$n');\n";
            $widists->add_weighted_edge($nn->(), nn_xy($bx,$by), 1);
            $wiarchs->add_edge($nn->(), nn_xy($bx,$by)) if $solid;
            $wiarchs->add_edge($nn->(), nn_xy($bx,$by)) if $solid;
-print "\$g->add_edge('".$nn->()."','".nn_xy($bx,$by)."');\n" if $solid;
+#print "\$g->add_edge('".$nn->()."','".nn_xy($bx,$by)."');\n" if $solid;
 
            printf PO "%d,%d league %s %s \n", $x,$y,
                $solid?'solid':'dotted', $dirn;
@@ -175,7 +175,7 @@ sub process_yppedia_graphs () {
        } sort $wiarchs->connected_component_by_index($ccix);
 
        if (exists $wiccix2arch{$ccix}) {
-           error("architecture determination failed:\n".
+           error("archipelago determination failed, wrongly merged:\n".
                  "    archipelago $arch\n".
                  "    archipelago $wiccix2arch{$ccix}\n".
                  $desc);
@@ -198,8 +198,3 @@ parse_yppedia_map();
 parse_database_map();
 process_yppedia_graphs();
 compare_island_lists();
-
-printf "%d %d %d %d\n", $wiarchs->has_edge('32,17','33,18'),
-    $wiarchs->connected_component_by_vertex('32,17'),
-    $wiarchs->connected_component_by_vertex('33,18'),
-    $wiarchs->same_connected_components('32,17','33,18');