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 power law distribution.

A typical algorithm for the generation of random graphs with a power law distribution for its degrees utilizes the following simplified process (modified so it applies to a directed graph):

• 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.
• 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.

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:
  • No multiple edges: Only one edge is allowed between two modules.
  • 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.

Random dependency graph generator uses some classes from other Java libraries.

The JRET, developed at the York University , is a large library that provides a wide range of facilities for reverse engineering in Java.

src_samples.jar