Dependency graph
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph. Definition. Given a set of objects formula_1 and a transitive relation formula_2 with formula_3 modeling a dependency ""a" depends on "b"" (""a" needs "b" evaluated first"), the dependency graph is a graph formula_4 with formula_5 the transitive reduction of "R". For example, assume a simple calculator. This calculator supports assignment of constant  values to variables and assigning the sum of exactly two variables to a third variable. Given several equations like ""A" = "B"+"C"; "B" = 5+"D"; "C"=4; "D"=2;", then formula_6 and formula_7. You can derive this relation directly: "A" depends on "B" and "C", because you can add two variables if and only if you know the values of both variables. Thus, "B" must be calculated before "A" can be calculated. However, the values of "C" and "D" are known immediately, because they are number literals. Recognizing impossible evaluations. In a dependency graph, the cycles of dependencies (also called circular dependencies ) lead to a situation in which no valid evaluation order exists, because none of the objects in the cycle may be evaluated first. If a dependency graph does not have any circular dependencies, it forms a directed acyclic graph, and an evaluation order may be found by topological sorting. Most topological sorting algorithms are also capable of detecting cycles in their inputs; however, it may be desirable to perform cycle detection separately from topological sorting in order to provide appropriate handling for the detected cycles. Assume the simple calculator from before. The equation system ""A"="B"; "B"="D"+"C"; "C"="D"+"A"; "D"=12;" contains a  circular dependency formed by "A", "B" and "C", as "B" must be evaluated before "A", "C" must be evaluated before "B" and "A" must be evaluated before "C". Deriving an evaluation order. A correct evaluation order is a numbering formula_8 of the objects that form the nodes of the dependency graph so that the following equation holds: formula_9 with formula_10. This means, if the numbering orders two elements formula_11 and formula_12 so that formula_11 will be evaluated before formula_12, then formula_11 must not depend on formula_12. There can be more than one correct evaluation order. In fact, a correct numbering  is a topological order, and any topological order is a correct numbering. Thus, any algorithm that derives a correct topological order derives a correct evaluation order. Assume the simple calculator from above once more. Given the equation system ""A" = "B"+"C"; "B" = 5+"D"; "C"=4; "D"=2;", a correct evaluation order would be ("D", "C", "B", "A"). However, ("C", "D", "B", "A") is a correct evaluation order as well. Monoid structure. An acyclic dependency graph corresponds to a trace of a trace monoid as follows: Then the string consisting of the vertex labels ordered by a correct evaluation order corresponds to  a string of a trace. The monoidal operation formula_23 takes the disjoint union formula_24 of two graphs' vertex sets, preserves the existing edges in each graph, and draws new edges from the first to the second where the dependency relation allows, The identity is the empty graph. Examples. Dependency graphs are used in: Dependency graphs are one aspect of: