protected:acdc
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
protected:acdc [2009/05/10 20:16] – mark | protected:acdc [2010/05/06 14:00] – bil | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== ACDC Algorithm ====== | ====== ACDC Algorithm ====== | ||
====== History ====== | ====== History ====== | ||
- | Algorithm was developed | + | Developed |
====== Algorithm Intent ====== | ====== Algorithm Intent ====== | ||
- | ACDC algorithm | + | ACDC produces [[nested/ |
====== Factbase Properties ====== | ====== Factbase Properties ====== | ||
- | The //[[factbase]]// includes only dependencies between [[terms|entities]]. | + | The factbase includes only dependencies between [[terms|entities]]. |
====== Clustering Objectives ====== | ====== Clustering Objectives ====== | ||
The produced decomposition has the following properties: | The produced decomposition has the following properties: | ||
- | - Effective cluster | + | - Effective cluster |
- Bounded cluster cardinality | - Bounded cluster cardinality | ||
- File-level granularity | - File-level granularity | ||
Line 24: | Line 23: | ||
* Directory name | * Directory name | ||
* Module name with large out-degree | * Module name with large out-degree | ||
- | * “Support” for cluster contains all utilities | + | * “Support” for the cluster |
* Module name of [[subsystem patterns|dominator node]] | * Module name of [[subsystem patterns|dominator node]] | ||
- All utilities modules belong to one cluster | - All utilities modules belong to one cluster | ||
- | - A large number of cluster contains | + | - A large number of clusters contain |
- | + | ||
- | + | ||
- | | + | |
====== Algorithm Restrictions ====== | ====== Algorithm Restrictions ====== | ||
Line 37: | Line 33: | ||
====== Failed Assumptions ====== | ====== Failed Assumptions ====== | ||
====== Detailed Algorithm Description ====== | ====== Detailed Algorithm Description ====== | ||
- | ACDC produces software decomposition from a software system into | + | ACDC produces |
stages: | stages: | ||
- Skeleton construction | - Skeleton construction | ||
- | - Completion of clustering using Orphan Adoption | + | - 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 algorithm completes decomposition by using [[Orphan Adoption]] algorithm. | + | 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 |
===== Skeleton construction ===== | ===== Skeleton construction ===== | ||
Line 51: | Line 47: | ||
- Create | - Create | ||
- Create a support library and dispatcher list | - Create a support library and dispatcher list | ||
- | - Apply the [[subsystem patterns|sub-graph dominator pattern]] | + | - Create initial skeleton |
- Iterate the sub-graph dominator pattern including modules from the support library and dispatcher list | - Iterate the sub-graph dominator pattern including modules from the support library and dispatcher list | ||
- Apply both the [[subsystem patterns|support library pattern]] and the [[subsystem patterns|dispatch | - Apply both the [[subsystem patterns|support library pattern]] and the [[subsystem patterns|dispatch | ||
Line 59: | Line 55: | ||
=== Create | === Create | ||
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. | 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 === | === 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 [[subsystem patterns|dominator node]] and [[subsystem patterns|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 === | === Iterate the sub-graph dominator pattern including modules from the support library and dispatcher list === | ||
Line 74: | Line 82: | ||
In the previous phase, the skeleton of software decomposition was constructed. Some modules are left unassigned from the first phase. | In the previous phase, the skeleton of software decomposition was constructed. Some modules are left unassigned from the first phase. | ||
- | The [[Orphan Algorithm]] attempts to assign all unassigned modules to some subsystems. The skeleton decomposition serves as the existing structure, while the non-clustered modules are the orphans. [[Orphan Algorithm]] will not assign module if the module follows the leaf pattern, and it cannot be assigned to any subsystem with sufficient level of confidence. Finally, ACDC applies the leaf pattern for all unassigned modules. | + | The [[Orphan Algorithm]] attempts to assign all unassigned modules to some subsystems. The skeleton decomposition serves as the existing structure, while the non-clustered modules are the orphans. [[Orphan Algorithm]] will not assign module if the module follows the leaf pattern, and it cannot be assigned to any subsystem with sufficient level of confidence. Finally, ACDC applies the leaf pattern for all unassigned modules. |
+ | |||
+ | ====== Implementation ====== | ||
+ | |||
+ | The official implementation of ACDC can be downloaded [[http:// |
protected/acdc.txt · Last modified: 2010/05/08 15:20 by mark