Dependency Graphs

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

Graphs are a data structure used to model relationships between objects. They consist of nodes (entities) and edges (associations). Edges in a graph can be directed or undirected. Graphs can be acyclic, meaning they contain no cycles.

Dependency graphs are directed graphs that represent dependencies between objects. This data structure is at the heart of deps.cloud. To best explain, let us consider a simple example.

  • A depends on B
  • B depends on D
  • B depends on C
  • C depends on D

Conceptually, this looks something like the following.

Even with our simple example, we can start to see the complexity that comes with a dependency graph. Since edges often reference data between nodes of the same type, mapping concepts to traditional solutions can be difficult.

Graph traversal

Graph traversal refers to the process of walking and navigating a graph. They are similar to tree traversals, but require tracking nodes you’ve visited as it’s possible to encounter cycles. To simplify this for consumers, deps.cloud provides a search API for traversing it’s graph.

Breadth-first search (commonly abbreviated BFS) is an algorithm used to traverse tree and graph data structures. This approach often starts with a root node. The algorithm progresses by visiting neighbors of increasing depth, level by level.

Depth-first search (commonly abbreviated DFS) is another traversal algorithm. In this traversal, branches of the data structure are exhausted before backtracking. Unlike BFS, there are several possible orderings for the output of a DFS:

  • A preordering lists all nodes in the order they were first visit.
  • A postordering lists all nodes in the order they were last visited.
  • A reverse preordering lists all nodes in the opposite order they were first visit. This is not the same as a postordering.
  • A reverse postordering lists all nodes in the opposite order they were last visited. This is not the same as a preordering.

Next Steps

To learn more about how information is stored, head over to the data model documentation.

To learn about how information is extracted, head over to the manifest file documentation.


Last modified October 26, 2020: darken up lines (141fe72)