You can use a structure just like the one you show. You don't really need a data structure that is internally hierarchical. The one you have is an adjacency (dependency) list, which can store a tree (well, any graph) just fine. In fact, it's a little nicer since there may be duplicated dependencies, as you mention (your dependencies form a directed acyclic graph, and not necessarily a tree). Assuming that finding the dependencies is trivial, generate the adjacency list like this:
my @pkgs = qw[ mainpackage-1.0 ];
my %deps;
while (@pkgs) {
my $pkg = shift @pkgs;
next if exists $deps{$pkg};
my @deps = find_dependencies($pkg);
$deps{$pkg} = \@deps;
push @pkgs, @deps;
}
You can traverse it like a tree like this:
sub traverse {
my ($deps, $root, $depth) = @_;
print " " x $depth, "$root\n";
traverse($deps, $_, $depth + 1)
for @{ $deps->{$root} };
}
traverse( \%deps, "mainpackage-1.0" );
.. which would generate output like this:
mainpackage-1.0
dependency1-1.3
dep1_of_dep1
dependency2-2.3
dep1_of_dep2
dep2_of_dep2
dep3_of_dep3
dependency3
The output would contain duplicates if the directed graph is not a tree. But you can use an additional hash within your traversal to mark already-seen packages, say, if you were doing a postorder traversal to determine what order to install all the needed packages.
Anyway, with the adjacency list data structure, all the dependency information about a package is in one place. You can do the same with restrictions, i.e. "somepackage < 4.0" and "somepackage > 3.0". Store all these restrictions in another similar hash indexed by package name. When you're done calculating dependencies, look at each package's list of restrictions and see if they're reconcilable.
|