From 0aebc32d456530967d0ae187e23bcac8b207533a Mon Sep 17 00:00:00 2001
From: Ian Jackson <ian@liberator.relativity.greenend.org.uk>
Date: Thu, 20 Aug 2009 20:08:20 +0100
Subject: [PATCH] Demonstrate bug in Graph::Undirected

---
 yarrg/graph-pm-bug-demo.pl | 277 +++++++++++++++++++++++++++++++++++++
 yarrg/yppedia-chart-parser |   9 +-
 2 files changed, 283 insertions(+), 3 deletions(-)
 create mode 100755 yarrg/graph-pm-bug-demo.pl

diff --git a/yarrg/graph-pm-bug-demo.pl b/yarrg/graph-pm-bug-demo.pl
new file mode 100755
index 0000000..7a10def
--- /dev/null
+++ b/yarrg/graph-pm-bug-demo.pl
@@ -0,0 +1,277 @@
+#!/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);
+}
diff --git a/yarrg/yppedia-chart-parser b/yarrg/yppedia-chart-parser
index 068cd1c..8bcf3c9 100755
--- a/yarrg/yppedia-chart-parser
+++ b/yarrg/yppedia-chart-parser
@@ -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,6 +74,7 @@ sub parse_yppedia_map () {
 	    $winode2island{$n}= $island;
 	    $widists->add_vertex($n);
 	    $wiarchs->add_vertex($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+)\|
@@ -88,6 +89,8 @@ sub parse_yppedia_map () {
 
 	    $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;
 
 	    printf PO "%d,%d league %s %s \n", $x,$y,
 	        $solid?'solid':'dotted', $dirn;
@@ -179,7 +182,7 @@ sub process_yppedia_graphs () {
 	    next;
 	}
 	$wiccix2arch{$ccix}= $arch;
-	print "$ccix $arch ::\n$desc\n";
+#	print "$ccix $arch ::\n$desc\n";
     }
 }
 
-- 
2.30.2