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

Greetings, monks, who are so wise in the ways of science.*

I have a HoHoH... that looks something like this: 

$VAR1 = {
          '1' => {
                   '1a' => {}
                 },
          '2' => {
                   '2a' => {
                            '2b' => {}
                           }
                   '2c' => {},
                 }
        };

[download]

I need to walk through this structure and identify one or more elements that meet certain criteria. Once I find the element(s), I need to report not just the element name(s) (e.g., 2a) but also the path(s) to that element (e.g., 2 -> 2a).

I vaguely recall reading about similar problems but I suspect they focused on only traversing the structure - my searches turned up empty. I could brute-force this, but it seems like a module might already exist to do it (perhaps something along the lines of Algorithm::Loops?).

Suggestions and/or snippets are greatly appreciated. Thanks in advance.

Update: Thanks for the responses. jdporter's example gave me a good starting point.

*With proper attribution (and apologies) to Monty Python and the Holy Grail, of course. :-)

Replies are listed 'Best First'.
Re: Recursive traversal of a HoH... and paths
by jdporter (Paladin) on Oct 09, 2006 at 19:31 UTC

    Given that:

    1. All leaf nodes have a value which is an empty hash;
    2. The tree can be arbitrarily deep.
    then the solution can be as simple as: 

    sub walk
{
    my( $v, @path ) = @_;
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $v->{$k}, @path, $k );
        }
    }
    else
    {
        foo( @path );
    }
}

    [download]

    But if the tree is only two levels deep, as in your example, then you don't need a recursive solution.

    We're building the house of the future together.
[reply]
[d/l]

      Yes, the tree can be arbitrarily deep and each leaf terminates with an empty hash ref, so recursion is needed.

      Thanks for the example - it's a great starting point. If I understand it correctly, though, I'll need to change it slightly. Specifically, it looks like foo() is the criteria test, but it appears that only the keys pointing to the terminal leaves will be tested. I need to test all keys in between, too, so I'll pull that out of the else. That also means that the for loop need not be buried in the 'if' block, so I can remove the 'if' conditional. Finally, I need to track the matching paths, so I could use foo() (or similar) to do that.

      Thanks again.

[reply]
[d/l]
[select]

        Well I don't know what you mean by 'test', but if you want to do something on every node - internal as well as leaf - then something like this: 

        sub walk
{
    my( $v, @path ) = @_;
    foo( @path );
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $v->{$k}, @path, $k );
        }
    }
}

        [download]

        If that something might prevent recursion below the current node, then you could have it return a "prune" boolean: 

        sub walk
{
    my( $v, @path ) = @_;
    foo( @path ) or return; # true means recurse
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $v->{$k}, @path, $k );
        }
    }
}

        [download]

        Of course, for an even more general solution, you'd want to be able to pass in the "callback": 

        sub walk
{
    my( $cb, $v, @path ) = @_;
    $cb->( @path ) or return; # true means recurse
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $cb, $v->{$k}, @path, $k );
        }
    }
}

        [download]

        No doubt someone else will propose an iterator-based solution...

        We're building the house of the future together.
[reply]
[d/l]
[select]
Re: Recursive traversal of a HoH... and paths
by jbert (Priest) on Oct 09, 2006 at 19:19 UTC
    I don't know the modern modules that well, but the for do-it-yourself approach, I guess if you want arbitrary depth then a hash walker might look like: 
    use warnings;
use strict;

my $hoh = {
    '1' => {
        '1a' => {}
    },
    '2' => {
        '2a' => {
            '2b' => {}
        },
        '2c' => { X => 1 },
    }
};
# This coderef examines every node to see if it is the
# one we want
my $evaluator = sub {
    my $item = shift;
    return (ref $item
            && ref $item eq 'HASH'
            && exists $item->{X});
};

my $path = walk_hoh($hoh, $evaluator);
print "found: ", join(", ", @$path), "\n";

exit 0;

sub walk_hoh
{
    my $hr = shift;
    my $evaluator = shift;
    my $keypath = shift || [];

    foreach my $key (keys %$hr) {
      my $val = $hr->{$key};
      if ($evaluator->($val)) {
          # We found it here
          return [@$keypath, $key];
      }
      if (ref $val && ref $val eq 'HASH') {
        # To iterate is human, to recurse divine   
        my $found = walk_hoh($val,
                             $evaluator,
                             [@$keypath, $key]);
        return $found if (defined $found)         
      }
    }
    return undef; # Found nothing here
}

    [download]
[reply]
[d/l]
Re: Recursive traversal of a HoH... and paths
by madbombX (Hermit) on Oct 09, 2006 at 19:31 UTC
    If I understand you correctly, have you considered Data::Alias? This would allow you to copy results hash of "pointers" (or paths) to the data itself without altering the original data structure.

    The results hash could look something like this: $results{"$VAR1->{'1'}->{'1a'}"} = "element1"; Your search could push results into that hash. This is way your result and your path are both accessible via the same hash.

    To navigate a HoHoH, just do the following: 

    foreach my $a (keys %hash) {
  foreach my $b (keys %{$hash{$a}}) {
    print "$hash{$a}{$b}\n";
  }
}

    [download]
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom