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.
Re: Creating a tree from a parent child list, that also includes node specific properties...
by Corion (Patriarch) 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:
- Read the file, separate the lines into hashes of property => $value
- For each hash, add a property children => []
- 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.
| [reply] [d/l] [select] |
|
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...
| [reply] |
|
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. :( | [reply] [d/l] [select] |
Re: Creating a tree from a parent child list, that also includes node specific properties...
by ikegami (Patriarch) 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.
| [reply] [d/l] |
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
|
| [reply] |
Re: Creating a tree from a parent child list, that also includes node specific properties... (classy)
by ikegami (Patriarch) 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);
}
| [reply] [d/l] |
|
|