In mathematics and computer science, a dependency graph is a directed graph representing dependencies of several objects towards each other. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Mathematics and Computer science, a graph is the basic object of study in Graph theory. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph.
Contents |
Definition
Given a set of objects S and a transitive relation R = 
with 
modeling a dependency "a needs b evaluated first", the dependency graph is a graph G = (S, T) with 
and R being the transitive closure of T. In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b In Mathematics, the transitive closure of a Binary relation R on a set X is the smallest Transitive relation on X
For example, assume a simple calculator. This calculator supports assignment of constant values to variables and assigning the sum of exactly 2 variables to a third variable. Given several equations like "A = B+C; B = 5+D; C=4; D=2;", then S = A,B,C,D and R = (A,B),(A,C),(B,D). You can derive this relation directly - A depends on B and C, because you can add two variables only if and only if you know the values of both variables, thus, B and C must be calculated before A can be calculated. ↔ However, Ds value is known immediately, because it is a number literal. (TODO: add image for first graph. )
Recognizing Impossible Evaluations
In a dependency graph, impossible calculations form cycles. Thus, such situations are called circular dependencies. There exist efficient algorithms for detecting those cycles, like Tortoise and Hare. Cycle detection is the Algorithmic problem of finding a cycle of the following type In Mathematics, for any function &fnof that maps a Finite For further information, refer to cycle detection. Cycle detection is the Algorithmic problem of finding a cycle of the following type In Mathematics, for any function &fnof that maps a Finite If one strives for efficiency, this cycle detection can be done during the derivation of an evaluation order. However, this increases the difficulty of outputting the objects in the cycle, for example for special treatment or usage in an error message.
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. (TODO: add little image)
Deriving an evaluation order
A correct evaluation order is a numbering 
of the objects that form the nodes of the dependency graph so that the following equation holds: 
with 
. This means, if the numbering orders two elements a and b so that a will be evaluated before b, then b must not depend on a. Furthermore, there can be more than a single correct evaluation order. In fact, a correct numbering is a topological order, and any topological order is a correct numbering. In Graph theory, a topological sort or topological ordering of a Directed acyclic graph (DAG is a linear ordering of its nodes in which each node comes 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.
Examples
Dependency graphs are used in:
- Automated software installers. Installation (or setup) of a program (including drivers is the act and the effect of putting the program in a computer system so that it can be They walk the graph looking for uninstalled but needed software packages. The dependency is given by the coupling of the packages. In Computer science, coupling or dependency is the degree to which each program module relies on each one of the other modules
- Dead code elimination. In Compiler theory, dead code elimination is a Compiler optimization that removes code that does not affect the program If no side effected operation depends on a variable, this variable is considered dead and can be removed.
- Spreadsheet calculators. They need to derive a correct calculation order similar to that one in the example used in this article.
- Cooking. One needs to wash the vegetables before putting them in the soup.
See also
References
- Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. A dependency diagram is a visual representation of a dependency graph. In Graph theory, a topological sort or topological ordering of a Directed acyclic graph (DAG is a linear ordering of its nodes in which each node comes A data dependency in computer science is a situation in which a program statement (instruction refers to the data of a preceding statement 261, Eighth Working Conference on Reverse Engineering (WCRE'01)
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic