Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Traversing a simple tree - using GRAPH::DFS

by wufnik (Friar)
on Jun 17, 2004 at 13:18 UTC ( [id://367606]=note: print w/replies, xml ) Need Help??


in reply to Traversing a simple tree

why not generalize your problem slightly and use Jarko Heitaniemi's Graph packages to do the work of the postorder traversal for you?

i am normally reluctant to suggest any reengineering of code presented, but i have personally saved so much time using Graph::Base, Graph::Directed and Graph::DFS that i feel compelled to sketch out the following:

use Graph::Directed; use Graph::Base; use Graph::DFS; my $g = Graph::Directed->new(); growtree($g, $mydatastruct); # create the tree rooted in $g my $search = Graph::DFS->new($g); # for the search... while (my $vertex = $search->next_postorder()){ my $info = $g->get_attribute('myattrib',$vertex); # do stuff with $info... } sub growtree{ my ($g, $mydatastruct) = @_; my $data = # ...get stuff from $mydatastruct; $g->set_attribute('myattrib',$g, $data); my @newedges = # ...get new edges from $mydatastruct $g->add_edge($g,$_) for @newedges; my @newvertices = grep {! $g->has_vertex($_)} @newedges; map { growtree($_,$mydatastruct) } @newvertices; }
won't save you time immediately, but very handy in the medium & long term.

hope it helps;

...wufnik

-- in the world of the mules there are no rules --

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2024-03-29 05:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found