Expanding tree paths

[soup_or_power]

I'm trying to list all the paths in a tree. The tree is specified by
the following hash:

my %tree=(
"a1" => ["a2", "a6", "a9"],
"a2" => ["a3", "a4", "a5"],
"a6" => ["a7", "a8"],
"a9" => ["a10", "a11"],
"a10" => ["a12", "a13"]
);
I want to extract the paths as follows:

a1 - a2 - a3
a1 - a2 - a4
a1 - a2 - a5
a1 - a6 - a7
a1 - a6 - a8
a1 - a9 - a10 - a12
a1 - a9 - a10 - a13
a1 - a9 - a11

Can anyone help me out? I am posting my code just in case anyone can
improve it. Many thanks!


use Data:umper;
my %tree=(
"a1" => ["a2", "a6", "a9"],
"a2" => ["a3", "a4", "a5"],
"a6" => ["a7", "a8"],
"a9" => ["a10", "a11"],
"a10" => ["a12", "a13"]
);
$depth{"a10"}=2;
$depth{"a11"}=2;
$depth{"a12"}=3;
$depth{"a13"}=3;
&Data:umper:umper(\$tree);
my $path=();
my $each=();
my $root="";
my $iter=0, $root;
sub recur() {
my ($top, %tree)=@_;
if ($iter == 0) {
$root=$top;
$iter=1;
}
if ( exists $tree{$top}) {
} else {
push @$path, @each;
print "this is each:\n";
foreach my $h (@each) {
print "$h\n";
}
my $x=pop @each;
print "popping last $x";
return;

}
print "entering for top=$top";
foreach my $k ($tree{$top}) {
if ($depth{$top} != @each) {
@each=();
}
@each=mypush($root, @each);
@each=mypush($top, @each);
print "\npushed top=$top\n";
foreach my $h (@each) {
print "my $h\n";
}
foreach (@$k) {
print "pushing $_ for parent $top\n";
@each=mypush($_, @each);
recur($_, %tree);
}
}
}

sub mypush() {
my($v, @a)=@_;
my $flg=0;
foreach (@a) {
if ($v eq $_) {
$flg=1;
}
}
if ($flg == 1) {
} else {
push @a, $v;
}
return @a;
}

 

[Paul Lalli]

I'm trying to list all the paths in a tree. The tree is specified by
the following hash:

my %tree=(
"a1" => ["a2", "a6", "a9"],
"a2" => ["a3", "a4", "a5"],
"a6" => ["a7", "a8"],
"a9" => ["a10", "a11"],
"a10" => ["a12", "a13"]
);
I want to extract the paths as follows:

a1 - a2 - a3
a1 - a2 - a4
a1 - a2 - a5
a1 - a6 - a7
a1 - a6 - a8
a1 - a9 - a10 - a12
a1 - a9 - a10 - a13
a1 - a9 - a11

Can anyone help me out? I am posting my code just in case anyone can
improve it. Many thanks!

Your code is not strict compliant. Your code generates three warnings
and zero output. Are you asking for help finishing it?

use Data:umper;
my %tree=(
"a1" => ["a2", "a6", "a9"],
"a2" => ["a3", "a4", "a5"],
"a6" => ["a7", "a8"],
"a9" => ["a10", "a11"],
"a10" => ["a12", "a13"]
);
$depth{"a10"}=2;
$depth{"a11"}=2;
$depth{"a12"}=3;
$depth{"a13"}=3;

Your description above said nothing about depths. What are these for?

&Data:umper:umper(\$tree);

1) Dumper is exported by Data:umper. There is no need to fully
qualify it.
2) Do not call subroutines with & unless you specifically want the
special behavior that creates. You don't.
3) There is no such variable $tree. This is why we "use strict;"

<snip very lengthy code>

I'm sorry, but I really don't feel like going through that large amount
of code to figure out what might be wrong with it. I would start by
adding strict and warnings to your code and fixing the warnings the
interpreter tells you are there.

In the mean time, here is my solution to your problem as stated. We
simply maintain the current path in the variable @_. When the
recursive function is called, we examine the last element of the path.
If that element has an entry in the hash, we call recurse() on each of
that entry's path elements. If not, we print out the current path:

#!/usr/bin/perl
use strict;
use warnings;
my %tree=(
"a1" => ["a2", "a6", "a9"],
"a2" => ["a3", "a4", "a5"],
"a6" => ["a7", "a8"],
"a9" => ["a10", "a11"],
"a10" => ["a12", "a13"]
);


sub recurse {
my $first = $_[-1];
if (exists ($tree{$first})){
my @paths = @{$tree{$first}};
foreach my $path (@paths){
recurse (@_, $path);
}
} else {
local $" = ' - ';
print "@_\n";
}
}

recurse "a1";

__END__

a1 - a2 - a3
a1 - a2 - a4
a1 - a2 - a5
a1 - a6 - a7
a1 - a6 - a8
a1 - a9 - a10 - a12
a1 - a9 - a10 - a13
a1 - a9 - a11


Paul Lalli

 

[soup_or_power]

Paul
Many thanks for your solution. It works like magic ! I'm trying to
understand how it works. My plan is to put some print statements and
figure it out

Best regards