Jeff 'Japhy' Pinyan wrote:
>
> >my %tree = { package1 => [ package2, package3, package4 ],
> > package2 => [ package7 ],
> > package3 => [ package5 ],
> > package4 => [ package7, package6],
> > package5 => [ ],
> > package6 => [ ],
> > package7 => [ ] };
>
> You have curly braces { ... } where you want parentheses ( ... ).
>
> >Now, I want to walk the tree starting with a known "package1" and build an
> >ordered list of packages to install. For example:
> >
> >package7
> >package2
> >package5
> >package3
> >(no package7 here because it is already in the list)
> >package6
> >package4
> >package1
>
> This sounds like postorder tree traversal to me:
>
> // pseudocode
> postorder (tree) {
> if tree is null: return
> for node in tree.nodes: postorder(node)
> print tree
> }
>
> With your hash, in perl, this would look like:
>
> postorder(\%tree, 'package1');
>
> sub postorder {
> my ($tree, $pkg, $seen) = @_;
> return if $seen->{$pkg}++; # to stop from traversing a node twice
>
> postorder($tree, $_, $seen) for @{ $tree->{$pkg} };
> print "$pkg\n";
> }
>
> This gives the expected output.
Hi Jeff.
But in the general caase there's a problem with finding the root of the tree.
Indeed there may be several independent trees or none at all if the
relationships are cyclic.
Rob
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>
