Arranging a dependency tree

[Kyle Root]

I'm working on a little practice program, but I've become stuck and am
now utterly confused :?

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.
:)

I've been thinking about this for a few days but I always get lost.
So far I have a has_deps(filename) function, and not much else. I get
stuck on the actual changing the files from the random jumble to a
into a nice orderly list of files. One problem that I can't
overcome is when I'm a couple of deps in and I finally get to the
files that don't require anything, I have no way of getting back to do
the parent file's other deps. (Does that make any sense?)

Basically I was wondering if anyone had any tips or pointers, or knew
of any dependency resolving algorithms...

Thanks,
Kyle

[Heiko Wundram]

Basically, dependencies (should) create a tree structure, except when you have
circular dependencies. Now, what you have to do to resolve the tree structure
in case there are no circular dependencies is to walk the edges of the graph,
from leaf to top.

Example graph:

x
| ----> y
| ----> z | ----> a
| | ----> b
| ----> a

Now, you need a way to store this in Python, I'd use dictionaries:

deps = {"x":
{"y":{},
"z":{"a":{}}
}}

Reading the data into a format like this is pretty simple too:

<code>
def makeTree(files):
"""Pass in a list of files for which dependency info
should be generated."""

deps = {}
cur_files = [(fname,deps) for fname in files]
all_deps = {}
while cur_files:
cur_file, cur_deps = cur_files.pop()
if cur_file in all_deps:
cur_deps[cur_file] = all_deps[cur_file]
continue
new_deps = {}
# getDeps returns the dependencies needed by cur_file.
for dep in getDeps(cur_file):
cur_files.append((dep,new_deps))
cur_deps[cur_file] = new_deps
all_deps[cur_file] = new_deps
return deps
</code>

Now, reading in the dependency list as done above properly takes care of
circular dependencies, and might create dictionaries which contain themselves
at some depth. It won't read dependency info more than once for a given file,
too.

The following code will walk the tree generated by makeTree, but it will barf
on circular dependencies. You'll have to devise some means to deal with
these, the most common form being simply to break tree walking at the current
level in case you encounter a circular dependency. The algorithm is
recursive. Doing it iteratively would be possible too, but at quite some
cost.

<code>
def _walkTree(tree,cur_files,walked_files):
for cur_file, cur_deps in tree.iteritems():
if cur_file in walked_files:
continue
elif cur_file in cur_files:
# Deal with circular deps here. You might just do:
# raise StopIteration
raise ValueError, "Circular tree structure."
if cur_deps:
for sub_file in _walkTree(cur_deps,cur_files+(cur_file,),walked_fi les):
yield sub_file
walked_files.append(cur_file)
yield cur_file

def walkTree(tree):
"""Walk a tree as generated by makeTree."""

for f in _walkTree(tree,(),[]):
yield f
</code>

Well, hope this helps and gives you some hints!

Heiko.

[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

[Bryan Olson]

Heiko Wundram wrote:

Basically, dependencies (should) create a tree structure, except when
you have circular dependencies. [...]

Non-circular dependencies create a directed acyclic graph (DAG),
not necessarily a tree.

I'm sure Heiko actually knew this, but being the kind of smart-
ass I am, I can't resist the chance to correct him on things he
already knew twice in one day. Earlier he wrote "large prime"
where he clearly meant "large integer". I trust he will take
this post in the spirit in which it is intended.
--
--Bryan

[Mike C. Fletcher]

Bryan Olson wrote:
....

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.

There's a module here:
http://www.vrplumber.com/programming/
which provides two implementations of topological sorting in Python.
With that, should be a trivial task to do a dependency sort on the OP's
graph.

HTH,
Mike

________________________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://www.vrplumber.com
http://blog.vrplumber.com

[Heiko Wundram]

Am Donnerstag, 12. August 2004 08:22 schrieb Bryan Olson:

I'm sure Heiko actually knew this, but being the kind of smart-
ass I am, I can't resist the chance to correct him on things he
already knew twice in one day. Earlier he wrote "large prime"
where he clearly meant "large integer". I trust he will take
this post in the spirit in which it is intended.

I bow before the master. ;-)

Heiko.

[Heiko Wundram]

Am Donnerstag, 12. August 2004 08:34 schrieb Heiko Wundram:

I bow before the master. ;-)

No, but seriously, I guess I shouldn't be the one to teach computer science or
maths... I'm much better at "real" programming. And that's why Python is so
much fun: just try it out and see... :-)

Heiko.
(who is currently writing his first big exams in medicine)

[Paul Rubin]

ky******@gmail.com (Kyle Root) writes:

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. :)

Suppose that deps list is for file5. I'm reading your example to mean
file5 depends on file10, file7, and file3, and not the other way around.

As others have mentioned, what you want to do is called topological
sorting. Since nobody's described the algorithm, it goes something
like this:

1) Make a dictionary indexed by filename, whose entry deps[f] will
be the set of files f depends on. In the above example,
deps["file5"] = Set(["file10", "file7", "file3"]). You can
also use a dict instead of a Set in the obvious way.

1) Make another dictionary indexed by filename, whose entry d[f] for
filename f will be a list of the files that depend on f. For
example, if the deps for file5 are ("file10","file7","file3"), then
you'll put "file5" into d["file10"], d["file7"], and d["file3"].
You can straightforwardly build this dict when you scan the deps lists.

2) Also when you scan the deps lists, make a list U of all the files
that don't depend on anything.

3. while U is not empty, do the following:
choose an f from U
output f
remove f from U
for g in d[f]: # for each file depending on f
remove f from deps[g]
if deps[g] is now empty, add g to U

If there are no circular dependencies and if I haven't goofed up (it's
late here), then the above scheme should output all the filenames in
topologically sorted order, in running time linear in the # of
filenames plus the # of dependencies.

You can probably find a clearer explanation in any intro CS text with
a chapter about graph algorithms.

[Kyle Root]

Well thank you all that helps very much, I should have this done soon :D
And also thanks to Paul Foley who sent me tha topological sorter :)

[Paul McGuire]

"Kyle Root" <ky******@gmail.com> wrote in message
news:6c**************************@posting.google.c om...

I'm working on a little practice program, but I've become stuck and am
now utterly confused :?

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.
:)

I've been thinking about this for a few days but I always get lost.
So far I have a has_deps(filename) function, and not much else. I get
stuck on the actual changing the files from the random jumble to a
into a nice orderly list of files. One problem that I can't
overcome is when I'm a couple of deps in and I finally get to the
files that don't require anything, I have no way of getting back to do
the parent file's other deps. (Does that make any sense?)

Basically I was wondering if anyone had any tips or pointers, or knew
of any dependency resolving algorithms...

Thanks,
Kyle

Look into using pydot if you want to actually draw the trees/graphs.

-- Paul