Program Modularization Detection using a k-Cut Algorithm

Problem

Real-world computer programs are often quite large. In order to build them, designers break the implementation into modules. However, many programming languages do not directly support modules and must simulate modules with functions or files. Subsequent mainainers may not have the benefit of accurate documentation for mapping between the conceptual modules and the actual code. Consequently, there is a need to derive such mappings from the code.

Background

If each function in a program is thought of as a node in a graph, and calls from one function to another are denoted by arcs, the resultant structure is a call graph. Call graphs for real-world programs can have thousands of nodes and be completely unintelligible when drawn on a computer screen What is desired is to replace a group of related nodes by a single abstract node and, at the same time, to collapse all adjacent arcs into a single arc. In this way, complex graphs can be simplified into a more usable form.

One way of detecting candidate modules is to look for subgraphs of the a program's call graph that have the following two properties: connectivity among the nodes in the subgraph is high and connectivity between the subgraph and the nodes outside of the subgraph is low. In terms of graph theory, we are trying to find ways to cut a call graph into pieces.

This miniproject asks you to implement and apply an algorithm for partitioning graphs called a k-cut algorithm to actual call graphs obtained from software systems in order to assess its practicality in determining the systems' modules.

Deliverables

• An implementation of the algorithm
• A 2500-word report (about 5 pages). Longer is OK, but not necessary. Report should discuss the applicability of the algorithm to the problem of determining modules.

Evaluation

Evaluation is based on the quality of your report .