Tree depth is a classical example for Depth-first search:

use strict;
use warnings;
use List::Util qw/max/;
my $graphspec = '1 -> 2 2 -> 0 3 -> 4 4 -> 2 5 -> 10 6 -> 10 7 -> 9 8 
+-> 9
9 -> 6 10 -> 4 11 -> 10 12 -> 10 13 -> 12 14 -> 10 15 -> 2';

my %graph;
while ($graphspec =~ /(\d+)\s+->\s+(\d+)/g) {
    $graph{$1} = $2;
}

sub depth {
    return max map { $_and 1 + depth($graph{$_}) } @_;
}

print depth(keys %graph);
[download]

Update: this produces the largest distance to the root, not the height. The difference is 1, ie the height is always one larger than the distance to the root. Easy to fix if you do want the tree height.

Thanks - this works fine!

At a second glance it didn't work as well as I expected. In fact, I get quite weird results when I try to implement your code into a program that takes an entire file with > 35,000 trees, each one occupying one line of values. Here are the first lines of the revised code: use strict; use warnings; use List::Util qw/max/; my %graph; while (<>) { chomp; while ($_ =~ /(\d+)\s+->\s(\d+)/g) { ...etc. Then I wish to print each tree depth on a separate line of output until EOF. It looks good at the beginning, but there seems to be an accumulation of values in some variable making the output lines growing into unrealistic figures. Do you have any solution to this?

If you have one graph per line, you should empty %graph before reading a line, or even better, declare it on the inside of the while-loop to limit its scope, and pass it on to the depth subroutine.

By the way, my code isn't optimized for large trees (because your example wasn't very large), it might make sense to cache depths if a graph is much larger.

Perl 6 - second systems done right

Here's how I'd determine the max depth of a Perl nested hash/array structure:

use Carp qw/croak/;
use List::Util qw/max/;

sub max_depth
{
    my $thing = shift;
    croak "too many arguments" if @_;
    
    my $children = do {
        if (ref $thing eq 'ARRAY')    { $thing }
        elsif (ref $thing eq 'HASH')  { [values %$thing] }
        else                          { undef }
    };
    
    return 1 + max map { max_depth($_) } @$children
        if $children;

    return 0;
}

my $data = {
    foo => [1, 2, 3],
    bar => [4, 5, { quux => { quuux => 6 } }],
    baz => 7,
    };

print max_depth($data->{bar}[2]{quux}{quxux}) . "\n";
print max_depth($data->{bar}[2]{quux}) . "\n";
print max_depth($data->{bar}[2]) . "\n";
print max_depth($data->{bar}) . "\n";
print max_depth($data) . "\n";

__END__
0
1
2
3
4
[download]

Any suggestions?

Tree::Simple

#!/usr/bin/perl --
use strict; use warnings;
use Tree::Simple;
my $tdat = <<'SHABBA';
1 -> 2
2 -> 0
3 -> 4
4 -> 2
5 -> 10
6 -> 10
7 -> 9
8 -> 9
9 -> 6
10 -> 4
11 -> 10
12 -> 10
13 -> 12
14 -> 10
15 -> 2
SHABBA

my %nodes;
while( $tdat =~ /^(\d+)\D+(\d+)$/mg ){
#~     my( $parent_id, $child_id ) = ( $1, $2 );
    my( $child_id , $parent_id ) = ( $1, $2 );
    my $parent = $nodes{$parent_id} ||= Tree::Simple->new( $parent_id 
+);
    my $child = $nodes{$child_id} ||= Tree::Simple->new( $child_id );
    $parent->addChild( $child );
}


for my $k ( sort { $a <=> $b } keys %nodes ){
    my $tree = $nodes{$k};
    use Tree::Simple::View::ASCII;
    my $tree_view = Tree::Simple::View::ASCII->new( $tree );
    $tree_view->includeTrunk(1);
    print $tree_view->expandAll(), $/, $/;

    $tree->traverse(sub {
      my ($_tree) = @_;
      my $d = $_tree->getDepth();
      print ("($k)($d)", ("\t" x $d), $_tree->getNodeValue(), "\n");
    });

    print "($k) getHeight ", $tree->getHeight, "\n";
    print "($k) getWidth ", $tree->getWidth, "\n";
    print "($k) getDepth ", $tree->getDepth, "\n";
    print "#" x 12, "\n";
}
__END__
[download]

Not sure if this is what you want, but the Height/Width number seems to jive (7) , the depth is zero based

0
    |---2
            |---1
            |---4
            |       |---3
            |       |---10
            |               |---5
            |               |---6
            |               |       |---9
            |               |               |---7
            |               |               |---8
            |               |---11
            |               |---12
            |               |       |---13
            |               |---14
            |---15


(0)(0)2
(0)(1)    1
(0)(1)    4
(0)(2)        3
(0)(2)        10
(0)(3)            5
(0)(3)            6
(0)(4)                9
(0)(5)                    7
(0)(5)                    8
(0)(3)            11
(0)(3)            12
(0)(4)                13
(0)(3)            14
(0)(1)    15
(0) getHeight 7
(0) getWidth 7
(0) getDepth -1
############
[download]

I would be so grateful!

Pics? ;)

Anonymous, the finishing "Pics? ;)" may have been intended humorously, but it's contributing to the kind of atmosphere that makes women feel unwelcome on PerlMonks, and in programming circles in general.

Please don't.