According to Wikipedia:

That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.

Is this by design, or is this simply the byproduct of the following:

DAGs may be used to model several different kinds of structure in mathematics and computer science. A collection of tasks that must be ordered into a sequence, subject to constraints that certain tasks must be performed earlier than others, may be represented as a DAG with a vertex for each task and an edge for each constraint;

I'm a programmer, but my math skills are not stellar. I'm trying to understand if there is a use case for this feature in my field. On the Game Development Stack Exchange it was suggested this would be a good approach for modeling conversations with NPCs. However, I find that many times in games (especially RPGs) conversations will loop and create a directed cycle.

  • 1
    $\begingroup$ It is design only in the sense we cannot allow directed cycles in the the graph if we call it a directed acyclic graph. :) More seriously, if the concept of a DAG is too restrictive for you, why don't you consider modeling using plain "directed graphs" (digraphs). They are allowed to have cycles... $\endgroup$ – Srivatsan Sep 19 '11 at 15:53
  • $\begingroup$ @SrivatsanNarayanan What's actually funny is that is basically what I was trying to get at :) So, for example, while you're describing a graph model of data, it is more likely you would "discover" it to have no directed cycles (acyclic), then to say, "Hey, I need a graph with no directed cyles." I hope that makes sense. $\endgroup$ – user16349 Sep 19 '11 at 16:14

There are situations where acyclicity is a very desirable phenomenon. For example, consider a "dependency graph", where the presence of the edge $A \to B$ means that you need $A$ to get $B$. Such graphs arise naturally in many contexts:

  • In an adventure game, actions often have preconditions. For example, to enter the shed you might need to open the rusty lock. To open the rusty lock, you might need the key and some oil. To get the key, you might need a stick and some chewing gum, and so on. You can express such dependencies as a DAG, as in $\{\text{stick}\to\text{key}$, $\text{gum}\to\text{key}$, $\text{key}\to\text{lock}$, $\text{oil}\to\text{lock}$, $\text{lock}\to\text{shed}\}$.
  • Similarly, strategy games often have a "tech tree" (which should really be called a "tech DAG", since in most games it isn't a tree), a graph that indicates which precursor technologies are needed in order to develop a more advanced technology or unit. In this case, a drawing of the actual graph is often presented to the players in the game documentation.
  • When installing software, a program might require the presence of some libraries (or other programs), which might in turn require other libraries or programs. The graph of such dependencies forms a DAG. A good package management tool will traverse that graph and automatically install all the required programs and libraries for you.
  • Similarly, when compiling a program, different class or source files often depend on each other, so that when one of them is changed, several others need to be recompiled as well. Again, a natural representation of such dependencies is often a DAG.

In many of these situations, having a cyclic dependency means trouble. For example, if the player needs oil to get into the shed, and must enter the shed in order to find some oil, then they (and probably the game designer too) have a problem. Or if the tech tree says you need coal to develop steelmaking and steel to develop coal mining, clearly there's something wrong. And I'm sure, even with the most careful package management, most of us have sometimes been in a situation where you, say, need to download a driver to get your network connection to work, but can't download the driver without a working network connection.

Of course, in some cases cyclic dependencies can be resolved: for example, if two class files in a program depend on each other, it may just mean that, when either of them is changed, you need to recompile both. But that only works if you know that you can somehow recompile them simultaneously — or at least that, if you keep recompiling them one by one, over and over, eventually the output will stop changing. Generally, resolving such cycles (when it's not just done by ad hoc kluges) involves somehow merging and/or breaking up the tasks in the cycle so that they no longer form a cycle.

Another way to resolve a cyclic dependency is by finding some alternative way to satisfy at least one set of preconditions. For example, you might be able to install the network driver off a flash drive if you can't download it directly, or a player might be able to open the door to the shed with a crowbar instead. It's worth noting that ordinary DAGs can't represent such alternative requirement sets (like "opening the lock requires either oil and the key or a crowbar" or "getting the key requires a stick and either gum or duct tape") very well; for such requirements, you need more advanced representations.

  • $\begingroup$ These are excellent examples! Thanks for keeping the discussion focused around games. That helped considerably. $\endgroup$ – user16349 Sep 19 '11 at 19:29

A directed acyclic graph has no cycles because if it did, it wouldn't be a directed acyclic graph. It's just a definition.

As for use cases, they crop up all over the place. For instance, in this Latin Square completion algorithm I posted here a few days ago. Also, optimising compilers are full of them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy