in reply to Tree depth

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.

Perl 6 - second systems done right

Replies are listed 'Best First'.
Re^2: Tree depth
by katarinahm (Initiate) on Mar 13, 2012 at 10:41 UTC
    Thanks - this works fine!
[reply]
Re^2: Tree depth
by katarinahm (Initiate) on Mar 13, 2012 at 13:44 UTC
    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?
[reply]

      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
[reply]
[d/l]
[select]

        Sorry to bother you again, but your recent advice doesn't seem to help me. I've changed the code into this:

        while (<>) {
        chomp;
        (@row) = split(/ /,$_);
        foreach $item (@row) {
                ($node,$value) = split(/->/,$item,2);
                $graph{$node} = $value;
        }
        sub depth {
                return max map { $_ and 1 + depth($graph{$_}) } @_;
                shift @_
}
        print depth(keys %graph);
        print "\n";
        @row = ();
        $graph = ""
}

        [download]

        , but I still get the values wrong, even if I just try it on a few lines of my infile. Here is an example of my infile (9 lines), picked at random but in a sequence: ------------------------------------ 

        1->14 2->3 3->1 4->5 5->3 6->3 7->9 8->9 9->10 10->6 11->10 12->10 13-
+>10 14->0 15->14 16->15 17->18 18->15 19->18 20->19 21->14
1->2 2->0 3->5 4->5 5->6 6->2 7->2 8->7 9->2
1->2 2->0 3->4 4->2 5->7 6->7 7->4 8->7 9->8 10->2
1->2 2->0 3->2 4->3 5->7 6->5 7->11 8->7 9->7 10->9 11->4 12->11 13->1
+2 14->15 15->11 16->2
1->2 2->0 3->2
1->2 2->0 3->2 4->5 5->3 6->5 7->6 8->6 9->8 10->9 11->12 12->10 13->2
1->2 2->0 3->5 4->5 5->2 6->2 7->6 8->2
1->3 2->3 3->4 4->0 5->4 6->5 7->6 8->6 9->8 10->11 11->8 12->11 13->1
+2 14->4
1->2 2->8 3->2 4->2 5->6 6->4 7->6 8->0 9->8 10->8

        [download]
        --------------------------------------

        Here is the output that I get:

        -------------------------------------- 
        9
7
6
9
9
13
10
10
7

        [download]
        --------------------------------------

        Then, if I try the script on a separate input file, containing just those 9 lines, I get the following output:

        -------------------------------------- 
        7
5
5
8
8
13
10
9
6

        [download]
        --------------------------------------

        It's confusing... Do you have any ideas?

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom