Dependency Structure Matrices and the Cost of a Cycle

A dependency graph drawn as boxes and arrows becomes unreadable somewhere around thirty nodes; the arrows cross, the layout rearranges them into a shape that reflects the drawing tool rather than the code, and readers take away an impression instead of a fact. The same graph as a square matrix stays readable at a few hundred nodes, because position carries the information and the eye is good at finding structure in a grid. The matrix also answers the two questions evaluations actually ask: can these modules be built and tested in a chosen order, and which parts of the system cannot be separated from each other at all.

The matrix form and what a filled cell means

Take the modules at whatever granularity the build system recognises — packages, projects, crates, Gradle modules — and order them along both axes. Cell $(i, j)$ is marked when module $i$ depends on module $j$. A strict dependency has a direction and is not symmetric, so a well-formed system fills only one triangle of the matrix. The diagonal is either blank or holds self-dependencies, which are a different finding: a module whose internals form a cycle.

The useful invariant is triangularity. If the modules can be reordered so that every mark sits below the diagonal, then the dependency relation is acyclic and the order along the axis is a valid build order. The diagonal boundary is the frontier: everything below it is a lower layer, everything above an upper layer, and a mark above it is a dependency pointing backwards, which is exactly what a layering violation is.

This is the same information a topological sort produces, but the matrix shows the whole relation at once rather than one valid sequence. Two different sequences can both be topological, so a sorted list hides which edges were nearly violations; the matrix shows the density near the diagonal, which is where the expensive coupling lives.

Partitioning: recovering levels without touching code

Partitioning is the operation of permuting rows and columns with the same permutation until the marks cluster near the diagonal. The permutation is a hypothesis about the intended layers, and it costs nothing to try, because it changes only the view.

The manual version is fast enough for most systems: pick the module with no outgoing dependencies, put it first, remove its row and column, repeat. What remains when no module can be removed is precisely the set of modules that participate in or depend on a cycle. That residue is the finding the evaluation is after, and it appears without any graph library.

Two facts make the matrix worth the effort at this granularity:

• The number of distinct module pairs grows as $n(n-1)/2$, so 100 modules give 4,950 pairs and 9,900 possible directed dependencies. At that size a drawing is useless and a matrix is still scannable.
• Real systems are sparse. A module typically depends on a handful of others regardless of $n$, so the matrix is mostly blank and the marks stand out.

The blanks matter as much as the marks. A large empty block between two groups of modules is evidence that they can be built, versioned, and released independently; a densely filled block is a candidate for being one module rather than several.

Finding the strongly connected components

When the residue needs explaining rather than just locating, the tool is the strongly connected component: a maximal set of modules where every member reaches every other. Condensing each component to a single node always yields a directed acyclic graph, so the components are the true units of build order, and their internal structure is the part that has to be untangled by hand.

Tarjan’s algorithm computes them in $O(V + E)$ time with one depth-first traversal, using an index per node and a low-link value that records the smallest index reachable through the current stack. A node whose low-link equals its own index is the root of a component, and everything above it on the stack belongs to that component.

def components(graph):
    index, low, on_stack, stack = {}, {}, set(), []
    result, counter = [], 0

    def visit(v):
        nonlocal counter
        index[v] = low[v] = counter
        counter += 1
        stack.append(v)
        on_stack.add(v)
        for w in graph.get(v, ()):
            if w not in index:          # tree edge: recurse, then absorb low-link
                visit(w)
                low[v] = min(low[v], low[w])
            elif w in on_stack:         # back edge into the current stack
                low[v] = min(low[v], index[w])
        if low[v] == index[v]:          # v roots a component; pop through it
            comp = []
            while True:
                w = stack.pop()
                on_stack.discard(w)
                comp.append(w)
                if w == v:
                    break
            result.append(comp)

    for v in graph:
        if v not in index:
            visit(v)
    return result

Recursion depth equals the longest path, which for a few hundred modules is fine and for a few thousand generated modules may not be; the iterative formulation with an explicit stack is the same algorithm with the call stack made visible.

What a cycle costs, and what it does not

A cycle is not a style violation in the abstract. It costs four specific things:

Build independence disappears. Modules in one component cannot be compiled, tested, or released separately in a strict sense, because each needs the other’s artefacts. Incremental builds still work at file granularity, but the release unit is the component.

Test isolation degrades. A unit test of a module in a cycle drags its partners in, so the test is really an integration test, and the failure it reports cannot be attributed to one side.

Change propagation widens. A modification in any member can require a modification in every other member, because the contract between them can move in either direction. This is the mechanism behind the change coupling that shows up in version history, and it is the reason cycles predict co-change better than import counts do.

Reasoning requires holding the whole component at once. There is no order in which a reader can understand the members one at a time.

What a cycle does not do is make the code wrong. Many cycles are legitimate: a parser and its AST node types reference each other, a plugin interface and its registry reference each other. For those, the honest resolution is to record the cycle as intentional, place a boundary around it so it cannot grow, and stop treating the component as a unit that could be split. The failure mode is the undocumented cycle, which grows by absorbing modules that were never meant to be in it.

Breaking a cycle without a rewrite

Three moves are available, in increasing cost.

Dependency inversion replaces a direct edge with an edge to an interface the lower module owns. If billing and shipping both need to send notifications, the notification port belongs in a module that neither owns, and both point at it. The cycle becomes two edges into a leaf. The Java and C# ecosystems get this nearly free because interface types can live in a separate assembly; the cost is a new module and a stable interface that has to be designed carefully, since a bad interface at the bottom of the graph propagates to everyone above it.

Mediation moves the interaction to a coordinator above both parties. The coordinator depends on both, neither depends on the other, and the cycle becomes a V shape. The cost is a new central node that can turn into a god object, and a runtime hop in every mediated interaction.

Merging accepts that the two modules are one and collapses them. This is often correct. Two packages that import each other, change together, and are released together are one package with an artificial boundary. Merging removes the false signal and makes the real boundary visible, which is more honest than a documented cycle that everyone has learned to ignore.

Edges the compiler cannot see

The matrix built from imports is a lower bound on coupling. Several dependency channels leave no import statement:

Reflective and dynamic lookup. Class names in configuration, service locators, and string-keyed registries create edges that no static tool sees. A plugin loaded by name is a dependency on a contract plus a dependency on whatever the plugin touches.

Shared mutable state. Two modules that both write the same table, cache key, or filesystem path are coupled through data even with no code path between them. Database schema is the usual carrier, and it is invisible in any per-language analysis.

Build and deployment ordering. A migration script that must run before a service starts is an edge, expressed in a file the language does not parse.

Generated code. Generated clients embed a copy of a remote contract; regenerating one side without the other is a coupled change with no import.

An evaluation that reports “no cycles” from import analysis has reported a fact about imports. The narrower claim is worth making explicitly, and it is why the matrix is best paired with a structural test that encodes the intended layering, as described in fitness functions.

Granularity decides the answer

The same system has a different component structure at every level: files, packages, modules, deployable services. A cycle at file level may vanish at package level if the files are siblings, and a package-level acyclicity may coexist with a service-level cycle through synchronous calls in both directions. Neither view is wrong; they answer different questions.

The granularity to choose is the one that matches the unit of change the quality-attribute scenarios describe. If a scenario asks how long it takes to add a payment provider, the relevant matrix is at the level of the modules a provider change touches. If it asks whether checkout can be released without shipping, the relevant graph is over deployable units and their runtime calls. Running the analysis at a level nobody changes anything at produces clean diagrams and no information.