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


in reply to how to construct tree from parent pointer list

Getting you started with the previously mentioned Tree module: 

use Tree ();

my %nodes;

while (<>) {
   my ($child, $parent) = split /:/;

   my $parent_node = $nodes{$parent} ||= Tree->new($parent);
   my $child_node  = $nodes{$child}  ||= Tree->new($child);

   $parent_node->add_child($child_node);
}

my @roots = grep { $_->is_root } values %nodes;

die("Invalid data: No roots\n")
   unless @roots;

foreach (@roots) {
   ...
}

[download]
If you are only expecting one root, replace the bottom loop with: 
die("Invalid data: Multiple roots\n")
   if @roots > 1;

my $root = $roots[0];

...

[download]

I didn't check for circular dependancies.

Replies are listed 'Best First'.
Re^2: how to construct tree from parent pointer list
by bryank (Acolyte) on Jun 30, 2009 at 13:30 UTC
    Hi,

    How do you output the tree? I tried using the various Tree methods with the keys of the hash, but without success.

[reply]
      Like any other tree. 
      sub visit_preorder {
   my ($cb, node, $depth) = @_;
   $depth ||= 0;
   $cb->($node, $depth);
   visit_preorder($cb, $_, $depth+1) for $node->children();
}

sub visit_postorder {
   my ($cb, $node, $depth) = @_;
   $depth ||= 0;
   visit_postorder($cb, $_, $depth+1) for $node->children();
   $cb->($node, $depth);
}

visit_preorder(sub {
   my ($node, $depth) = @_;
   ...
}, $root);

      [download]

      It's odd that the module doesn't provide this for you.

      What's wrong with the solutions we've already customised for you?

[reply]
[d/l]
        Thanks. The module does provide an example for output, but I couldn't figure out how to implement it in the example shown here. For example, here is what the module gives:

         my @nodes = $tree->traverse( $tree->PRE_ORDER );

        [download]
        The example I was working off of:

        use Tree (); 
my %nodes; 
while (<>) { 
my ($child, $parent) = split /:/; 

my $parent_node = $nodes{$parent} ||= Tree->new($parent); 
my $child_node = $nodes{$child} ||= Tree->new($child); 
$parent_node->add_child($child_node); 

} 

my @roots = grep { $_->is_root } values %nodes; 

die("Invalid data: Multiple roots\n") if @roots > 1; 
my $root = $roots[0];

        [download]

        Basically, I didn't know what to do since I couldn't find a tree object? I'm sure I am missing all sorts of obvious signs in the code -- I am just too much of a newby to fully understand it. Sorry.

[reply]
[d/l]
[select]
        Hi, Can you explain what the pieces of this does 

        sub visit_preorder {
   my ($cb, node, $depth) = @_;
   $depth ||= 0;
   $cb->($node, $depth);
   visit_preorder($cb, $_, $depth+1) for $node->children();
}

        [download]

        For example, what is '$cb' ? What I am trying to do is output the tree in a flattened format once the tree is built. Something like : Fruit|Apple|Granny Smith.. Fruit being the parent of Apple, Apple being the parent of Granny Smith..

[reply]
[d/l]

In Section Seekers of Perl Wisdom