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.

blokhead

In reply to Re: Re: Re: building a dependency tree by blokhead
in thread building a dependency tree by agaffney

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.