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:50] – 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 11: Line 11:
   * 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 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.   * 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 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.+  * 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.
  
  
Line 23: Line 23:
     * 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).     * 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).
     * Low Clustering Coefficient: The clustering coefficient of an undirected graph is a measure of the number of triangles in the graph.       * Low Clustering Coefficient: The clustering coefficient of an undirected graph is a measure of the number of triangles in the graph.  
 +
  
 ====== 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.1245534610.txt.gz · Last modified: by mark