Dependency graph

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 ${\displaystyle n:S\to \mathbb{N}}$ of the objects that form the nodes of the dependency graph so that the following equation holds: ${\displaystyle n(a)<n(b)\Rightarrow (a,b)\notin R}$ with ${\displaystyle a,b\in S}$. This means, if the numbering orders two elements ${\displaystyle a}$ and ${\displaystyle b}$ so that ${\displaystyle a}$ will be evaluated before ${\displaystyle b}$, then ${\displaystyle a}$ must not depend on ${\displaystyle b}$.

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:

• A function ${\displaystyle \varphi :S\to \mathrm{\Sigma }}$ labels each vertex with a symbol from the alphabet ${\displaystyle \mathrm{\Sigma }}$
• There is an edge ${\displaystyle a\to b}$ or ${\displaystyle b\to a}$ if and only if ${\displaystyle (\varphi (a),\varphi (b))}$ is in the dependency relation ${\displaystyle D}$.
• Two graphs are considered to be equal if their labels and edges correspond.

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

The monoidal operation ${\displaystyle (S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)}$ takes the disjoint union ${\displaystyle S_{12}=S_1\bigsqcup S_2}$ 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,

${\displaystyle R_{12}=R_1\bigsqcup R_2\bigsqcup \{(a,b)\mid a\in S_1\wedge b\in S_2\wedge (\varphi (a),\varphi (b))\in D\}}$

The identity is the empty graph.

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 Unix Make, Node npm install, php composer, Twitter bower install, 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.
• Dynamic graph analytics: GraphBolt and KickStarter capture value dependencies for incremental computing when graph structure changes.
• 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 used in alarm correlation approaches for tracing the impact or propagation of network attacks through the network. This approach exploits the spatio-temporal attributes of alarms and the dependencies between network devices, which are modeled as a network dependency graph. Given that false alarms generated by an intrusion detection system (IDS), for example, may produce incorrect dependency relationships, entropy-based measures can be applied to mitigate the uncertainty introduced by false alarms in the identification of attack impact or propagation paths.
• Video games, especially puzzle and adventure video games, which are frequently designed as a graph of dependent relationships between in-game actions.

Dependency graphs are one aspect of:

• Manufacturing plant types: Raw materials are processed into products via several dependent stages.
• Job shop scheduling: A collection of related theoretical problems in computer science.