|
Re: representing a tree
by dragonchild (Archbishop) on Jul 03, 2008 at 10:00 UTC
|
use Tree;
my @data = (
[ 1,3 ],
[ 1,4 ],
[ 1,5 ],
[ 3,8 ],
[ 3,9 ],
[ 4,11 ],
[ 4,18 ],
[ 8,14 ],
[ 8,15 ],
[ 5,17 ],
[ 5,16 ],
[ 17,21 ],
);
my %nodes;
foreach my $edge ( @data ) {
my ($parent_id, $child_id) = @$edge;
my $parent = $nodes{$parent_id} ||= Tree->new( $parent_id );
my $child = $nodes{$child_id} ||= Tree->new( $child_id );
$parent->add_child( $child );
}
Now, you have a tree. Do what you want with it.
My criteria for good software:
- Does it work?
- Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
| [reply]
[d/l] |
|
|
use strict;
use warnings;
my @data = (
[ 1,3 ],
[ 1,4 ],
[ 1,5 ],
[ 3,8 ],
[ 3,9 ],
[ 4,11 ],
[ 4,18 ],
[ 8,14 ],
[ 8,15 ],
[ 5,17 ],
[ 5,16 ],
[ 17,21 ],
);
use Tree::Simple;
my %nodes;
foreach my $edge ( @data ) {
my ($parent_id, $child_id) = @$edge;
my $parent = $nodes{$parent_id} ||= Tree::Simple->new( $parent_id
+);
my $child = $nodes{$child_id} ||= Tree::Simple->new( $child_id );
$parent->addChild( $child );
}
use Tree::Visualize;
my $visualize = Tree::Visualize->new( $nodes{1}, 'ASCII', 'TopDown' );
print $visualize->draw(), $/, $/;
use Tree::Simple::View::ASCII;
my $tree_view = Tree::Simple::View::ASCII->new( $nodes{1} );
$tree_view->includeTrunk(1);
print $tree_view->expandAll(), $/, $/;
__END__
|
+---+
| 1 |
+---+
________________|___________________
| | |
+---+ +---+ +---+
| 3 | | 4 | | 5 |
+---+ +---+ +---+
___|________ ____|____ ____|____
| | | | | |
+---+ +---+ +----+ +----+ +----+ +----+
| 8 | | 9 | | 11 | | 18 | | 17 | | 16 |
+---+ +---+ +----+ +----+ +----+ +----+
____|____ |
| | |
+----+ +----+ +----+
| 14 | | 15 | | 21 |
+----+ +----+ +----+
1
|---3
| |---8
| | |---14
| | |---15
| |---9
|---4
| |---11
| |---18
|---5
|---17
| |---21
|---16
| [reply]
[d/l] |
Re: representing a tree
by pjotrik (Friar) on Jul 03, 2008 at 09:58 UTC
|
Actually, I felt like writing a little homework today :-) I leave the rest of prettyprinting to you.
use warnings;
use strict;
my (%edges, %processed);
while (<DATA>) {
if (/(\d+),(\d+)/) {
$edges{$1} = [] unless (exists $edges{$1});
push(@{$edges{$1}}, $2);
}
};
close DATA;
for (sort keys %edges) {
print_tree($_) unless exists $processed{$_};
}
sub print_tree {
my ($node, $pp) = @_;
$pp = '' unless defined $pp;
print "$pp$node\n";
$processed{$node} = 1;
return unless exists $edges{$node};
for (@{$edges{$node}}) {
print "$pp$_ - cycle detected\n" if exists $processed{
+$_};
print_tree($_, $pp.' ') unless exists $processed{$_};
}
}
__DATA__
1,3
1,4
1,5
3,8
3,9
4,11
4,18
8,14
8,15
5,17
5,16
17,21
| [reply]
[d/l] |
Re: representing a tree
by Arunbear (Prior) on Jul 03, 2008 at 13:13 UTC
|
This monstrosity builds a hierarchical hash and prints it using YAML:
use strict;
use warnings;
use YAML qw/Dump/;
my %parent_of;
my %tree;
my %ref;
while(<DATA>) {
chomp;
my ($parent, $child) = split /,/;
$parent_of{$child} = $parent;
my $h;
if(exists $parent_of{$parent}) {
$h = $ref{ $parent };
$h->{$child} = {};
$ref{$child} = $h->{$child};
}
else {
$h = \%tree;
$ref{$parent} = $h;
$h->{$parent}{$child} = {};
$ref{$child} = $h->{$parent}{$child};
}
}
print Dump(\%tree) . "\n";
__DATA__
1,3
1,4
1,5
3,8
3,9
4,11
4,18
8,14
8,15
5,17
5,16
17,21
output:
---
1:
3:
8:
14: {}
15: {}
9: {}
4:
11: {}
18: {}
5:
16: {}
17:
21: {}
| [reply]
[d/l]
[select] |
|
|
| [reply] |
Re: representing a tree
by moritz (Cardinal) on Jul 03, 2008 at 09:21 UTC
|
What have you tried so far? Show us some code so we see some effort from you, we can help you if you tell us with which part of the task you have problems with.
If you don't show any effort, it feels like homework, which many of us don't like to answer. | [reply] |
|
|
you're right it does sound's like homework but is has passed quite some time since i last attended any real classes. so what i tried so far is through recursion catch the pattern to transform it to the nice tree :
use strict;
open (T, "<", "file.txt")|| die "$!";
open (OUT, ">", "out.txt") || die "$!";
my $t = $ARGV[0];# $t could be 3 not 1 so that i can start from that p
+oint
my %hash;
while (<T>){
m/^(\d+?),(\d+?)\n/g;
my ($child, $parent) = ($2,$1);
push @{$hash{$child}},$parent;
}
walk($t);
sub walk {
my $numb = shift;
print OUT "\|->$numb\n";
#my @walk = $numb;
for (@{$hash{$numb}}){
#push @walk,
#print OUTNOD "\|->>>";
walk($_);
print OUTNOD "\|->>";
}
#return @walk;
}
there are some relict's in the code but that is because i'm still trying to figure it out. | [reply]
[d/l] |
|
|
push @{$hash{$child}},$parent;
That doesn't look right. Usually you store a tree the other way round, i.e. for each node you store a list of child nodes. So change that to push @{$hash{$parent}}, $child;, and you'll start to get some results.
This is how I'd traverse the tree:
sub other_walk {
my ($indent, $item) = @_;
print ' ' x (2 * $indent);
print $item, "\n";
for (@{$hash{$item}}){
other_walk($indent+1, $_);
}
}
other_walk(0, 1);
It's not perfect, but I think it goes into the right direction, and you can add your ASCII art eye candy later on ;-) | [reply]
[d/l]
[select] |