SIG – Partitioning a Call Graph
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 large 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 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.