Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Creating a tree from a parent child list, that also includes node specific properties...

by bryank (Acolyte)
on Jun 29, 2009 at 14:56 UTC ( #775702=perlquestion: print w/replies, xml ) Need Help??

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

Hi Monks,

I want to take a tab-delimited file, and create a tree out of it. This is a continuation on a similar question I had a week or two ago. Anyway, each line in the file contains parent child columns, in addition to properties that pertain to the child. When constructing the tree, I want all properties from a parent to inherit (ie., overide) the children properties (with the exception of node description). For example, if a parent node had a property of hidden, I'd want any children marked as such.

Here's an example -- below I have node ids (parent, child), followed by the title (description) of the child. After that are additional properties of child:

Parent Child Desc Property1 Property2 50 100 Apple hidden non-searchable 100 110 Granny Smith Visible searchable

So in the above example, node id 110, aka 'Granny Smith', would keep its description, but have its other properties overwritten by what was in node 100.

I'd also like a way to indicate if a node was overwritten by its parent. Perhaps as an additional property.

Any tips appreciated.

  • Comment on Creating a tree from a parent child list, that also includes node specific properties...
  • Download Code

Replies are listed 'Best First'.
Re: Creating a tree from a parent child list, that also includes node specific properties...
by Corion (Pope) on Jun 29, 2009 at 15:01 UTC

    As you haven't shown any code, I assume that your problem is with the general approach. I suggest doing it the following way:

    1. Read the file, separate the lines into hashes of property => $value
    2. For each hash, add a property children => []
    3. For each hash, add it to the children list of the hash which has the Child propery the same value as this hashes Parent propery. You might want to create another hash to ease the lookup.

    What do you mean by "indicate if a node was overwritten by its parent"? Please show us an example of where such overwriting happens and what the implications of this are.

      bryank will also need some kind of iterator/traverser if the parents properties are going to be applied to the whole branch (i.e. children who are also parents).

      You could check out Tree::Simple. The docs there also review most of the other tree data structures/parsers/dumpers.

      Just a something something...
        I'm playing around with Tree::Simple, but I fear I don't get it:

        use warnings; use strict; use Tree::Simple; # make a tree root my $tree = Tree::Simple->new("0", Tree::Simple->ROOT); while(<DATA>) { chomp; my ($child, $parent) = split /:/; my $sub_tree = Tree::Simple->new("$parent", $tree); # explicity add a child to it $sub_tree->addChild(Tree::Simple->new("$child")); } $tree->traverse(sub { my ($_tree) = @_; print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n"); }); __DATA__ apple:fruit granny smith:apple fuji:apple orange:fruit blood orange:orange mandarine:orange dwarf fuji:fuji

        Currently, the output looks like this:

        $ perl test.pl fruit apple apple granny smith apple fuji fruit orange orange blood orange orange mandarine fuji dwarf fuji

        I want a format more like the one in the module example:

        1 1.1 2 2.1 2.1a 2.2 3

        I know I am missing some stuff, but I can't grok it. :(

Re: Creating a tree from a parent child list, that also includes node specific properties...
by ikegami (Pope) on Jun 29, 2009 at 15:25 UTC
    use strict; use warnings; use DBI; sub treeify { my ($sth) = @_; my %root = ( _children => [] ); my %children; while (my $row = $sth->fetchrow_hashref()) { my ($id, $parent_id) = @$row{qw( Child Parent )}; my $parent = ( defined($parent_id) ? $children{$parent_id} ||= { _children => [] } : \%root ); my $node = $children{$id} ||= {}; %$node = ( _children => [], %$row ); push @{ $parent->{_children} }, $node; } return \%root; } { my $sponge = DBI->connect( 'dbi:Sponge:', '', '', { RaiseError => 1 } ); my $sth = $sponge->prepare( 'SELECT * FROM Fruit', { NAME => [qw( Parent Child Desc Property1 +Property2 )], rows => [ [ undef, 50, 'Fruit', 'hidden', +'non-searchable' ], [ 50, 100, 'Apple', 'hidden', +'non-searchable' ], [ 100, 110, 'Granny Smith', 'Visible', +'searchable' ], ], } ); my $tree = treeify($sth); use Data::Dumper; print Dumper $tree; }

    Based on Generating a Hash of Hashes Recursively to Display Database Hierarchy. Should use a classes.

Re: Creating a tree from a parent child list, that also includes node specific properties...
by dreadpiratepeter (Priest) on Jun 29, 2009 at 15:01 UTC
    Can you show us what you have tried? This is not a code writing site, but we would be happy to help you debug what you have written.
    It sounds to me like you need to keep a state hash of attributes as you walk the tree you create and add or remove from it as you go down or up levels


    -pete
    "Worry is like a rocking chair. It gives you something to do, but it doesn't get you anywhere."
Re: Creating a tree from a parent child list, that also includes node specific properties... (classy)
by ikegami (Pope) on Jun 29, 2009 at 15:51 UTC
    use strict; use warnings; use DBI qw( ); use Tree::Simple qw( ); { package Fruit; use Data::Dumper qw( Dumper ); sub new { my $class = shift; bless({@_}, $class) } sub dump { my ($self, $prefix) = @_; local $Data::Dumper::Useqq = 1; local $Data::Dumper::Terse = 1; local $Data::Dumper::Indent = 1; local $Data::Dumper::Pad = $prefix; local $Data::Dumper::Sortkeys = sub{[qw( Parent Child Desc Property1 Property2 )]}; return Dumper($self); } } sub treeify { my ($sth) = @_; my $tree = Tree::Simple->new(undef); my %children; while (my $row = $sth->fetchrow_hashref()) { my ($id, $parent_id) = @$row{qw( Child Parent )}; my $parent = ( defined($parent_id) ? $children{$parent_id} ||= Tree::Simple->new(undef) : $tree ); my $node = $children{$id} ||= Tree::Simple->new(); $node->setNodeValue( Fruit->new(%$row) ); $parent->addChild( $node ); } return $tree; } sub dump_tree { my ($tree) = @_; $tree->traverse(sub { my ($node) = @_; my $prefix = "\t" x $node->getDepth(); print( $node->getNodeValue()->dump( $prefix ) ); }); } { my $sponge = DBI->connect( 'dbi:Sponge:', '', '', { RaiseError => 1 } ); my $sth = $sponge->prepare( 'SELECT * FROM Fruit', { NAME => [qw( Parent Child Desc Property1 +Property2 )], rows => [ [ undef, 50, 'Fruit', 'hidden', +'non-searchable' ], [ 50, 100, 'Apple', 'hidden', +'non-searchable' ], [ 100, 110, 'Granny Smith', 'Visible', +'searchable' ], ], } ); my $tree = treeify($sth); dump_tree($tree); }

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2020-11-27 00:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?