#This program read the triplets from file named "data" into
#an array of array.
use strict;
use warnings;
use Data::Dumper;
use Graph;
#use Graph::Subgraph;     ## WKS
my @S;
while (<DATA>) { push @S, [split]; }   ## WKS
print "-----TRIPLETS-------\n";
print Dumper \@S;

#Make a copy of @S
my @trip = map { [@$_] } @S;

# Find the number of vertices
my @L;
for my $i ( 0 .. $#S ) {
    for my $j ( 0 .. $#{ $S[$i] } ) {
        push( @L, $S[$i][$j] );
    }
}
my %seen;
@L = grep { !$seen{$_}++ } @L;
print " ----VERTICES------\n";
print Dumper \@L;

# Now lets generate the G(L)
# In order to generate the G(L) we'll extract first two columns of S into another matrix
my @GL = @S;
splice( @$_, 2, 1 ) foreach @GL;
print "----EDGE LIST TO BUILD G(L)-----\n";
print Dumper \@GL;

#my %h = map { $_->[0] => $_->[1] } @S;
#print Dumper(\%h);

##### CONNECTED COMPONENTS ##########
my $g = Graph->new( undirected => 1 );
my @a;
my @b;
for ( my $p = 0; $p <= 2; $p++ ) {
    $a[$p] = $S[$p][0];
}
for ( my $q = 0; $q <= 2; $q++ ) {
    $b[$q] = $S[$q][1];
}
for ( my $r = 0; $r <= 2; $r++ ) {
    $g->add_edge( $a[$r], $b[$r] );
}
my @subgraphs = $g->connected_components;
my @allgraphs;
my $V = $g->vertices;
print "Number of taxa=$V\n";
my $q = scalar @subgraphs;
print "Number of connected components ", $q, "\n";
print "First connected component: ", @{ $subgraphs[0] }, "\n";
print "First connected component element: ", $subgraphs[0][1], "\n\n";

sub induced {
    my (@z) = @_;
    for my $QT ( \@z ) {

        #print Dumper $QT;
        for my $triplet (@trip) {
            my %Pie;
            undef @Pie{@$QT};
            delete @Pie{@$triplet};
            print "@$triplet\n" if keys(%Pie) <= ( @$QT - @$triplet ); ## WKS
            return (@$triplet);
        }
    }
}
my @C;
my $d;
my $p = $#subgraphs + 1;
for ( $d = $p; $d >= 1; $d-- ) {
    print "component $d = @{ $subgraphs[$d-1] }\n";
    my @qw = induced( @{ $subgraphs[ $d - 1 ] } );  # WKS post 2
    print Dumper @qw;                               # WKS post 3
    print "induced=@qw\n";                          # WKS post 2
}
__DATA__
b c a
a c d
d e b