Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^4: Question about recursively generated iterators

by perlfan (Vicar)
on Sep 21, 2007 at 19:31 UTC ( [id://640427]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Question about recursively generated iterators
in thread Question about recursively generated iterators

I am not stuck on doing this recursively - a DFS iterator example or tutorial would be killer. I'll send you a msg, too. Thanks!

Replies are listed 'Best First'.
Re^5: Question about recursively generated iterators
by Limbic~Region (Chancellor) on Sep 22, 2007 at 00:55 UTC
    perlfan,
    Doing a DFS as an iterator is pretty simple. If this code example isn't sufficient, let me know.
    #!/usr/bin/perl use strict; use warnings; { my %seen; my %tree = ( A => ['B', 'C'], B => ['D', 'E'], C => ['F', 'G'], E => ['H', 'I'], G => ['J', 'K'], H => ['L', 'M', 'N'], I => ['O', 'P'], K => ['Q'], ); sub get_root { 'A' } sub get_children { my ($node) = @_; return $tree{$node} ? @{$tree{$node}} : (); } sub visited { my ($node, $val) = @_; return $seen{$node} = $val if defined $val; return $seen{$node}; } } sub gen_tree_iter { my @nodes = get_root(); return sub { { my $node = shift @nodes; return undef if ! defined $node; redo if visited($node); visited($node => 1); unshift @nodes, get_children($node); return $node; } }; } my $iter = gen_tree_iter(); while (my $node = $iter->()) { print "Visiting $node\n"; }

    Cheers - L~R

Re^5: Question about recursively generated iterators
by Limbic~Region (Chancellor) on Sep 22, 2007 at 14:50 UTC
    perlfan,
    I wrote another version of the DFS iterator that was more memory efficient at the sacrifice of speed since I wasn't sure which was more important to you. The most items this version will ever have on the stack/queue is the max depth of the tree.

    Please let me know if this requires explanation as it is not as clear as the original.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://640427]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (8)
As of 2024-03-29 13:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found