yarrg/graph-pm-bug-demo.pl

   1 #!/usr/bin/perl
   2 use strict (qw(vars));
   3 use warnings;
   4 use Graph::Undirected;
   5
   6 sub test_with ($) {
   7     my ($g) = @_;
   8     $g->add_vertex('18_1');
   9     $g->add_vertex('25_4');
  10     $g->add_vertex('23_2');
  11     $g->add_vertex('25_4');
  12     $g->add_vertex('22_7');
  13     $g->add_vertex('17_6');
  14     $g->add_vertex('18_11');
  15     $g->add_vertex('27_12');
  16     $g->add_edge('24_3','25_4');
  17     $g->add_edge('23_2','24_3');
  18     $g->add_edge('25_4','24_5');
  19     $g->add_edge('24_5','23_6');
  20     $g->add_edge('23_6','22_7');
  21     $g->add_edge('17_6','19_6');
  22     $g->add_edge('19_6','20_7');
  23     $g->add_edge('20_7','22_7');
  24     $g->add_edge('19_10','18_11');
  25     $g->add_edge('20_9','19_10');
  26     $g->add_edge('21_8','20_9');
  27     $g->add_edge('22_7','21_8');
  28     $g->add_edge('18_11','20_11');
  29     $g->add_edge('20_11','22_11');
  30     $g->add_edge('22_11','24_11');
  31     $g->add_edge('24_11','25_12');
  32     $g->add_edge('25_12','27_12');
  33     $g->add_edge('22_7','23_8');
  34     $g->add_edge('23_8','24_9');
  35     $g->add_edge('24_9','25_10');
  36     $g->add_edge('25_10','26_11');
  37     $g->add_edge('26_11','27_12');
  38     $g->add_edge('27_12','28_13');
  39     $g->add_edge('28_13','29_14');
  40     $g->add_edge('29_14','30_15');
  41     $g->add_edge('30_15','31_16');
  42     $g->add_edge('31_16','32_17');
  43     $g->add_edge('32_17','33_18');
  44     $g->add_vertex('6_23');
  45     $g->add_vertex('1_26');
  46     $g->add_vertex('2_19');
  47     $g->add_vertex('10_25');
  48     $g->add_vertex('7_18');
  49     $g->add_vertex('6_29');
  50     $g->add_vertex('12_21');
  51     $g->add_edge('12_21','11_22');
  52     $g->add_edge('9_22','11_22');
  53     $g->add_edge('9_22','8_23');
  54     $g->add_edge('6_23','8_23');
  55     $g->add_edge('2_25','1_26');
  56     $g->add_edge('3_24','2_25');
  57     $g->add_edge('3_24','5_24');
  58     $g->add_edge('6_23','5_24');
  59     $g->add_edge('5_22','6_23');
  60     $g->add_edge('4_21','5_22');
  61     $g->add_edge('3_20','4_21');
  62     $g->add_edge('2_19','3_20');
  63     $g->add_edge('6_23','7_24');
  64     $g->add_edge('7_24','8_25');
  65     $g->add_edge('8_25','10_25');
  66     $g->add_edge('7_28','6_29');
  67     $g->add_edge('8_27','7_28');
  68     $g->add_edge('9_26','8_27');
  69     $g->add_edge('10_25','9_26');
  70     $g->add_vertex('17_30');
  71     $g->add_vertex('18_35');
  72     $g->add_vertex('23_38');
  73     $g->add_vertex('18_43');
  74     $g->add_vertex('25_44');
  75     $g->add_vertex('27_40');
  76     $g->add_vertex('26_31');
  77     $g->add_edge('17_30','16_31');
  78     $g->add_edge('16_31','17_32');
  79     $g->add_edge('17_32','16_33');
  80     $g->add_edge('16_33','17_34');
  81     $g->add_edge('17_34','18_35');
  82     $g->add_edge('17_30','19_30');
  83     $g->add_edge('19_30','21_30');
  84     $g->add_edge('21_30','23_30');
  85     $g->add_edge('23_30','24_31');
  86     $g->add_edge('24_31','26_31');
  87     $g->add_edge('18_35','19_36');
  88     $g->add_edge('19_36','20_37');
  89     $g->add_edge('20_37','21_38');
  90     $g->add_edge('21_38','23_38');
  91     $g->add_edge('23_38','22_39');
  92     $g->add_edge('22_39','21_40');
  93     $g->add_edge('21_40','20_41');
  94     $g->add_edge('20_41','19_42');
  95     $g->add_edge('19_42','18_43');
  96     $g->add_edge('18_43','20_43');
  97     $g->add_edge('20_43','22_43');
  98     $g->add_edge('22_43','23_44');
  99     $g->add_edge('23_44','25_44');
 100     $g->add_edge('26_43','25_44');
 101     $g->add_edge('27_42','26_43');
 102     $g->add_edge('26_41','27_42');
 103     $g->add_edge('27_40','26_41');
 104     $g->add_edge('23_38','24_39');
 105     $g->add_edge('24_39','25_40');
 106     $g->add_edge('25_40','27_40');
 107     $g->add_edge('24_37','23_38');
 108     $g->add_edge('25_36','24_37');
 109     $g->add_edge('26_35','25_36');
 110     $g->add_edge('25_34','26_35');
 111     $g->add_edge('26_33','25_34');
 112     $g->add_edge('25_32','26_33');
 113     $g->add_edge('26_31','25_32');
 114     $g->add_vertex('33_18');
 115     $g->add_vertex('38_19');
 116     $g->add_vertex('42_21');
 117     $g->add_vertex('38_25');
 118     $g->add_vertex('43_26');
 119     $g->add_vertex('33_26');
 120     $g->add_vertex('37_30');
 121     $g->add_edge('33_26','34_27');
 122     $g->add_edge('34_27','35_28');
 123     $g->add_edge('35_28','36_29');
 124     $g->add_edge('36_29','37_30');
 125     $g->add_edge('33_26','35_26');
 126     $g->add_edge('35_26','37_26');
 127     $g->add_edge('38_25','37_26');
 128     $g->add_edge('32_25','33_26');
 129     $g->add_edge('33_24','32_25');
 130     $g->add_edge('32_23','33_24');
 131     $g->add_edge('33_22','32_23');
 132     $g->add_edge('32_21','33_22');
 133     $g->add_edge('33_20','32_21');
 134     $g->add_edge('32_19','33_20');
 135     $g->add_edge('33_18','32_19');
 136     $g->add_edge('33_18','35_18');
 137     $g->add_edge('35_18','36_19');
 138     $g->add_edge('36_19','38_19');
 139     $g->add_edge('38_19','39_20');
 140     $g->add_edge('39_20','40_21');
 141     $g->add_edge('40_21','42_21');
 142     $g->add_edge('37_24','38_25');
 143     $g->add_edge('36_23','37_24');
 144     $g->add_edge('35_22','36_23');
 145     $g->add_edge('34_21','35_22');
 146     $g->add_edge('33_20','34_21');
 147     $g->add_edge('39_24','38_25');
 148     $g->add_edge('40_23','39_24');
 149     $g->add_edge('41_22','40_23');
 150     $g->add_edge('42_21','41_22');
 151     $g->add_edge('38_29','37_30');
 152     $g->add_edge('39_28','38_29');
 153     $g->add_edge('40_27','39_28');
 154     $g->add_edge('40_27','42_27');
 155     $g->add_edge('43_26','42_27');
 156     $g->add_edge('38_25','40_25');
 157     $g->add_edge('40_25','41_26');
 158     $g->add_edge('41_26','43_26');
 159     $g->add_vertex('49_12');
 160     $g->add_vertex('47_8');
 161     $g->add_vertex('55_14');
 162     $g->add_vertex('44_11');
 163     $g->add_vertex('57_10');
 164     $g->add_vertex('52_9');
 165     $g->add_vertex('59_16');
 166     $g->add_edge('44_11','46_11');
 167     $g->add_edge('46_11','47_12');
 168     $g->add_edge('47_12','49_12');
 169     $g->add_edge('50_11','49_12');
 170     $g->add_edge('51_10','50_11');
 171     $g->add_edge('52_9','51_10');
 172     $g->add_edge('49_12','50_13');
 173     $g->add_edge('50_13','52_13');
 174     $g->add_edge('52_13','53_14');
 175     $g->add_edge('53_14','55_14');
 176     $g->add_vertex('31_52');
 177     $g->add_vertex('31_58');
 178     $g->add_vertex('35_60');
 179     $g->add_vertex('37_58');
 180     $g->add_vertex('38_53');
 181     $g->add_vertex('44_51');
 182     $g->add_vertex('42_55');
 183     $g->add_vertex('43_58');
 184     $g->add_edge('31_52','30_53');
 185     $g->add_edge('30_53','31_54');
 186     $g->add_edge('31_54','30_55');
 187     $g->add_edge('30_55','31_56');
 188     $g->add_edge('31_56','30_57');
 189     $g->add_edge('30_57','31_58');
 190     $g->add_edge('31_58','32_59');
 191     $g->add_edge('32_59','33_60');
 192     $g->add_edge('33_60','35_60');
 193     $g->add_edge('36_59','35_60');
 194     $g->add_edge('37_58','36_59');
 195     $g->add_edge('31_52','33_52');
 196     $g->add_edge('33_52','35_52');
 197     $g->add_edge('35_52','36_53');
 198     $g->add_edge('36_53','38_53');
 199     $g->add_edge('38_57','37_58');
 200     $g->add_edge('37_56','38_57');
 201     $g->add_edge('38_55','37_56');
 202     $g->add_edge('37_54','38_55');
 203     $g->add_edge('38_53','37_54');
 204     $g->add_edge('37_58','39_58');
 205     $g->add_edge('39_58','41_58');
 206     $g->add_edge('41_58','43_58');
 207     $g->add_edge('38_53','40_53');
 208     $g->add_edge('41_52','40_53');
 209     $g->add_edge('41_52','43_52');
 210     $g->add_edge('44_51','43_52');
 211     $g->add_vertex('51_32');
 212     $g->add_vertex('62_33');
 213     $g->add_vertex('57_36');
 214     $g->add_vertex('53_38');
 215     $g->add_vertex('47_42');
 216     $g->add_vertex('48_45');
 217     $g->add_vertex('54_43');
 218     $g->add_vertex('58_45');
 219     $g->add_edge('48_41','47_42');
 220     $g->add_edge('49_40','48_41');
 221     $g->add_edge('50_39','49_40');
 222     $g->add_edge('50_39','52_39');
 223     $g->add_edge('53_38','52_39');
 224     $g->add_edge('54_37','53_38');
 225     $g->add_edge('54_37','56_37');
 226     $g->add_edge('57_36','56_37');
 227     $g->add_edge('52_37','53_38');
 228     $g->add_edge('51_36','52_37');
 229     $g->add_edge('50_35','51_36');
 230     $g->add_edge('51_34','50_35');
 231     $g->add_edge('50_33','51_34');
 232     $g->add_edge('51_32','50_33');
 233     $g->add_edge('51_32','52_33');
 234     $g->add_edge('52_33','53_34');
 235     $g->add_edge('53_34','54_35');
 236     $g->add_edge('54_35','55_36');
 237     $g->add_edge('55_36','57_36');
 238     $g->add_vertex('2_53');
 239     $g->add_vertex('2_57');
 240     $g->add_vertex('3_60');
 241     $g->add_vertex('8_61');
 242     $g->add_vertex('9_58');
 243     $g->add_vertex('7_54');
 244     $g->add_vertex('9_50');
 245     $g->add_vertex('12_53');
 246     $g->add_edge('9_50','10_51');
 247     $g->add_edge('10_51','11_52');
 248     $g->add_edge('11_52','12_53');
 249     $g->add_edge('9_50','8_51');
 250     $g->add_edge('8_51','9_52');
 251     $g->add_edge('9_52','8_53');
 252     $g->add_edge('8_53','7_54');
 253     $g->add_edge('2_53','4_53');
 254     $g->add_edge('4_53','5_54');
 255     $g->add_edge('5_54','7_54');
 256     $g->add_edge('7_54','9_54');
 257     $g->add_edge('9_54','11_54');
 258     $g->add_edge('12_53','11_54');
 259     $g->add_edge('7_54','6_55');
 260     $g->add_edge('6_55','7_56');
 261     $g->add_edge('7_56','8_57');
 262     $g->add_edge('8_57','9_58');
 263
 264     my $v1= '32_17';
 265     my $v2= '33_18';
 266     printf "has_edge=%d ccbv1=%d ccbv2=%d same_conn_comp=%d\n",
 267         $g->has_edge($v1,$v2),
 268         $g->connected_component_by_vertex($v1),
 269         $g->connected_component_by_vertex($v2),
 270         $g->same_connected_components($v1,$v2);
 271 };
 272
 273 foreach my $uf (qw(0 1)) {
 274     print "unionfind $uf ";
 275     my $thisg= Graph::Undirected->new(unionfind => $uf);
 276     test_with($thisg);
 277 }