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;
}
[download]

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" );
[download]

.. 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
[download]

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.