Dependency graph

Last updated

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

A depends on B and C; B depends on D Dependencygraph.png
A depends on B and C; B depends on D

Given a set of objects and a transitive relation with modeling a dependency "a depends on b" ("a needs b evaluated first"), the dependency graph is a graph with 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 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 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, 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 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 and so that will be evaluated before , then must not depend on .

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: [1] :12

Then the string consisting of the vertex labels ordered by a correct evaluation order corresponds to a string of a trace.

The monoidal operation takes the disjoint union 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, [1] :14

The identity is the empty graph.

Examples

Dependency graphs are used in:

Dependency graphs are one aspect of:

See also

Related Research Articles

<span class="mw-page-title-main">Catenary</span> Curve formed by a hanging chain

In physics and geometry, a catenary is the curve that an idealized hanging chain or cable assumes under its own weight when supported only at its ends in a uniform gravitational field.

<span class="mw-page-title-main">Feynman diagram</span> Pictorial representation of the behavior of subatomic particles

In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduced the diagrams in 1948. The interaction of subatomic particles can be complex and difficult to understand; Feynman diagrams give a simple visualization of what would otherwise be an arcane and abstract formula. According to David Kaiser, "Since the middle of the 20th century, theoretical physicists have increasingly turned to this tool to help them undertake critical calculations. Feynman diagrams have revolutionized nearly every aspect of theoretical physics." While the diagrams are applied primarily to quantum field theory, they can also be used in other areas of physics, such as solid-state theory. Frank Wilczek wrote that the calculations that won him the 2004 Nobel Prize in Physics "would have been literally unthinkable without Feynman diagrams, as would [Wilczek's] calculations that established a route to production and observation of the Higgs particle."

<span class="mw-page-title-main">Genus (mathematics)</span> Number of "holes" of a surface

In mathematics, genus has a few different, but closely related, meanings. Intuitively, the genus is the number of "holes" of a surface. A sphere has genus 0, while a torus has genus 1.

<span class="mw-page-title-main">Quadratic function</span> Polynomial function of degree two

In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before the 20th century, the distinction was unclear between a polynomial and its associated polynomial function; so "quadratic polynomial" and "quadratic function" were almost synonymous. This is still the case in many elementary courses, where both terms are often abbreviated as "quadratic".

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

<span class="mw-page-title-main">Lattice model (physics)</span>

In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime. Lattice models originally occurred in the context of condensed matter physics, where the atoms of a crystal automatically form a lattice. Currently, lattice models are quite popular in theoretical physics, for many reasons. Some models are exactly solvable, and thus offer insight into physics beyond what can be learned from perturbation theory. Lattice models are also ideal for study by the methods of computational physics, as the discretization of any continuum model automatically turns it into a lattice model. The exact solution to many of these models includes the presence of solitons. Techniques for solving these include the inverse scattering transform and the method of Lax pairs, the Yang–Baxter equation and quantum groups. The solution of these models has given insights into the nature of phase transitions, magnetization and scaling behaviour, as well as insights into the nature of quantum field theory. Physical lattice models frequently occur as an approximation to a continuum theory, either to give an ultraviolet cutoff to the theory to prevent divergences or to perform numerical computations. An example of a continuum theory that is widely studied by lattice models is the QCD lattice model, a discretization of quantum chromodynamics. However, digital physics considers nature fundamentally discrete at the Planck scale, which imposes upper limit to the density of information, aka Holographic principle. More generally, lattice gauge theory and lattice field theory are areas of study. Lattice models are also used to simulate the structure and dynamics of polymers.

In mathematics, an expression is a written arrangement of symbols following the context-dependent, syntactic conventions of mathematical notation. Symbols can denote numbers (constants), variables, operations, functions. Other symbols include punctuation signs and brackets.

