**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 GraphSearch.

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

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.

Related publications (7)

Related people (1)

Related concepts (2)

Related courses (3)

Related lectures (14)

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 directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

Directed acyclic graph

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 (also called arcs), 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.

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

Graph Pattern Matching: Work-sharing

Explores optimizing graph pattern matching with work-sharing techniques and context-aware parallelization for pattern mining at scale.

Graph-to-Graph Transformers: Syntax-aware Graph Encoding

Introduces the Syntax-aware Graph-to-Graph Transformer architecture for effective conditioning on syntactic dependency graphs.

Lovasz Local Lemma: Dependencies and Independence

Covers the Lovasz Local Lemma, 'small dependencies', dependency graphs, and conditions for valid solutions.

Natural language processing has experienced significant improvements with the development of Transformer-based models, which employ self-attention mechanism and pre-training strategies. However, these models still present several obstacles. A notable issue ...

Unsupervised graph representation learning aims to learn low-dimensional node embeddings without supervision while preserving graph topological structures and node attributive features. Previous Graph Neural Networks (GNN) require a large number of labeled ...

Simon Bliudze, Anastasia Mavridou

JavaBIP allows the coordination of software components by clearly separating the functional and coordination aspects of the system behavior. JavaBIP implements the principles of the BIP component framework rooted in rigorous operational semantics. Recent w ...