On May 12, Andrew Gaffney said:
my %tree = { package1 => [ package2, package3, package4 ], package2 => [ package7 ], package3 => [ package5 ], package4 => [ package7, package6], package5 => [ ], package6 => [ ], package7 => [ ] };
You have curly braces { ... } where you want parentheses ( ... ).
Whoops. I'm usually use hash references instead of actual hashes.
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:
I've seen that term before when looking into this, but I don't know what it means.
// 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.
Is $seen another hash that should be passed as a reference to postorder() ?
I also want to be able to track what package is a dependency of what (which key a certain value is under) with my tree structure. What is the easiest way to do this? Is there a better way to do this?
You'd need another structure somewhere. Starting with this:
my %tree = ( package1 => [ qw( package2 package3 package4 ) ], package2 => [ qw( package7 ) ], package3 => [ qw( package5 ) ], package4 => [ qw( package7 package6 ) ], package5 => [ ], package6 => [ ], package7 => [ ], );
You could then do:
my %parents_of;
for my $p (keys %tree) { push @{ $parents_of{$_} }, $p for @{ $tree{$p} }; }
If you can't understand that code, let me unroll it a bit for you:
for my $parent (keys %tree) { for my $kid (@{ $tree{$parent} }) { push @{ $parents_of{$kid} }, $parent; } }
Now you have another hash of arrays that is basically the inverse of %tree:
%parents_of = ( package4 => [ 'package1' ], package5 => [ 'package3' ], package6 => [ 'package4' ], package7 => [ 'package4', 'package2' ], package2 => [ 'package1' ], package3 => [ 'package1' ], );
Nice. Thank you. I'll give this a try.
-- Andrew Gaffney Network Administrator Skyline Aeronautics, LLC. 636-357-1548
-- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] <http://learn.perl.org/> <http://learn.perl.org/first-response>
