Dependency Graph

Dependency Graph

A dependency graph is a data structure formed by a directed graph that describes the dependency of an entity in the system on the other entities of the same system. The underlying structure of a dependency graph is a directed graph where each node points to the node on which it depends.

Some dependency graphs can have conditions set on the different connections between the nodes. The root node of the dependency graph is called the entrypoint.

Dependency graphs have many applications in software engineering. Package managers use dependency graphs to pin versions of packages and bundlers to identify resources to bundle together.

What is dependency resolution?

Dependency resolution is the process of identifying the numbering of nodes. The numbering must comply with two rules:

• Each node has a unique number after resolution.
• All the dependencies of a node have numbers lower than the node itself.

There may be more than one way to number the nodes, and each is equally valid.

‍

‍

In this example, node A depends on B; B depends on both C and D; D depends on E. Thus, C and E are the independent nodes and will take the initial positions. For the above graph, all the following resolutions are valid:

• E, D, C, B, A
• E, C, D, B, A
• C, E, D, B, A

On the flip side, there is a possibility that such a resolution is not possible. A dependency graph may become unresolvable due to cyclic dependencies or conditions on the connections that lack any solution satisfying them.

‍

‍

In this example, A depends on B, which depends on C, which depends on A. Here, resolution fails as there is no independent node to be evaluated first.

‍

‍

Here, both B and C depend on two different versions of D. Here, again, no resolution can be reached as no version of D satisfies the requirements imposed on the connections BD and CD.