In physics, the Brans–Dicke theory of gravitation is a competitor to Einstein's general theory of relativity. It is an example of a scalar–tensor theory, a gravitational theory in which the gravitational interaction is mediated by a scalar field as well as the tensor field of general relativity. The gravitational constant is not presumed to be constant but instead is replaced by a scalar field which can vary from place to place and with time.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

1/<i>N</i> expansion Perturbative analysis of quantum field theories

In quantum field theory and statistical mechanics, the 1/N expansion is a particular perturbative analysis of quantum field theories with an internal symmetry group such as SO(N) or SU(N). It consists in deriving an expansion for the properties of the theory in powers of , which is treated as a small parameter.

In mathematics, a change of variables is a basic technique used to simplify problems in which the original variables are replaced with functions of other variables. The intent is that when expressed in new variables, the problem may become simpler, or equivalent to a better understood problem.

The Kuramoto model, first proposed by Yoshiki Kuramoto, is a mathematical model used in describing synchronization. More specifically, it is a model for the behavior of a large set of coupled oscillators. Its formulation was motivated by the behavior of systems of chemical and biological oscillators, and it has found widespread applications in areas such as neuroscience and oscillating flame dynamics. Kuramoto was quite surprised when the behavior of some physical systems, namely coupled arrays of Josephson junctions, followed his model.

In category theory, monoidal functors are functors between monoidal categories which preserve the monoidal structure. More specifically, a monoidal functor between two monoidal categories consists of a functor between the categories, along with two coherence maps—a natural transformation and a morphism that preserve monoidal multiplication and unit, respectively. Mathematicians require these coherence maps to satisfy additional properties depending on how strictly they want to preserve the monoidal structure; each of these properties gives rise to a slightly different definition of monoidal functors

In mathematics, a first-order partial differential equation is a partial differential equation that involves only first derivatives of the unknown function of n variables. The equation takes the form

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.

In mathematical physics the Knizhnik–Zamolodchikov equations, or KZ equations, are linear differential equations satisfied by the correlation functions of two-dimensional conformal field theories associated with an affine Lie algebra at a fixed level. They form a system of complex partial differential equations with regular singular points satisfied by the N-point functions of affine primary fields and can be derived using either the formalism of Lie algebras or that of vertex algebras.

The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.

In mathematics, the Butcher group, named after the New Zealand mathematician John C. Butcher by Hairer & Wanner (1974), is an infinite-dimensional Lie group first introduced in numerical analysis to study solutions of non-linear ordinary differential equations by the Runge–Kutta method. It arose from an algebraic formalism involving rooted trees that provides formal power series solutions of the differential equation modeling the flow of a vector field. It was Cayley (1857), prompted by the work of Sylvester on change of variables in differential calculus, who first noted that the derivatives of a composition of functions can be conveniently expressed in terms of rooted trees and their combinatorics.

In mathematical analysis and its applications, a function of several real variables or real multivariate function is a function with more than one argument, with all arguments being real variables. This concept extends the idea of a function of a real variable to several variables. The "input" variables take real values, while the "output", also called the "value of the function", may be real or complex. However, the study of the complex-valued functions may be easily reduced to the study of the real-valued functions, by considering the real and imaginary parts of the complex function; therefore, unless explicitly specified, only real-valued functions will be considered in this article.

Lagrangian field theory is a formalism in classical field theory. It is the field-theoretic analogue of Lagrangian mechanics. Lagrangian mechanics is used to analyze the motion of a system of discrete particles each with a finite number of degrees of freedom. Lagrangian field theory applies to continua and fields, which have an infinite number of degrees of freedom.

References

  1. 1 2 Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN   981-02-2058-8 . Retrieved 18 April 2021.
  2. Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.
  3. Keval Vora; Rajiv Gupta; Guoqing Xu (2017). "KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations". In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17). pp. 237–251. doi: 10.1145/3093337.3037748 .
  4. Gilbert, Ron. "Puzzle Dependency Charts". Grumpy Gamer. Retrieved 11 January 2020.