Dependency Graphs

Many concepts in the deps.cloud ecosystem stem from graph theory.

When we think about dependencies, our first thought is often of a tree. These trees stem from the projects that we work on day to day, each with its own set of branches. As our projects pull in dependencies, their trees can grow… and grow… and grow. In practice, this tree is more of a graph (technically a tree is a type of graph with a few special characteristics).

Graphs are a data structure used to model relationships between objects. They consist of nodes (entities) and edges (associations).

Graphs can be either directed or undirected. Edges in undirected graphs simply connect two nodes, such as x and y. Edges in directed graphs start at x and end at y, indicating a direction to the edge. You can only traverse directed edges in their associated direction (i.e. from x to y).

Graphs can be acyclic, meaning they contain no cycles; or they can be cyclic, meaning they have cycles.

Dependency graphs are directed graphs that represent dependencies between objects. This data structure is at the heart of deps.cloud. Most software we write requires some kind of dependency. These dependencies come in many shapes and forms, but the ones we’re most familiar with are libraries. To demonstrate, let us consider an example.

• Application A uses library B
• Library B needs libraries C and D
• Library C also depends on library D

Visually, the dependency graph for such a system would look like:

While our example is small, real world cases often grow in size and complexity. The more complex the structure gets, the harder it can be to make changes to it. As it grows in size, it can be difficult to track all the open source software you use.

deps.cloud helps companies understand their software dependency graph.