Was ist der Vorteil der Lage zu sein, eines Systems Abhängigkeiten als DAG (gerichteter azyklischer Graph) abzubilden?

Question

Wenn ich eine Sammlung von Objekten Abhängigkeiten in einem DAG zu organisieren, in welchen Situationen, so dass wünschenswerter sein als eine andere Datenstruktur würde als BDD (binäres Entscheidungsdiagramm)?

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-