Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: how to construct tree from parent pointer list

by demerphq (Chancellor)
on Mar 22, 2006 at 17:50 UTC ( #538557=note: print w/replies, xml ) Need Help??


in reply to how to construct tree from parent pointer list

This is an algorithm that IMO every programmer should be familiar with. Its good that you are taking the time to learn.

#perl -e; use Data::Dumper; my %nodes; my @children; while (<DATA>) { chomp; my ($c,$p)=split/:/,$_; 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; __END__ b:a c:a d:b e:c f:c

This version of the algorithm is flexible, it doesnt expect the nodes to be inorder as some of the solutions posted do. It will also identify mixed heirarchies (ie two distinct trees in the same list), and is fairly simple. It has the disadvantage that it must store a list of the nodes which are children until the end of the data input. Here is the output:

$VAR1 = { 'name' => 'a', 'kids' => { 'c' => { 'name' => 'c', 'kids' => { 'e' => { 'name' => 'e' }, 'f' => { 'name' => 'f' } } }, 'b' => { 'name' => 'b', 'kids' => { 'd' => { 'name' => 'd' } } } } };
---
$world=~s/war/peace/g

Replies are listed 'Best First'.
various hash construction/ printing questions..
by bryank (Acolyte) on Jun 13, 2009 at 15:42 UTC
    Hi Perl monks.

    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;

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

    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'

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

    a a:c a:c:e a:c:f

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

    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} || {} }; }

      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' } } } } } };

        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} || {} }; }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://538557]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (4)
As of 2020-11-25 02:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?