Home: Perl Programming Help: Advanced:
Tree Hierarchy



sriharsha_12
Novice

Oct 4, 2011, 2:05 AM


Views: 6504
Tree Hierarchy

I have an interesting problem. consider the below tree structure,

....................a
................/.....\
................b......c
............../..\....|
.............d....e...b
....................../..\
......................d...e

if the input is 'e', i need to print
e - b - a & e - b - c - a
if input is c,
c - a

i need to write a perl script which applies for any given tree structure.

i generated a hash,

a => -
b => a,c
c => a
d => b
e => b

here i'm stuck in writing an algo that prints any given tree.

any ideas?


(This post was edited by sriharsha_12 on Oct 5, 2011, 2:01 AM)


Zhris
Enthusiast

Oct 6, 2011, 1:23 PM


Views: 6293
Re: [sriharsha_12] Tree Hierarchy

Hi,

Where is the tree structure derived? You mention you generated a hash, is this meant to be the hard coded tree? Otherwise, inevitably the first task is to parse the tree structure into some kind of usable Perl data structure. Maybe provide some more information.

(Update: I wrote a very rough script (not great) to demonstate some fundamental aspects i.e. recursive subroutine etc):


Code
######################################## 

#! /usr/bin/perl
use strict;
use warnings;

########################################

my $tree = {
a => {
b => {
d => { },
e => { }
},
c => {
b => {
d => { },
e => { }
}
}
}
};

my $input = 'e';

########################################

my $data = process($tree);

foreach (keys %$data) {
print reverse($_) . "\n" if ($_ =~ /$input$/);
}

########################################

sub process
{
my $ref = shift || die "Tree required.\n";
my $key_string = shift || '';
my $data = shift || { };

foreach my $key (keys %$ref)
{
my $next_ref = $ref->{$key};
my $next_key_string = $key_string . ',' . $key;
$data->{$next_key_string} = undef;

process($next_ref, $next_key_string, $data);
}

return $data;
}

########################################


Chris


(This post was edited by Zhris on Oct 6, 2011, 2:27 PM)


sriharsha_12
Novice

Oct 7, 2011, 1:17 AM


Views: 6171
Re: [Zhris] Tree Hierarchy

The hash is not hard coded. The tree structure can change. Even the number of levels can increase.

simpler version of the input file,
a:
--b
--c
b:
--d
--e
c:
--b

from this input file i derived the hash,
a => - (a is the parent because it is not called anywhere)
b => a,c
c => a
d => b
e => b

another sample file,
a:
--b
--c
--d
b:
--e
--f
--c
c:
--g
--h
from this i'll get the hash,
a => -
b => a
c => a,b
e => b
f => b
g => c
h => c
d =>a

my recursive algorithm should apply for any tree structure.

your code looks good for a hard coded hash.


rovf
Veteran

Oct 14, 2011, 2:48 AM


Views: 5985
Re: [sriharsha_12] Tree Hierarchy

I had a related problem and found on CPAN the module 'Graph', which proved to be very useful.

It might look like overkill to your problem, but it is easy to install and use.

Ronald


sriharsha_12
Novice

Oct 19, 2011, 9:13 AM


Views: 5918
Re: [rovf] Tree Hierarchy

OK. I'll try it.