Dependency graph

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.

Contents

Definition

Dependencygraph.png

Given a set of objects S and a transitive relation R = S \times S with (a,b) \in R modeling a dependency "a needs b evaluated first", the dependency graph is a graph G = (S,T) with T \subseteq R 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 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 if and only if you know the values of both variables. Thus, B and C must be calculated before A can be calculated. However, D's 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 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  n : S \rightarrow N of the objects that form the nodes of the dependency graph so that the following equation holds:  n(a) < n(b) \Rightarrow (a, b) \notin R with  a, b \in S. 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.

Examples

Dependency graphs are used in:

  • Automated software installers. They walk the graph looking for software packages that are required but not yet installed. The dependency is given by the coupling of the packages.
  • Software build scripts such as the Unix Make system or Apache Ant. They need to know what files have changed so only the correct files need to be recompiled.
  • In Compiler technology and formal language implementation:
  • Instruction Scheduling. Dependency graphs are computed for the operands of assembly or intermediate instructions and used to determine an optimal order for the instructions.
  • Dead code elimination. 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 XForms to know what visual elements to update if data in the model changes.

Dependency graphs are one aspect of:

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Dependency grammar — Hybrid constituency/dependency tree from the Quranic Arabic Corpus Dependency grammar (DG) is a class of syntactic theories developed by Lucien Tesnière. It is distinct from phrase structure grammars, as it lacks phrasal nodes. Structure is… …   Wikipedia

  • Dependency diagram — A dependency diagram is a visual representation of a dependency graph. Dependency diagrams are integral to software development, outlining the complex, interrelationships of various functional elements. Typically in a dependency diagram, arrows… …   Wikipedia

  • Dependency network — Contents 1 Importance 2 Overview 3 The activity dependency networks …   Wikipedia

  • Dependency Structure Matrix — A Dependency Structure Matrix, or DSM (also referred to as Dependency Structure Method, Design Structure Matrix, Problem Solving Matrix (PSM), incidence matrix, N square matrix or Design Precedence Matrix), is a compact, matrix representation of… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • Long-range dependency — A self similar phenomenon behaves the same when viewed at different degrees of magnification, or different scales on a dimension (space or time). Self similar processes can be described using heavy tailed distributions, also known as long tailed… …   Wikipedia

  • Signal-flow graph — A signal flow graph (SFG) is a special type of block diagram[1] and directed graph consisting of nodes and branches. Its nodes are the variables of a set of linear algebraic relations. An SFG can only represent multiplications and additions.… …   Wikipedia

  • Instruction scheduling — In computer science, instruction scheduling is a compiler optimization used to improve instruction level parallelism, which improves performance on machines with instruction pipelines. Put more simply, without changing the meaning of the code, it …   Wikipedia

  • Syntactic methods — In software engineering, syntactic methods are techniques for developing correct software programs. The techniques attempt to detect, and thus prevent, certain kinds of defects (bugs) by examining the structure of the code being produced at its… …   Wikipedia

  • Artificial neural network — An artificial neural network (ANN), usually called neural network (NN), is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”