Iterating over a hash, recursively, forever!

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

Long time listener, first time caller. Love the show.

I gave up on my employer ever having a formal org chart, so I've started piecing one together with information available from our time and attendance package.

I've got the following information for each employee:

Department ID, employee ID, boss ID, employee name, department description.

I've built a hash of %boss, which contains:

$VAR1 = {
          '4' => '3',
          '1' => '1',
          '3' => '2',
          '2' => '1'
        };
[download]

Okay, you're right. This isn't the Real Information I'm working with, it's just sample data! The problem still shows with this small data set, however.

In other words, employee ID 1 is the big kahuna in charge. Employee 2 works for 1, 3 works for 2, and 4 is the low man on the totem pole that actually does the work. *cough*

Here's my subroutine, which is passed an employee ID:

sub getreports {
    my $target = shift(@_);
    while (my ($employeeid, $bossid) = each %boss) {
        print "scanning data for x, $target:   $employeeid, $bossid\n"
+;
        if ($bossid eq $target) {
            print "\n$bossid  $name{$bossid}    $area{$bossid}\n-> $em
+ployeeid  $name{$employeeid}\n";
        if ($hasreports{$employeeid}) {
            print "$name{$employeeid} has subordinates\n";
                print "getting employees of $employeeid\n";
                getreports($employeeid);
            }
    }
    }
    print "exiting while % boss with target of $target\n\n";
}
[download]

Here's the output I'm getting:

scanning data for x, 2:   4, 3
scanning data for x, 2:   1, 1
scanning data for x, 2:   3, 2

2  big boss    corner office
-> 3  small boss
small boss has subordinates
getting employees of 3
scanning data for x, 3:   2, 1
exiting while % boss with target of 3

scanning data for x, 2:   4, 3
scanning data for x, 2:   1, 1
scanning data for x, 2:   3, 2
[download]

This seems to be willing to loop forever, starting over at the beginning of the hash. What have I done wrong?

Humbly,
Anonymous Monk

Comment on Iterating over a hash, recursively, forever! Select or Download Code

