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 preciseIn software engineering, a dependency graph in software engineering is a directed acyclic graph - a directed graph with no cycles. In the context of 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 other module depends on, and a leaf module (outdegree = 0) is one that does not depend on any module.
Notation
Let’s say module A depends on module B (Figure 1), then there will be . In this case, a directed edge is 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 it uses classes or methods of from B. Module B does not know anything about A if it exists or not, however, While module B is unaware of module A’s existence, module A knows about module 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 may unintensionally evolve into 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 upemerge, if proper module structure is not implemented.
The following diagram below 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., meaning the modules in within a layer are independent of each otherone another.
In practice, the above achieving this scenario is rarely achievedrare. One strives should always strive for highly cohesive (self-contained) and loosely coupled modules. The loose coupling is meant to be Loose coupling should exist among the modules in within the same layer of the architecture. For example, let us let’s look at the figures below (Figures 3-7 have been , adapted from the a 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 should be moved into an API (see Figure 6). Similarly, for other layers in the architecture, one can take such measures similar measures can be taken to enforce a proper dependency structure.
One can use the above The module rules above can be applied to improve the bad “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 that another module is dependent depends on.
One You can use the Modules Graph Assert- , a Gradle plugin, to analyze the dependency graph of the codebase to make sure and ensure that the modularization is right stays on track as you keep adding add new modules. It is It’s always better to prevent any dreaded problematic dependencies than to spend time refactoring them later.
Beginner’s Dilemma
A naive common question might arise in a beginning contributor’s mindfrom a beginner might be: why build a module dependency graph using a library or a plugin since when the developers of the project already know beforehand the dependencies of the new module they are creating. One can manually create ? Can’t the dependency graph , rightbe created manually? 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 . Tracking the edges among between modules is somewhat can become cumbersome. As a the project matures , and new features keep getting added as requirements ariseare added to meet evolving requirements, this task become even more complex.
The Real Problem
The problem here is that one can add any dependency with ease - just adding dependencies is too easy—just one line of code in the Gradle build file, and then one you can use access any class from any module from , across any layer since . Since Android studio or any other IDE doesn’t prevent one from doing that. As Murphy’s law this, as Murphy’s Law of dependencies states - : Whatever they can access, they will access. And doing that makes the modules This practice leads to tightly coupled modules.
In reality, the graphs (see Figure 9) can become very complicated, making it difficult to keep track of the dependencies among modules let alone drawing them manually. The number of modules might may increase linearly with time, however, the dependencies tend to often grow at a much faster rate.
Advantages of generating a module dependency graph using a library or plugin , other than (beyond the technical onesbenefits):
Dependency graphs give provide new contributors with a head start in learning understanding the existing codebase quickly, since they don’t need to keep digging around . These graphs eliminate the need to dig through the codebase to figure out the dependencies It is easy to update manually.
Updating dependency graphs is quick and straightforward whenever new modules get are 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 maintain a lean architecture. For example, you can set a maximum height for the tree with a root module. Fixing the Enforcing a max height makes sure ensures that the graph tree doesn’t degenerate into a list.2
Acknowledgements:I would like to thank Rajan Maurya, Lead Engineer of Mobile Development at Mifos Initiative, for inspiring me to share my learnings about dependency graphs through this article.
If you are interested in contributing to open-source projects, I encourage you to explore the Mifos Initiative projects on GitHub: https://github.com/openmf
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 demonstrationclarity.
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 total build time of for the modules built in parallel, will depend on be determined by the module with the maximum longest build time among B, C, and D.
Total build time = Build time of E + Max Build 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 demonstrationclarity.
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 time of (E + D + C + B + A)
= 3 + 10 + 10 + 15 + 2 = 40 s