Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Dependency graph
Summary
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.
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.
In a dependency graph, the 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.
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.