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]

In reply to Depth-first tree traversal with Algorithm::Loops::NestedLoops by Solo

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.