1998 United States NP-hard

Bunch — Software Module Clustering

Spiros Mancoridis and Brian Mitchell, 1998 — recovering the right modular structure of a codebase reduces to graph partitioning, which is NP-hard. Architecture is search.

Spiros Mancoridis and Brian Mitchell, at Drexel University, with Yih-Farn Chen and Emden Gansner, defined the software module clustering problem and built the Bunch tool to solve it heuristically. Given a module dependency graph — nodes are source files, edges are calls or imports — find a partition of the nodes into clusters that maximizes a modularization quality (MQ) metric: high cohesion within clusters, low coupling between them. This is graph partitioning, NP-hard. Bunch attacks it with hill-climbing and genetic algorithms; later work added simulated annealing and multi-objective Pareto search. Every empirical study confirms the same: optimal modularization is computationally infeasible at industrial scale, and every architectural-recovery tool delivers approximations. The hardness is intrinsic. Choosing where the modules go is a search problem, not an engineering one.

In plain terms

When a project is small, the right module structure is obvious. Two files. Three files. You can hold the whole thing in your head. When a project gets to ten thousand files, the right module structure is not obvious. It is a research question. Mancoridis and Mitchell gave the research question its formal name. The dependency graph of a codebase has source files as nodes and dependencies as edges. A modular architecture is a partition of that graph — every file belongs to exactly one module, and the module boundaries should follow the natural seams of the dependency structure. Files that talk to each other a lot belong in the same module (high cohesion). Modules should not talk to each other unnecessarily (low coupling). The Modularization Quality metric MQ formalizes this trade-off. Maximizing MQ over all possible partitions of a graph is graph partitioning. Graph partitioning is NP-hard. This means that for any real codebase, there is no algorithm that finds the truly optimal modular structure — the search space is too large. Bunch sidesteps the hardness with hill-climbing and genetic algorithms. You start with a random partition, swap files between modules looking for improvements, and stop when no swap helps anymore. The result is a local optimum, not a global one. Every modern architectural-recovery tool — every "your codebase is divided into these modules" report from a static analyzer or a refactoring assistant — is solving the same NP-hard problem with a heuristic. This is the second time in the book the same pattern appears: a real engineering activity (deciding where the modules go) turns out to be a known-hard combinatorial problem (graph partitioning), and the tools are heuristics. The next chapter is the third time, with package dependencies. When AI tools claim to "refactor" a codebase or "improve its architecture," they are running an even less rigorous heuristic than Bunch. They have no MQ metric, no convergence guarantee, no guarantee of even local optimum. They are predicting the next token from context. That is a worse search procedure than hill climbing for an NP-hard problem. Where do the modules go. NP-hard. Architecture is search.