AWallBuilder has asked for the wisdom of the Perl Monks concerning the following question:

I am trying to write a script to find the lowest common ancestor for a list of ids

I have a file with the parent of each id, and have parsed this into a Hash containing the parent of every id %HoPar. This code not shown, but working properly

Then I am making an array of ancestors for each id. Then in a final step I am comparing all of these ancestor arrays to find the intersection. This is where I am having problems, I'm not sure of the syntax to create the List::Compare object. Any help appreciated

my %HoAncestors; foreach my $qu (keys %HoTxHits) { # go through each taxid, get ancestors, then find the intersec +tion foreach my $taxid (@{$HoTxHits{$qu}}){ my $queryTaxid=$taxid; while ((exists $HoPar{$queryTaxid}) && ($HoPar{$queryT +axid} != 1)) { my $parent=$HoPar{$queryTaxid}; push (@{$HoAncestors{$taxid}},$parent); $queryTaxid=$parent; } } $lcm=List::Compare=>new(\ @intersection=$lcm->get_intersection; } }

Replies are listed 'Best First'.
Re: Passing List::Compare a list of arrays
by hdb (Monsignor) on Jul 12, 2013 at 09:33 UTC

    I do not know what your code is trying to achieve but

    $lcm=List::Compare=>new
    looks suspicious. Should it not be
    $lcm=List::Compare->new
Re: Passing List::Compare a list of arrays
by rjt (Curate) on Jul 12, 2013 at 09:34 UTC
            $lcm=List::Compare=>new(\

    List::Compare->new() (note arrow operator, not fat comma) expects a list of ARRAY refs as its arguments. I don't know enough about your algorithm to write the exact code for you, but it looks like, for example, $HoAncestors{$taxid} is just such an ARRAY ref, so just send it straight to List::Compare->new($HoAncestors{$taxid}, ...), filling in the ... with as many other ARRAY refs as you want to include in the same comparison (i.e., the ones you wish to calculate the intersection of).

    use 5.012; use warnings; use List::Compare; my %hash = ( a => [ qw/foo bar baz for/ ], b => [ qw/bar bells are for tough guys/ ], c => [ qw/belly up to the bar for beer/ ], d => [ qw/d is not used for comparison/ ], ); my $lc = List::Compare->new($hash{a}, $hash{b}, $hash{c}); # my $lc = List::Compare->new(@hash{ qw/a b c/ }); # Or with hash slic +e my @intersection = $lc->get_intersection; say "@intersection";

    Output:

    bar for

      thankyou. My problem is that I am incorporating this in a loop so that I do not know how many Hashes of arrays (ie. how many taxids) I will have each time

      here I have tried to illustrate a bit better what I want (although I know its not correct). Or is there some way of pushing or pasting the arrays into a list that I then pass to List::Compare

      my %HoAncestors;my @intersection; foreach my $qu (keys %HoTxHits) { my $array_list;my $numb_taxids; # go through each taxid, get ancestors, then find the intersec +tion foreach my $taxid (@{$HoTxHits{$qu}}){ $numb_taxids=scalar(@{$HoTxHits{$qu}}); my $queryTaxid=$taxid; while ((exists $HoPar{$queryTaxid}) && ($HoPar{$queryT +axid} != 1)) { my $parent=$HoPar{$queryTaxid}; push (@{$HoAncestors{$taxid}},$parent); $queryTaxid=$parent; } } my $lcm=List::Compare->new($HoAncestors{$taxid}[0]..$HoAncesto +rs{$taxid}[$numb_taxids-1]); @intersection=$lcm->get_intersection; }
Re: Passing List::Compare a list of arrays
by tobyink (Canon) on Jul 12, 2013 at 12:35 UTC

    The easiest algorithm to find the common ancestor for @things is:

    use List::MoreUtils qw(all); my ($first, @rest) = @things; my $ancestor = $first; while (defined $ancestor) { last if all { $_->has_ancestor($ancestor) } @rest; $ancestor = $ancestor->get_parent; }

    This assumes that all the things have a get_parent method which returns the thing's parent, or undef if it has no parent; and has_ancestor which returns a boolean indicating if the first thing is descended (whether directly, or by many generations) from the second.

    Obviously I've used OO in the above, but it's easy enough to adapt the algorithm to non-OO code.

    package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
Re: Passing List::Compare a list of arrays
by kcott (Archbishop) on Jul 13, 2013 at 07:35 UTC

    G'day AWallBuilder,

    It would have been useful if you'd supplied some indication of the data you're working with: replies along the lines of "I don't really know what you're doing" tend to bear this out.

    I was having similar problems myself. I also didn't understand your syntax issue: List::Compare seems well documented and, to be honest, two of the (only) five lines in its SYNOPSIS should have got you substantially further than what you've posted.

    Anyway, I hadn't used List::Compare previously so I was curious. Here's what I came up with:

    #!/usr/bin/env perl -l use strict; use warnings; use List::Compare; my %tree_path_for; my %is_known_node; my @nodes; while (<DATA>) { my ($node, $parent) = split; ++$is_known_node{$node}; $tree_path_for{$node} = [$node => $parent eq 'root' ? () : \$tree_path_for{$parent}] +; } for (@ARGV) { if ($is_known_node{$_}) { push @nodes => $_; } else { print "Unknown node: $_"; } } if (! @nodes) { print "No valid nodes to process!"; } else { print "Nodes for this run: @nodes"; if (@nodes == 1) { print "Need at least two nodes to process!"; } else { my @commons = List::Compare::->new( map { [ flatten_nested_AoA($tree_path_for{$_}) ] } @nodes )->get_intersection; if (@commons) { print "Lowest common ancestor: ", $commons[-1]; } else { print "No common ancestor!"; } } } sub flatten_nested_AoA { map { ref $_ ? flatten_nested_AoA($$_) : $_ } @{+shift} } # Example ancestor trees # # _A_ W # / \ | # B __C__ X # / | \ / \ # D E F Y Z # / \ # G H # Data: node parent # __DATA__ G E D C C A A root E C H E Y X F C X W Z X W root B A

    Here's a few sample runs:

    $ pm_find_common_ancestors.pl D E F Nodes for this run: D E F Lowest common ancestor: C
    $ pm_find_common_ancestors.pl X Y N O P Unknown node: N Unknown node: O Unknown node: P Nodes for this run: X Y Lowest common ancestor: X
    pm_find_common_ancestors.pl X N O P Unknown node: N Unknown node: O Unknown node: P Nodes for this run: X Need at least two nodes to process!
    $ pm_find_common_ancestors.pl G H X Y Nodes for this run: G H X Y No common ancestor!
    $ pm_find_common_ancestors.pl N O P Unknown node: N Unknown node: O Unknown node: P No valid nodes to process!

    Maybe you can adapt this to your requirements.

    -- Ken