SIG – Partitioning a Call Graph #SWI2005

A company has a large software system that has become costly to maintain. What they need to do is break the system into smaller more manageable modules. Of course, this is a job for a trained expert. However, when the system is largely an automated suggestion for a partition into modules is useful.

Given a Call Graph (Nodes are programs or classes or similar. Edge a->b means program a uses program b) we need to partition the nodes into sets in a manner that favors edges between nodes in the same set and minimizes edges between nodes in different sets. We are interested in algorithms that exploit only the structure of the Call Graph.

The size and complexity of a Call Graph can vary considerably depending on the underlying language and call level. For instance, a typical COBOL system on the program level will contain 1000’s of nodes whereas a Java system on a method level can be over one million nodes.

Good solutions are useful for various graph sizes.