Cycles in Module Dependency Graphs and How to Break Them

A dependency graph with a cycle has no topological order, and a build system, a test runner, or a code owner map needs one. That is the mechanical statement of the problem, and it understates it. A cycle means the modules inside it cannot be compiled, tested, released, or understood in isolation no matter how well their interfaces are designed, because each one’s correctness depends on a version of the others that is not yet determined. The graph, not the code, has made them a single unit.

Compilers enforce acyclicity for some kinds of edge and not others, which is why cycles accumulate in codebases that appear clean. A Java compiler accepts two packages that import each other; nothing in the language prevents it. Go rejects import cycles outright. C and C++ permit header cycles through forward declarations, which removes the compile-time edge but leaves the design dependency. The rule a project can enforce is narrower than the rule it needs.

Strongly connected components are the real modules

Every directed graph decomposes uniquely into strongly connected components: maximal sets of vertices where each vertex can reach every other. Condensing each component to a single vertex yields a directed acyclic graph. Tarjan’s algorithm computes the decomposition in time linear in vertices plus edges, so the analysis is cheap enough to run on every commit.

The consequence for modularity is direct. If a component contains 40 modules, the graph has recorded that those 40 are one module for the purposes of ordering, versioning, and change impact. The directory listing may show 40 entries; the release graph shows one. A cycle of length two and a cycle of length forty differ in how hard they are to untangle, not in what they do to the release unit.

The measure worth tracking is not “number of cycles” but the size distribution of components. A single component containing a third of the codebase is a stronger signal than a dozen two-module cycles scattered through leaf packages, because it determines the minimum granularity at which anything can be replaced. Change-impact analysis inherits the same structure: a change anywhere in a component of size N requires reasoning about N modules, regardless of how many edges the change actually touches.

Four mechanisms that produce cycles

Mutual reference between domain concepts. An Order needs to know its Customer, and Customer needs a list of recent Orders. In an object model the two types reference each other; in a module graph the two packages do too. The cycle is often a modelling artefact rather than a design requirement: one direction is usually a query that belongs in a repository or a service, not in the entity.

Shared utility drift. A common module starts with a string helper. Then it acquires a date formatter that needs the locale from a settings module, and settings imports common for the helper. The cycle is created by accretion, one plausible import at a time, and it is invisible in review because each individual import looks reasonable. Utility modules are cycle generators precisely because they have no defined secret and therefore no principled reason to refuse a dependency.

Callbacks and events. Module A calls B, and B notifies A through a registered listener. There is no import from B to A, so the static graph is acyclic, but the runtime graph is not: A cannot be tested without B and B’s behaviour depends on A. This is the cycle that static analysis misses, and it is the one that causes the most surprising test failures. Registration order and re-entrancy determine behaviour, and neither appears in any module’s interface.

Layer inversion through a framework. A dependency injection container wires implementations into interfaces declared in lower layers. The source code is acyclic; the configuration is not, because the wiring names concrete classes from an upper layer. The build graph and the deployment graph disagree, and a change to an upper-layer class forces a rebuild or redeploy of the composition root.

Breaking a cycle without moving it

The techniques differ in what they cost, and the first decision is whether the two modules should be one.

Collapse them. If the cycle exists because the two modules share a private representation and constantly pass it back and forth, the boundary is in the wrong place. Merging restores acyclic order at the cost of a larger module, and it is the correct answer more often than refactoring advice admits. The test is whether the pair could ever be released independently; if not, they were already merged in every respect except the directory listing.

Invert one edge with an interface owned by the consumer. The consumer declares the interface it needs, in its own package, and the provider implements it. The import edge now points from provider to consumer, which is the direction that removes the cycle. This is the dependency inversion principle applied literally, and its cost is that the interface lives away from its implementations, so discoverability depends on tooling.

// package reporting declares what it needs; it does not import storage.
package reporting

type Reader interface {
    Load(id string) (Record, error)
}

type Service struct{ r Reader }

func (s Service) Render(id string) (string, error) {
    rec, err := s.r.Load(id)
    if err != nil {
        return "", err
    }
    return format(rec), nil
}

// package storage imports reporting for its Record type; Go does not
// require a declaration that Store implements reporting.Reader.
package storage

type Store struct{ /* ... */ }

func (s *Store) Load(id string) (reporting.Record, error) { /* ... */ }

The Go version is unusually clean because interface satisfaction is implicit: storage must still import reporting for the Record type, but if Record is a plain data type the dependency is one-way and harmless. In a language with nominal interfaces, the provider imports the consumer’s interface package explicitly, which is the same shape with one more edge to inspect.

Extract the shared part into a lower module. When both sides depend on a third concept that lives in one of them, moving that concept down breaks the cycle and creates two acyclic edges. The risk is that the extracted module becomes a new common and attracts future dependencies from everywhere. Extracted modules need the same secrecy discipline as any other: name what they hide, and refuse imports that are not about that.

Move the orchestration up. If A and B call each other because each performs half of a workflow, the workflow belongs in a third module that calls both. Neither A nor B needs to know about the other, and the sequence becomes explicit and testable in one place. The cost is an extra layer of calls and a module that is mostly coordination.

Replace the direct call with an event. This removes the static edge but keeps the runtime one. It is a valid choice when the two sides genuinely must not know each other, and it is a bad choice when used to quiet a linter, because it converts a compile-time error into a behaviour that only appears under specific timing. Any event-based break should come with a documented ordering guarantee and a test that exercises both participants together.

Keeping the graph acyclic after it is fixed

A cycle-free graph is a temporary state. Three practices keep it that way without freezing the design.

Make the graph visible in continuous integration. Emitting the edge list and the component decomposition on every build turns an architectural rule into a build failure, and it lets reviewers see when a new edge merges two previously separate components. The check costs one graph traversal, which is negligible next to compilation.

Encode the intended layering as data, not as prose. A list of permitted dependency directions, checked against the extracted edges, fails on the specific violation rather than on a generic “architecture test”. The list needs an owner and an expiry date, because an allow-list that nobody prunes becomes the architecture.

Treat new edges as review events. The question is not whether the import compiles but what knowledge it adds. An import of a data type used in one signature is a weaker commitment than an import of a class whose methods are called, and the graph as commonly extracted does not distinguish them. The distinction is worth recording in review comments even when no tool captures it.

The limits of the graph

A dependency graph is an approximation of knowledge, not a measurement of it. It does not see reflection, string-based dispatch, configuration files, database schemas shared by two modules, or two modules that read the same file format. Those are dependencies in the only sense that matters — a change to one forces a change to the other — and they do not appear as edges.

The corrective is to combine the graph with change coupling: pairs of modules that are modified in the same commits despite having no import edge are coupled by something the graph cannot see. That signal, and not the arrow count, is what coupling and cohesion is ultimately about. Once the cycles are gone, the remaining question is which edges are stable enough to build on, which is what the instability and abstractness metrics attempt to quantify.