Arranging a dependency tree

[Bryan Olson]

Kyle Root wrote:
 > I've created a jumble of python modules, in each one is a tuple that
 > goes something like,
 >
 > deps = ("file10","file7","file3").
 >
 > And some have no dependencies at all.  I have one file called "start",
 > and the whole thing makes a tree of dependencies as each file has deps
 > and their deps might have deps, and so on.  What I'm trying to do is
 > "straighten" them or put them in order as if they were to be
 > installed.  Basically I'm trying to replicate the way portage does it.
 > :)
[...]
 > Basically I was wondering if anyone had any tips or pointers, or knew
 > of any dependency resolving algorithms...

This may be too abstract to help, but I guess it couldn't
hurt...

'Depends' is a binary relation (a set of pairs) where (a, b) is
an element of Depends if and only if b is in a's "deps"
list/tuple.

If you want an ordering in which each module follows the
modules on which it depends, you want a 'topological sort' based
on the depends relation.

If you want to find all the modules on which a module depends,
you want the 'transitive closure' of the depends relation.


If you want to know if the dependencies can or cannot possibly
work, look up the work of Bertrand Meyer and his Eiffel team
on possibly-circular dependencies.


-- 
--Bryan