Differences

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

--- mdg_generator [2009/06/20 21:44] – mark
+++ mdg_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 ======
@@ Line 10: / Line 10: @@
   * 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.
@@ Line 20: / Line 19: @@
     *   No cycles: The new edge should not result in a cycle
     *   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:
+    * 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.
 ====== 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|}}