Software Clustering

User Tools

Site Tools

You are here: Welcome to the Software Clustering Wiki » Simulated Dependency Graph Generation
Trace:
mdg_generator

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
mdg_generator [2009/06/20 21:43] – markmdg_generator [2010/03/21 20:53] (current) – mark
Line 1: Line 1:
-======  Random Dependency Graph Generation  ====== +======  Simulated Dependency Graph Generation  ====== 
-Random dependency graph generator creates a random graph that imitates a module dependency graph.  The generator produces  a power-law graph due to empirical studies suggest that  degrees of the nodes in a typical Module Dependency Graph (MDG) of a software system follow a [[http://en.wikipedia.org/wiki/Power_law|power law distribution]].+Simulated dependency graph generator creates a random graph that imitates a module dependency graph.  The generator produces  a power-law graph due to empirical studies suggest that  degrees of the nodes in a typical Module Dependency Graph (MDG) of a software system follow a [[http://en.wikipedia.org/wiki/Power_law|power law distribution]].
  
 ====== History ====== ====== History ======
Line 10: Line 10:
  
   * Every node in the graph starts with a current in- and out- degree of 0.   * Every node in the graph starts with a current in- and out- degree of 0.
-  * Every node in the graph is assigned a target in- and out-degree, so that the sequence of degrees follows a power law distribution. The sum of all target in-degrees is equal to the sum of all target out-degrees. +  * Every node in the graph is assigned a target in- and out-degree, so that the seqence of degrees follows a power law distribution. The sum of all target in-degrees is equal to the sum of all target out-degrees. 
-  * Let $I$ be the set of nodes whose current in-degree is less than +  * Let <m>I</m> be the set of nodes whose current in-degree is less than their target in-degree. Let <m>O</m> be the set of nodes whose current out-degree is less than their target out-degree. While <m>I</m> and <m>O</m> are not empty, randomly select a node from each set. Create an edge between the two nodes.
-their target in-degree. Let $O$ be the set of nodes whose current out-degree is less than their target out-degree. While $I$ and $O$ are not empty, randomly select a node from each set. Create an edge between the two nodes.+
  
  
 Random dependency graph generator algorithm is a modified version of the above process, since the user may need to apply additional constraints so that the end result resembles more closely an MDG derived from a software system. The implementation allows for two types of constraints: Random dependency graph generator algorithm is a modified version of the above process, since the user may need to apply additional constraints so that the end result resembles more closely an MDG derived from a software system. The implementation allows for two types of constraints:
   * Edge constraints. These are applied after each edge creation. If the constraint is violated, the edge creation is cancelled, and a new pair of nodes is selected. The current implementation includes three possible edge constraints:   * Edge constraints. These are applied after each edge creation. If the constraint is violated, the edge creation is cancelled, and a new pair of nodes is selected. The current implementation includes three possible edge constraints:
-    *   * No multiple edges: Only one edge is allowed between two modules. +    *   No multiple edges: Only one edge is allowed between two modules. 
-    *   * No cycles: The new edge should not result in a cycle +    *   No cycles: The new edge should not result in a cycle 
-    *   * No loops: The new edge should not connect a node to itself+    *   No loops: The new edge should not connect a node to itself
  
- +  * Graph constraints: These are applied after all edges have been created. If the constraint is violated, an effort will be made to satisfy it if possible by reshuffling some of the edges. If that is not possible, the graph generation process needs to be repeated. The current implementation includes two possible graph constraints: 
-  * Graph constraints: These are applied after all edges have been +    * Connectivity: The produced graph needs to be connected. If that is not the case, our algorithm identifies the connected components and modifies as many edges as required in order to connect them (without violating other constraints). 
-created. If the constraint is violated, an effort will be made to +    * Low Clustering Coefficient: The clustering coefficient of an undirected graph is a measure of the number of triangles in the graph.  
-satisfy it if possible by reshuffling some of the edges. If that is not +
-possible, the graph generation process needs to be repeated. The current +
-implementation includes two possible graph constraints:+
  
  
 ====== Implementation ====== ====== Implementation ======
 +Random dependency graph generator uses some classes from other  Java libraries.
 +
 +===== Dependency =====
 +The [[JRET]], developed at the York University , is a large library that provides a wide range of facilities for  reverse engineering   in Java.
 +
 +===== Download =====
  
-{{:sample.tar.gz|}}+{{:src_samples.jar|}}
mdg_generator.1245534195.txt.gz · Last modified: 2009/06/20 21:43 by mark