I am in search of wisdom!

I was wondering if you could explain a couple things for me from your example:

$nodes{$_}{name}||=$_
        for $c,$p;
[download]

-- I'm not use to putting '$_' as a key for a hash. I am also not sure what '||=$_' means/does. Can you explain?

I'm also not sure why you are deleting children...

delete $nodes{$_}
    for @children;
[download]

Sorry for the newbie questions -- I've been dabbling in Perl for years, and I use hashes a lot but my syntax is still on the simple side.

I have another question. Any tips on printing nested hashes? I use Data::Dumper all the time, but I usually just use the default output. What I am looking for is the "full path". For example, in the above example, we have this:

 'name' => 'a',
          'kids' => {
                      'c' => {
                               'name' => 'c',
                               'kids' => {
                                           'e' => {
                                                    'name' => 'e'
                                                  },
                                           'f' => {
                                                    'name' => 'f'
[download]

-- I'd like to print out something like this:

a
a:c
a:c:e
a:c:f
[download]

I usually just print each piece of the hash, which isn't too hard if I created the hash. For example, if I had a hash ref that had name/address information, I'd do something like:

print $hash->{$key}->{'name'} . "\t";
print $hash->{$key}->{'addres'} . "\n";
[download]

But if the hash is created via autovivification (for example, let's say I am constructing a complex node tree from a parent-child list of several thousand nodes) I get stumped on how I'd be able to print the full path of each element in the hash.

Does that make any sense? I am waking up and keeping two little kids from killing each other. ;)

Any tips much appreciated!!

Thanks.

--Bryan

-- I'm not use to putting '$_' as a key for a hash. I am also not sure what '||=$_' means/does. Can you explain

My code uses a for modifier to alias $c and $p to $_ for the duration of the statement. This is done to eliminate duplicated code. The ||= $_ means "or-equal's $_". Its easiest to exlain by just defining ||= properly, which is that $x ||= $y; does exactly the same thing that $x = $x || $y; which in turn is effectively the same as $x=$y if not $x;

I'm also not sure why you are deleting children...

My algorithm is meant to be order insensitive. That is that you should build the same tree regardless of the order that each parent/child tuple is processed. It does this by putting each node in the root tree, and then basically merging the trees together. However every tree that is a child shouldnt be in the root hash at the end of processing. However we dont know if a node is a true root (the tuples may represent a forest of trees) until we have processed the full list.

-- I'd like to print out something like this

Basically you would write a recursive routine that recursively inorder traverse the tree. Such a routine would look something like the following:

sub print_inorder {
   my $node= shift;
   print $node->{name}, "\n";
   print_inorder($_)
      for sort { $a->{name} cmp $b->{name} } 
          values %{ $node->{kids} || {} };
}
[download]

And before you ask... %{ $node->{kids} || {} } is a "trick" to make the code relatively simple yet also able to deal with nodes that have no children (as it dereferences an empty hash if there are no kids defined).

---
$world=~s/war/peace/g

Thanks,

That was very informative. What if I have three points of data.. say, child, parent, node name (ie descriptor)? Something like:

__DATA__
b:a:apples
d:b:fuji apples
<\c>

<p>


The structure would look something like:
<p>
<c>

$VAR1 = {
          'a' => {
                   'name' => 'fruit',
                   'child' => {
                                'b' => {
                                         'name' => 'apples',
                                         'child' => {
                                                      'd' => {
                                                               'name' 
+=> 'fuji apples'
                                                             }
                                                    }
                                       }
                              }
                 }
        };
[download]

Can your current algorithm be modified to work with this?

Hi. I am having problems incorporating your output subroutine. Can you help?

use Data::Dumper;
use strict;
use warnings;

my %nodes;
my @children;

while (<>) {
    chomp;
    my ($c,$p)=split "\t";
    push @children,$c unless $nodes{$c};
    $nodes{$_}{name}||=$_
        for $c,$p;
    $nodes{$p}{kids}{$c}=$nodes{$c};
}
delete $nodes{$_}
for @children;
my @roots=keys %nodes;

#print Dumper($nodes{$_}) for @roots;

print_inorder(%nodes);


sub print_inorder {
    my $node= shift;
    print $node->{name}, "\n";
   print_inorder($_)
       for sort { $a->{name} cmp $b->{name} }
    values %{ $node->{kids} || {} };
}
[download]