#This program read the triplets from file named "data" and returns the 
#supertree.  
# ___DATA(triplets)____ 
#b c a 
#a c d 
#d e b 
#### NOTE ::: SuperTree part hasnt been incorporated yet. 
use strict; 
use warnings; 
use Data::Dumper; 
use Graph;  
use Data::Dump qw/ pp /; 
####READ IN THE INPUT DATA ######## 
my @triplets; # Get all the triplets 
 while (<>) { 
        push @triplets, [ split ]; 
    } 
 
#Make a deep copy of @triplets  
my @triplet_deep_copy = map { [@$_] } @triplets; 
 
 
#####AUXILIARY GRAPH   G(L) ####### 
# In order to generate the G(L)  first of all extract first two columns of  @triplets #into another matrix 
my @auxiliary_edges=@triplets; 
splice(@$_, 2, 1) 
foreach @auxiliary_edges; 
print "----EDGE LIST TO BUILD AUXILIARY GRAPH-----\n"; 
print Dumper \@auxiliary_edges; 
 
 
##### CONNECTED COMPONENTS ########## 
my $auxiliary_graph = Graph->new( undirected => 1 ); 
 
my @from; 
my @to; 
for (my $p = 0; $p <= 2; $p++) { 
        $from[$p]=$triplets[$p][0]; 
  } 
 
for (my $q = 0; $q <= 2; $q++) { 
        $to[$q]=$triplets[$q][1]; 
  } 
 
for (my $r = 0; $r <= 2; $r++) { 
     $auxiliary_graph->add_edge($from[$r], $to[$r]); 
 } 
 
my @subgraphs = $auxiliary_graph->connected_components; # Subgraphs 
my $V = $auxiliary_graph->vertices; # Number of taxa 
my $connected_components=scalar @subgraphs; #Get the number of #connected components 
 
###### FINDING THE TRIPLETS WHICH ARE SUBSET(OR INDUCED BY) OF #EACH OF THE CONNECTED COMPONENTS###### 
Main(@auxiliary_edges); 
exit(0); 
sub induced { 
  my $trip = shift; 
  my @matches; 
  for my $QT ( @_ ) { 
         for my $triplet ( @$trip ) { 
                my %seen;        # my %Pie; 
                undef @seen{@$QT}; 
                delete @seen{@$triplet}; 
                if ( keys( %seen ) <= ( @$QT - @$triplet ) ) { 
                     push @matches, $triplet; 
      } 
    } ## end for my $triplet ( @$trip ) 
  } ## end for my $QT ( @_ ) 
  return @matches; 
}## end sub induced 
 
 
sub Main { 
  my $tree = Graph->new( undirected => 1 ); 
  my $dad='u'; 
  $tree->add_vertex($dad); 
  for my $one (@subgraphs) { 
      my @matches = induced( \@triplet_deep_copy, $one ); 
      print "\nTriplet induced by subgraph ", pp( $one => { MATCHES =>\@matches } ), "\n\n"; 
  } 
}

___INPUT(set of triplets)____ 
b c a 
a c d 
d e b

b c 
a c 
d e

 a-c-b  d-e

TreeConstruct(S) 
1. Let L be the set of species appear in S. Build G(L) 
2. Let C1 , C2 , . . . , Cq be the set of connected components in G(L) 
3. If q >1, then 
• For i = 1, 2, . . . , q, let Si be the set of triplets in S labeled by the set 
of leaves in Ci . 
• Let Ti = TreeConstruct(Si ) 
• Let T be a tree formed by connecting all Ti with the same parent node. 
Return T. 
4. If q=1 and C1 contains exactly one leaf, return the leaf; else return fail.

1. Initially we have q=2 (a-c-b & d-e). So introduce an internal vertex (u) and make 
 these connected components child of u.  
u=> a-c-b; 
    d-e;  
2. Select component 1 = a-c-b. Check all lines from INPUT which are a subset of 
 this component1.First line of INPUT i.e. "b c a" is a subset of component1. 
3."b c a" now becomes the INPUT for the program and it is recursed again with 
 this INPUT(Now for input "b c a" the auxiliary graph will be "b-c" & "a",i.e. two  
connected components,thus q=2 ...)

u  => u => d 
        => e 
   => u => a 
        => u => b 
             => c