Spectral and meta-heuristic algorithms for software clustering

When large software systems are reverse engineered, one of the views that is produced is the system decomposition hierarchy. This hierarchy shows the system's subsystems, the contents of the subsystems (i.e., modules or other subsystems), and so on. Software clustering tools create the system decomposition automatically or semi-automatically with the aid of the software engineer. The Bunch software clustering tool shows how meta-heuristic search algorithms can be applied to the software clustering problem, successfully. Unfortunately, we do not know how close the solutions produced by Bunch are to the optimal solution. We can only obtain the optimal solution for trivial systems using an exhaustive search. This paper presents evidence that Bunch's solutions are within a known factor of the optimal solution. We show this by applying spectral methods to the software clustering problem. The advantage of using spectral methods is that the results this technique produces are within a known factor of the optimal solution. Meta-heuristic search methods only guarantee local optimality, which may be far from the global optimum. In this paper, we apply the spectral methods to the software clustering problem and make comparisons to Bunch. We conducted a case study to draw our comparisons and to determine if an efficient clustering algorithm, one that guarantees a near-optimal solution, can be created. (c) 2004 Published by Elsevier Inc.