An Evolutionary Approach for Partitioning Weighted Module Dependency Graphs

The structure of most software systems is large and complex. Therefore, understanding these software systems is difficult. The reason for this complexity is the dependency of their varied modules on each other. The type of dependencies in software systems may be function calls, variable references, macro invocations, and so on. Dependencies of modules of a software system can be viewed as a weighted directed graph that in this paper is referred to as weighted module dependency graph (WMDG). Software clustering is the process that divides the WMDG of a large software system into different partitions with maximum intra-connectivity and minimum inter-connectivity. Software clustering problem is NP-hard and therefore software clustering algorithms try to find near optimal partitions. All algorithms, proposed for software clustering, use module dependency graphs and don´t consider weights for them. In this paper, a new genetic algorithm is proposed for clustering WMDGs. Experimental results show that using WMDGs increases the efficiency of clustering algorithm.