What is the benefit of being able to map a system's dependencies as a DAG (directed acyclic graph)?

Question

If I were to organize a collection of objects' dependencies into a DAG, in what situations would that be more desirable than another data structure such as a BDD (binary decision diagram)?

Answer 1

The DAG has a couple of properties which are ideal for analyzing dependencies.

First, you can easily identify the 'base level' components of your system. Those are the nodes in the DAG with no edges going into them. Knowing the relative layers of your system means you know the impact of refactorings. (Everything down the chain.)

Second, if you can produce a DAG you know that the system has no strange inter-dependencies. Cycles in the dependency graph would mean that you have two components which rely on one another -- a recipe for strange bugs and build errors. At Microsoft we used a tool called asmmeta to work around this issue.

Answer 2

I am not very knowledgeable about binary decision diagrams, but wikipedia seems to state that they are fundamentally directed, acyclic, graphs. I know a bit about DAGs. If you can represent your problem as a DAG you can ensure you don't have any cycles (as Chris Smith mentioned earlier).

Another attribute of a binary decision tree which may (or may not) be relevant here is that they are binary. However, I'm not sure how you would like to model your problem to a binary decision diagram. It looks like BDDs have zero, one or two choices at each node. I'm having a difficult time seeing how I would map dependencies to this. Mapping dependencies into a graph make a lot more sense to me.

Mainly, I think it just depends on what algorithms you want to run on your representation. If you are unsure you have a DAG, you can run a cycle detection algorithm to tell you if it is or not. If you want to find shortest paths, you can run Dijkstra's on it. I think this really depends on what you want to do, and I know things you can do with a general graph, which mainly involve proving it's a DAG. Once you've got a DAG, most of the things I would like to establish have been established. That's just me though.

-Brian J. Stinar-