Replies are listed 'Best First'.
Re: Iterating over a hash, recursively, forever! by jweed (Chaplain) on Jan 13, 2004 at 22:41 UTC
The problem is with the nature of the `each` function. This will return keys of the hash in order, until it returns false when there are none left. Then it starts over again. The problem now is that when you call you function recursively, the call to each isn't getting reset. So you go through the first three key/value pairs in the top function, then your subordinates search that you performed recursively is given the last key/value pair when it first evaluates each. Then, it gets `undef`, which is why it exits prematurely. Now that the hash has returned undef, it starts from the beginnig with the original function again. The global nature of %boss ensures that your recursion doesn't work. To stop this behavior, begin and end your function with `keys %boss` This will ensure that you start anew with the values. If it is possible to have a structure where a person has more than one subordinate, like this: `$VAR1 = { '4' => '3', '1' => '1', '3' => '2', '2' => '1', '3' => '5' };` [download] Then you will want to try assigning a temp hash before you call recursively. Though this isn't tested, you could try doing this at the top of your function: `my %temp_boss = %boss; while (my ($employeeid, $bossid) = each %temp_boss) {` [download] I think that recursive functions play nicely with lexical scoping, but don't quote me on that. HTH. Code is (almost) always untested. http://www.justicepoetic.net/	[reply] [d/l] [select]
Re: Iterating over a hash, recursively, forever! by Roger (Parson) on Jan 13, 2004 at 23:12 UTC
Logic error in the recursive function. Basically to make a recursive function, you either need to have a gradually reducing data set, or set a terminating condition, or both. I have wrote a small example below that prints an organization tree recursively. Note the terminating condition and reduced data set in the demo. use strict; use warnings; my %employees = ( '1' => { boss_id => '1', emp_name => 'big boss', }, '2' => { boss_id => '1', emp_name => 'middle boss', }, '3' => { boss_id => '2', emp_name => 'worker 1', }, '4' => { boss_id => '1', emp_name => 'small boss', }, '5' => { boss_id => '2', emp_name => 'worker 2', }, '6' => { boss_id => '4', emp_name => 'worker 3', }, ); getreports(1); sub getreports { my ($id, $level) = @_; $level = $level \|\| 0; die "Employee $id doesn't exist" if ! exists $employees{$id}; print ' ' x ($level * 3), "\|\n", ' ' x ($level * 3), "+- $employees{$id}{emp_name}\n"; my @employees = (); foreach my $emp_id (keys %employees) { # find the employees under $id except # when boss is himself push @employees, $emp_id if $employees{$emp_id}{boss_id} eq $id && $emp_id ne $id; } return if $#employees < 0; getreports($_, $level + 1) foreach (@employees); } [download] And the output is - `\| +- big boss \| +- small boss \| +- worker 3 \| +- middle boss \| +- worker 1 \| +- worker 2` [download]	[reply] [d/l] [select]
Re: Iterating over a hash, recursively, forever! by derby (Abbot) on Jan 14, 2004 at 01:53 UTC
Okay. So maybe I'm just too cynical but recursion, employee, id, department screams classic recursion homework problem. Just google it. If your seriously interested in perl and recursion, check out subroutine recurse vs goto LABEL or Recursion. -derby	[reply]
Re: Iterating over a hash, recursively, forever! by thor (Priest) on Jan 14, 2004 at 00:00 UTC
Might I suggest GraphViz for this? At a glance, GraphViz figures out how to draw a graph nicely. Heck, there's even a module for it. What's nice about it is that is that you provide it with the relationships, and it draws the picture for you in a format of your choosing. Here's some sample code (untested): `#!/usr/bin/perl -w use strict; use GraphViz; my $graph = GraphViz->new(); $graph->add_edge("Big Cheese" => "Vice Chair One"); $graph->add_edge("Big Cheese" => "Vice Chair Two"); $graph->add_edge("Vice Chair One" => "Manager Three"); $graph->add_edge("Vice Chair Two" => "Manager Four"); # etc $graph->as_ps("outfile.ps"); #because I like postscript` [download] thor	[reply] [d/l]
Re: Iterating over a hash, recursively, forever! by Roy Johnson (Monsignor) on Jan 13, 2004 at 22:44 UTC
Your use of the hash isn't very perlescent. You shouldn't be scanning it repeatedly. Every recursive call starts by scanning %boss, and hitting the same two ifs for the first item in it. Give your algorithm some more thought. Maybe write it in pseudocode first. The PerlMonk `tr///` Advocate	[reply]
Re: Iterating over a hash, recursively, forever! by Anonymous Monk on Feb 15, 2004 at 05:25 UTC
It's me again - the original poster. I thought I'd exhausted all of Perl's built-in documentation in my quest, but that wasn't the case. After I rethought my approach to the problem, MJD's oh-so-excellent perlreftut was exactly what I needed. Thanks to Roy Johnson and Roger for making me realize I needed to rethink. Here's an excerpt (I know, the code's pitiful. I'm still a newbie.) of what I wound up with: # populate the boss's part of the orgchart with employee numbers that + report to him/her while (my ($loccode, $empnum, $bossnum, $name, $area) = $sth->fetchrow +_array) { $boss{$empnum} = $bossnum; $name{$empnum} = $name; $area{$empnum} = $area; $loccode{$empnum} = $loccode; push @{$chart{$bossnum}}, $empnum; } # later, while working through the orgchart sub printreports { my $number = shift(@_); my $indent = shift(@_)." "; return unless defined @{$chart{$number}}; print "$indent$loccode{$number} $area{$number}:\n$indent*$name{ +$number} $number\n"; my @reports = @{$chart{$number}}; foreach my $peon (@reports) { next if $number == $peon; print "$indent$name{$peon} $peon $loccode{$number}\n"; printreports($peon, $indent) if $depth eq "recursive"; } } [download] This produces an (admittedly, not the most pretty) indented org chart of sorts, with the name of each department listed as the respective department head is encountered. Again, it ain't pretty, but it beats the snot out of the total lack of documentation we had before. Oh, and Derby: You're right, you're too cynical. This wasn't homework, it was live data from a Kronos database on an iSeries 830. Maybe next time, you should expend effort on a question that you feel isn't homework.	[reply] [d/l]