Depth-first tree traversal with Algorithm::Loops::NestedLoops

Thinking about Algorithm::Loops::NestedLoops has become my favorite distraction.

Here's a little snippet for performing depth-first tree traversal. The loop generated finds descendants to depth nodes-1, which is as deep as a tree can be--and NestedLoops seems to efficiently short-circuit those extra loops below the actual depth of the leaf node being examined.

use strict;
use warnings;

use Algorithm::Loops qw( NestedLoops );

my $tree = {
  A => '',
  B => 'A',
  C => 'A',
  D => 'C',
  E => 'C',
  F => 'B',
  G => 'D',
  H => 'D',
  I => 'D',
  J => 'G',
  K => 'B',
  L => 'K',
  M => 'L',
  N => 'M',
  O => 'N',
};

sub get_descendants {
  my ($tree, $node) = @_;
  my @children;
  for my $k (keys %$tree) {
      push @children, $k if $tree->{$k} eq $node;
  }
  return \@children;
}

my @paths = NestedLoops(
    [   sub { get_descendants($tree,'') },
       (sub { get_descendants($tree,$_) } ) x (scalar(keys %$tree) - 2
+)
    ],
    {  OnlyWhen => 1
    },
    sub { \@_ }
);

print join(', ',@$_) . "\n" for (@paths);

__END__
A
A, B
A, B, F
A, B, K
A, B, K, L
A, B, K, L, M
A, B, K, L, M, N
A, B, K, L, M, N, O
A, C
A, C, E
A, C, D
A, C, D, H
A, C, D, I
A, C, D, G
A, C, D, G, J
[download]

Comment on Depth-first tree traversal with Algorithm::Loops::NestedLoops Download Code

Replies are listed 'Best First'.
Re: Depth-first tree traversal with Algorithm::Loops::NestedLoops by Velaki (Chaplain) on Aug 12, 2004 at 16:17 UTC
Will you be creating snippets for BF graph traversal? It seems like this could be a nice tool for building parser factories, and performing dijkstra's, etc. Kudos! -v "Perl. There is no substitute."	[reply]
Re: Depth-first tree traversal with Algorithm::Loops::NestedLoops by Anonymous Monk on Jun 16, 2009 at 05:58 UTC
do you have implementation with oop php ?	[reply]