Arranging a dependency tree

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