Dependency Graphs

When architecting an application, it can be helpful to consider your dependency graph. This page outlines the general concepts of dependency graphs with the intent of defining terms, concepts, and properties that can be used to better reason about your dependency graph. If you manage your dependency graph carefully, you can ensure a cleaner codebase as well as take advantage of build time optimizations like parallel module builds, compile avoidance, etc. This page is intended as a primer for future pages about how to consider your dependency graph when architecting a codebase.

Assumed Prior Knowledge

To understand this page, it is expected that you know

• Some basic graph theory definitions:
  • What a graph is,
  • what a directed graph is, and
  • what a directed acyclic graph is (which would include the definition of a cycle).

Reading through the linked wikipedia pages should sufficient, assuming I've written the rest of this page well enough. Understanding other graph theory definitions and concepts (especially those specific to directed acyclic graphs) will be helpful, but I'll try to explain them where necessary.

Assumptions of This Page

Here are the base assumptions I'll be making

• I'll be assuming that we are using a compiled language.
• A module cannot compile unless all the modules it depends on have compiled.
• The number of modules is finite¹.

What is a Dependency Graph

In the broadest sense, a dependency graph is a mapping of how areas of your code are interconnected. To better define a dependency graph, we'll first need to define what we mean by "areas of your code", which we'll call "modules". Let's define a module as a collection of code that compiles together into a well-defined component. Gradle modules should directly align with the content here, but in general (perhaps with some small alterations in assumptions) a module could be a file, a class, a package, etc.

A dependency in our code occurs when one module must "know" about the details of another module. If module A must "know" about the details of module B, then we say that A depends on B and that B is a dependency of A. Often these dependencies will be explicit, such as in the dependencies block of a build.gradle file.

The dependency graph of a collection of modules is the directed acyclic graph where the nodes represent the modules, and an edge is drawn from node A to node B if and only if A depends on B. Here's a toy example that will be used throughout the rest of this page:

In this dependency graph Application Module depends on the modules Feature A and Feature B, Feature B depends on Library D and Library E, Library E has no dependencies, etc.

Why is the Dependency Graph Acyclic?

The directedness of our dependency graphs arises naturally from the nature of dependencies: if module A depends on module B, then A needs to know about details of B, but B need not know that A even exists. However, the necessity of the graph being acyclic may be less obvious.

To explore what it would mean to allow cycles in our dependency graph, let's first consider 1-cycles. A 1-cycle would just mean that a module is dependent on itself. We could argue that the module already inherently dependent on itself in a way (the module must "know" about its own code). However, if we tried to explicitly declare a dependency on itself, then by our assumptions, we need it to compile before it can compile, which is clearly nonsense.

Expanding to larger cycles, consider two modules, A and B, which both depend on each other, forming a 2-cycle:

Suppose you attempt to compile module A. Since module A depends on module B, we need to compile module B first. But module B depends on A, so to compile B we need to first compile A. So, which module actually gets compiled first? There's no valid answer, so we cannot begin the compilation.

For any cycle larger than 2, we can follow the same logic to find that there is no module in the cycle that can be compiled first. Thus, we cannot allow a cycle of any size in a dependency graph.

Useful properties of Directed Acyclic Graphs (DAGs)

Since dependency graphs are directed acyclic graphs (DAGs), it is helpful to define some terms and concepts from graph theory that will help us.

Walks/Paths

A walk from node A to node B along a directed graph is a sequence of edges where the first edge starts at A, each subsequent edge starts at the node where the previous edge ended, and the final edge ends at B. One can conceptually think of this as literally standing on node A and walking along the directed edges from node to node until they reach node B. In a DAG, all walks are also paths, which have the additional feature that no node (or edge, for that matter) will be visited more than once. The length of a walk/path is the number of edges in that walk/path

Height

The height of a node in a directed acyclic graph is the maximum length of all paths that start at that node. In a dependency graph, the height of a module is the largest number of modules that must compile in serial before that module can compile. The height of a directed acyclic graph is the maximum height among the nodes in that graph. This measure has build-time implications in a system that is capable of parallel compilation.

Reachability

A node \(B\) is reachable from a node \(A\) if there exists a path from \(A\) to \(B\). In this case, we can apply the notation \(A\leq B\) as a partial ordering. Note that reachability is transitive, i.e. \(A\leq B\) and \(B\leq C\) implies \(A \leq C\) (just concatenate the path from \(A\) to \(B\) and the path from \(B\) to \(C\) to get a path from \(A\) to \(C\)). An important feature of reachability in a dependency graph is that if \(A \leq B\), then \(B\) must compile before \(A\).

Degree and Reach

The in-degree of a node in a directed graph is the number of edges that point directly to that node. In a dependency graph, the in-degree is the number of modules that directly depend on the given module.

The in-reach² of a node is the number of nodes from which it is reachable. In a dependency graph, the in-reach of a node is the number of modules that cannot compile until that node has compiled

The out-degree of a node in a directed graph is the number of edges that point away from that node. The out-degree is the number of modules on which the given module directly depends.

The out-reach² of a node is the number of nodes that are reachable from it. In a dependency graph, the out-reach of a node is the number of modules that must compile before that node can compile.

Page History

• 2026-09-02 3e1424a Bump mkdocs-mermaid2-plugin from 1.2.1 to 1.2.3 (#14)