CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Advanced:
Tree Hierarchy

 



sriharsha_12
Novice

Oct 4, 2011, 2:05 AM

Post #1 of 5 (4017 views)
Tree Hierarchy Can't Post

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

Post #2 of 5 (3806 views)
Re: [sriharsha_12] Tree Hierarchy [In reply to] Can't Post

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

Post #3 of 5 (3684 views)
Re: [Zhris] Tree Hierarchy [In reply to] Can't Post

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

Post #4 of 5 (3498 views)
Re: [sriharsha_12] Tree Hierarchy [In reply to] Can't Post

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

Post #5 of 5 (3431 views)
Re: [rovf] Tree Hierarchy [In reply to] Can't Post

OK. I'll try it.

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives