The theory of dependency graphs

We are going to extend what we learned with the previous chapter when constructing a conversation graph, and with a few (but significant) changes, create a quest dependency graph that will store the completion state of its corresponding tasks. A dependency graph is essentially a directed graph representing dependencies of several objects with each other. The key difference of this graph from the conversation graph is that the dependency graph does not contain any cycles. A graph with circular dependencies would lead to a situation where no valid evaluation order exists, since none of the vertices can be evaluated first. Without cycles in a graph, we will end up using a directed acyclic graph (DAG).

As explained later, we will make sure that we check for cycles every time we add a new dependency, and if any of them are found, disregard that particular dependency.

The following diagram (Figure 2) represents a sample dependency graph with four total vertices...