http://qs321.pair.com?node_id=771257


in reply to various hash construction/ printing questions..
in thread how to construct tree from parent pointer list

-- 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

Replies are listed 'Best First'.
Re^2: various hash construction/ printing questions..
by bryank (Acolyte) on Jun 13, 2009 at 22:50 UTC
    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?

[reply]
[d/l]

      Of course it can. :-)

      If you play around with it I'm sure you'll figure it out. :-)

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

[reply]
        Hee hee. I did figure it out. Thanks for teaching me to fish, as it were. :)
[reply]
Re^2: various hash construction/ printing questions..
by bryank (Acolyte) on Jun 30, 2009 at 16:28 UTC
    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]
[reply]
[d/l]

In Section Seekers of Perl Wisdom