Dependency graph
Encyclopedia
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.
with 
modeling a dependency "a needs b evaluated first", the dependency graph is a graph 
with 
and R being the transitive closure
of T.
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
and 
. 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 and C must be calculated before A can be calculated. However, Ds value is known immediately, because it is a number literal.
, 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.
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 a must not depend on b. 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. 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.
Dependency graphs are one aspect of:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and digital electronics, a dependency graph is a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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 S and a transitive relationTransitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
with modeling a dependency "a needs b evaluated first", the dependency graph is a graph with and R being the transitive closureTransitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of T.
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
and . You can derive this relation directly: A depends on B and C, because you can add two variables if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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.
Recognizing impossible evaluations
In a dependency graph, 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 graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. 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...
, and an evaluation order may be found by topological sorting
Topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
. 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 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 a must not depend on b. Furthermore, there can be more than a single correct evaluation order.In fact, a correct numbering is a topological order
Topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
, 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.
Examples
Dependency graphs are used in:- Automated software installers. They walk the graph looking for software packagesSoftware package (installation)In package management systems, which are commonly used with Linux-based operating systems, a package is a specific piece of software which the system can install and uninstall....
that are required but not yet installed. The dependency is given by the couplingCoupling (computer science)In computer science, coupling or dependency is the degree to which each program module relies on each one of the other modules.Coupling is usually contrasted with cohesion. Low coupling often correlates with high cohesion, and vice versa...
of the packages. - Software build scripts such as the UnixUnixUnix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
Make system or Apache AntApache AntApache Ant is a software tool for automating software build processes. It is similar to Make but is implemented using the Java language, requires the Java platform, and is best suited to building Java projects....
. They need to know what files have changed so only the correct files need to be recompiled. - In CompilerCompilerA compiler is a computer program that transforms source code written in a programming language into another computer language...
technology and formal languageFormal languageA formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
implementation: - Instruction SchedulingInstruction schedulingIn computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines...
. Dependency graphs are computed for the operands of assembly or intermediate instructions and used to determine an optimal order for the instructions. - Dead code eliminationDead code eliminationIn compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important...
. 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.
- Web Forms standards such as XFormsXFormsXForms is an XML format for the specification of a data processing model for XML data and user interface for the XML data, such as web forms...
to know what visual elements to update if data in the model changes.
Dependency graphs are one aspect of:
- Manufacturing Plant Types. Raw materials are processed into products via several dependent stages.
- Job Shop SchedulingJob Shop SchedulingJob shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...
. A collection of related theoretical problems in computer science.