Definition
Wikipedia defines it as4:
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.
To be more precise, a dependency graph in software engineering is a directed acyclic graph - a directed graph with no cycles. In a module dependency graph, nodes represent modules and edges represent dependencies between modules.
A dependency graph in general can have more than one root. A root module (indgree = 0) is one on which no module depends on, and a leaf module (outdegree = 0) does not depend on any module.
Notation
Let’s say module A depends on module B (Figure 1), then there will be a directed edge shown by an arrow with its tail end at node A and its head at node B. Module A is said to be dependent on module B if A uses classes or methods of B. Module B does not know anything about A if it exists or not, however, A knows about B.
Why use module dependency graphs2?
The structure of your code’s module dependency graph greatly affects the build times
As the development of the code progresses, the module graph might become a list-like structure without someone noticing it
Gives an idea whether modules have clear separation of concerns and adhere to appropriate dependency structure
It is cheaper to prevent creating complicated module dependencies that would be difficult to fragment later
Unwanted module dependencies will pop up, if proper module structure is not implemented.
The following diagram shows the dependency graph of the older Kotlin multi-module architecture of mifos-wallet app (generated using Modules Graph Assert):
Significance of the Red Line
The red line represents the longest path in the graph from a root node to a leaf node. In Figure 2, the red line from the “:mifospay” module to the “:core:datastore-proto” module is the longest path from “:mifospay” module to any other module.
The path of the red line gives an idea about how good the modularization is. Ideally, a modularization is considered good if the red line does not pass through more than one module in the same layer, i.e., the modules in a layer are independent of each other.
In practice, the above scenario is rarely achieved. One strives for highly cohesive (self-contained) and loosely coupled modules. The loose coupling is meant to be among the modules in the same layer of the architecture. For example, let us look at the figures below (Figures 3-7 have been adapted from the talk by Josef Raska1):
Estimation of build time
This is a canonical application of topological sorting. The total build time of a project depends on scheduling of sequence of jobs or tasks (building each module) based on their dependencies5 as well as the build times of individual modules. See Appendix I for more details.
How do we improve modularization?
If an implementation depends on another implementation (as shown in Figure 4) then one should move the dependent part of the code into an API (see Figure 6). Similarly for other layers in the architecture, one can take such measures to enforce proper dependency structure.
One can use the above module rules to improve the bad module graph (Figure 4) as shown below:
Can “greatness” be achieved?
Yes definitely! Add interfaces for parts of the code of one module on which the other module is dependent on
One can use the Modules Graph Assert - a Gradle plugin, to analyze the dependency graph of the codebase to make sure the modularization is right on track as you keep adding new modules. It is always better to prevent any dreaded dependencies than to spend time refactoring them.
Beginner’s Dilemma
A naive question might arise in a beginning contributor’s mind: why build a module dependency graph using a library or a plugin since the developers of the project already know beforehand the dependencies of the new module they are creating. One can manually create the dependency graph, right? Not really!
In a project with just over ten modules, building the dependency graph might seem trivial but it’s not, as keeping track of the edges among modules is somewhat cumbersome. As a project matures, new features keep getting added as requirements arise.
The Real Problem
The problem here is that one can add any dependency with ease - just one line of code in the Gradle build file, and then one can use any class from any module from any layer since Android studio or any other IDE doesn’t prevent one from doing that. As Murphy’s law of dependencies states - Whatever they can access, they will access. And doing that makes the modules tightly coupled.
In reality, the graphs (see Figure 9) can become very complicated, difficult to keep track of the dependencies among modules let alone drawing them manually. The number of modules might increase linearly, however, the dependencies tend to grow much faster.
Advantages of generating a module dependency graph using a library or plugin, other than the technical ones:
Dependency graphs give new contributors a head start in learning the existing codebase quickly, since they don’t need to keep digging around the codebase to figure out the dependencies
It is easy to update dependency graphs whenever new modules get added quickly.
Apart from creating dependency graphs, Modules Graph Assert also has several features to improve modularization. It helps protect the architecture by keep it lean. One such feature is that one can set the max height of the tree with a root module. Fixing the max height makes sure that the graph tree doesn’t degenerate into a list.2
References:
https://www.droidcon.com/2022/11/15/modularization-flatten-your-graph-and-get-the-real-benefits/ - Talk by Josef Raska, author of Modules Graph Assert.
https://github.com/jraska/modules-graph-assert?tab=readme-ov-file
https://proandroiddev.com/module-rules-protect-your-build-time-and-architecture-d1194c7cc6bc
Appendix I
Estimation of build time
Build Time of Good Module Graph Example
Let’s estimate the build time for the example in “Good Module Graph” (Figure 3) using a diagram with simplified module names for a clean demonstration.
The valid topological sorts of the above graph are as follows:
For our purpose, the build path (reverse order of topological sort) can be represented as
E --> (B, C, D) --> A ,
Once module E is built, modules B, C, and D can be built in parallel followed by module A. The final build time of the modules built in parallel will depend on the module with the maximum build time among B, C and D.
Total build time = Build time of E + Max Build time of (B, C, D) + Build time of A
= 3 s + max(15 s, 10 s, 10 s) + 2 s
= 3 s + 15 s + 2 s = 20 s
Build Time of Bad Module Graph Example
Let’s estimate the build time for the example in “Bad Module Graph” (Figure 4) using a diagram with simplified module names for a clean demonstration.
In this case, there is only one valid topological sort, i.e., A, B, C, D, E and the total build time is given by
Total build time = Build Time of (E + D + C + B + A)
= 3 + 10 + 10 + 15 + 2 = 40 s