Software Clustering

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== ACDC Algorithm ======
====== History ======
Developed by Vassilios Tzerpos.

====== Algorithm Intent ======
ACDC produces [[nested/flat decomposition|flat]] or [[nested/flat decomposition|nested]] decompositions of a software system. The algorithm assigns meaningful names to the clusters it creates.

====== Factbase Properties ======
The factbase includes only dependencies between [[terms|entities]].

====== Clustering Objectives ======
The produced decomposition has the following properties:
  - Effective cluster names
  - Bounded cluster cardinality
  - File-level granularity

====== Process Description ======
ACDC creates clusters by detecting established subsystem patterns in the given software system. Software entities that are not clustered this way are assigned to the subsystem that depends the most on them.

====== Decomposition Properties ======

  - The cluster name is one of the following options:
      *	Directory name
      *	Module name with large out-degree 
      *	“Support” for the cluster that contains all utilities
      *	 Module name of dominator node
  - All utilities modules belong to one cluster
  - A large number of clusters contain a dominator node

====== Algorithm Restrictions ======
The algorithm is not suitable for systems with less than 100 source files.

====== Failed Assumptions ======
====== Detailed Algorithm Description ======
ACDC produces a software decomposition from a software system into
stages:

  - Skeleton construction
  - Orphan Adoption

The Skeleton construction phase creates a skeleton of the final decomposition by identifying subsystems using a pattern-driven approach. Depending on the pattern used, the subsystems are given names. In the second stage, the algorithm completes the decomposition by using the Orphan Adoption algorithm.  

===== Skeleton construction =====

The skeleton construction phase has seven steps:
  - Apply the source file pattern
  - Apply the body-header pattern 
  - Create  the potential dominator list
  - Create a support library and dispatcher list
  - Create initial skeleton
  - Iterate the sub-graph dominator pattern including modules from the support library and dispatcher list
  - Apply both the support library pattern and the dispatch  pattern to modules from corresponding list

All apply pattern steps are straight forward grouping entities according to the pattern rule. The other steps are described below.

=== Create  the potential dominator list ===
Algorithm creates a list of all modules in the systems. The list is sorted in order of ascending out-degree, i.e. the first element in the list is the one with smallest number of outgoing edges. 

=== Create a support library and dispatcher list ===
ACDC removes from //the potential dominator list//, all modules that have an in- or out-degree larger than 20. These nodes are placed in two listed:
  * Support library list. This list contains all modules with an in-degree larger than 20.
  * Dispatcher list. This list contains all modules with an out-degree larger than 20.    


=== Create initial skeleton ===

The ACDC goes through each module //n// in the //potential dominator list// and examines whether //n// is dominator node of a subsystem, according to the sub-graph dominator pattern.  

 When dominator node is found then ACDC creates a subsystem containing the dominator node and dominator set. Nodes in the dominator set are removed from the potential dominator list, unless the cardinality of the dominated set was larger than 20.


 After all modules from the potential dominator list have been examined, ACDC organizes the obtained subsystems, so that the containment hierarchy is a tree.     

=== Iterate the sub-graph dominator pattern including modules from the support library and dispatcher list ===





 

===== Orphan Adoption =====

In the previous phase, the skeleton of a software decomposition was constructed. Some modules are left unassigned from the first phase. In this phase, the algorithm assigns all non-clustered modules to an already created subsystem, in particular the subsystem that depends the most on the unassigned module.

====== Implementation ======

The official implementation of ACDC can be downloaded [[http://www.cse.yorku.ca/~bil/downloads|here]].