Dependency Graph

Overview

In the context of Computer Science, most programming languages have Dependency Graphs. These are networks of relationships between dependencies of an application. These relationships are created when one package is imported into another. This network of relationships takes the form of a Directed Acyclic Graph.

Directed Acyclic Graph

Directed Acyclic Graphs do not have any cycles. This rule is especially important for Dependency Graphs because building two packages that depend on each other can cause problems at either Build Time or Runtime (depending on the language and build tool).

We can’t build Package A until Package B is built, but we can’t build Package B until Package A is built. Something like this should never exist:

// File: ClassA.java
import ClassB;

// Some code...

////////////////////

// File: ClassB.java
import ClassA;

// Some code...

The solution for this type of problem is to separate the common logic into a third package that is imported into both A and B. This is the case with both packages and classes.

Various Representations

A Dependency Graph can be represented a number of ways, both visually and in code. Below are some of the most common ways of representing them:

Dependency Matrix

A matrix can be used to represent the graph where each node is listed on both the rows and columns. Each cell represents the relationship between two nodes. In code, a two-dimensional array (one array nested in another) can create a matrix.

# 1 means there is a dependency, 0 means no dependency
# For example, PackageA (row 0) depends on PackageB (column 1) and PackageC (column 2)
dependency_matrix = [
    [0, 1, 1, 0],  # PackageA depends on PackageB and PackageC
    [0, 0, 0, 0], 
    [1, 0, 0, 0],  # PackageC depends on PackageA
    [0, 0, 1, 0],  # PackageD depends on PackageC
]
# Note that the diagonal cells from (0, 0) to (3, 3) represent a relationship with the package itself, which would be 
# a circular dependency. 

Adjacency List

The term Adjacency List can be misleading because they’re usually represented by Hash Maps (dictionaries in Python). More specifically, a Hash Map where the values are lists or sets. This represents a one-directional relationship between the Key and the Values.

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

Linked Nodes

Linked Nodes can be represented in code, minimally, by a single Node class with a field representing a list of deps.

class Node:
    def __init__(self, value):
        self.value = value
        self.deps = []

# Create nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

# Link nodes
node1.deps.append(node2)
node2.deps.append(node3)
node3.deps.append(node4)

Build Tools and Package Managers

Build Tools and Package Managers fetch packages and build raw source code into artifacts that can be executed by the processes that actually run your application. In the case of Java, the process that runs your code is java, controlled by the JVM, whereas for JavaScript, it’s node for the Back-End and a browser for the Front-End. Each programming language has its own set of Build Tools. Java has tools like Maven and Gradle. JavaScript has NPM and yarn.

For projects that use multiple languages (especially common in distributed systems), Build Tools like Bazel provide a common developer interface to define dependencies in multiple languages.

java_library(
    name = "MyApp_lib",
    srcs = glob(["*.java"]),
    visibility = ["//visibility:public"],
)

java_binary(
    name = "MyApp",
    main_class = "com.example.MyApp",
    runtime_deps = [
        ":MyApp_lib",
    ],
)

Conflicts

Conflicts arise when two packages in the Dependency Graph require different versions of the same package.

In the above example, there are two different versions of Package C. The final artifact can only contain a single version of Package C. For this reason, either version 1.1 or 1.2 must be chosen to be included in the release artifact.

Conflict Resolution

A common resolution mechanism is to select the newest version (this assumes that the packages are backwards compatible).

Nuance: Build Tool vs Package Manager

Build Tools and Package Managers have evolved over time such that their overlaps now encompass each other almost entirely (in a sense). Originally, Build Tools were focused on building/compilation and testing whereas Package Managers were focused on managing dependencies and their installation. Now, Build Tools incorporate features of package management and Package Managers incorporate features of building and testing. However, if we use JavaScript’s npm as an example, it doesn’t build and test in the strictest sense, it invokes other tools to do the building (e.g. transpilation) and testing. Calling it a Build Tool isn’t entirely wrong, and is perfectly acceptable if convenience is the priority. However, given that one goal of Software.Land is to clarify nuances by diving into details, there is a difference.

As mentioned above, tools like Bazel (which is also considered a Build Tool) wrap multiple Build Tools and Package Managers to provide a common developer interface.

Next Steps

Learn more about Data Structures: What is a Data Structure?

Some code examples generated by ChatGPT of OpenAI and modified.

Updated: 2024-02-04

Author

Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.

• ← Build Time
• Class vs Interface →