mapss.dif
Class DIFRandomGraphGenerator

java.lang.Object
  mapss.dif.DIFRandomGraphGenerator

Direct Known Subclasses:

HSDFRandomGraphGenerator, SDFRandomGraphGenerator

public class DIFRandomGraphGenerator
extends java.lang.Object

Random graph generator in generating random DIF graphs. The generator makes random topology only. Parameters like production rates, consumption rates, and delays are to be determined in the specific class of dataflow. After the object instanciation, every call to #graph() generates a new graph with the same node count. Therefore, multiple random graphs can be obtained with only one time object creation.

Version:

$Id: DIFRandomGraphGenerator.java 414 2007-05-26 20:40:49Z plishker $

Author:

Mingyung Ko

Field Summary

protected DIFGraph	_graph The random graph.
protected boolean[][]	_incidence Incidence matrix.
protected boolean[][]	_reachability Reachability matrix.

Constructor Summary

DIFRandomGraphGenerator()
Null constructor.

Method Summary

protected void	_initialize() Initialize the generator.
protected void	_initialize(DIFGraph graph, java.lang.Object nodeWeight, java.lang.Object edgeWeight) Initialize the generator.
protected boolean	_isIncident(mocgraph.Node source, mocgraph.Node sink) Check the existence of an edge connecting the source to the sink.
protected boolean	_isReachable(mocgraph.Node source, mocgraph.Node sink) Check the existence of any path from the source to the sink.
protected void	_makeDAG(int density) Make a radom Directed Acyclic Graph (DAG).
protected int	_randomNonNegativeInt(int upperBound) Return a random non-negative integer for a given bound.
protected void	_reset(int nodeCount) Reset all configurations to generate a new random graph.
DIFGraph	graph(int nodeCount) Generate a random DIF graph with the given node count.
DIFGraph	graph(int minNodes, int maxNodes) Generate a random DIF graph with the given node count range.Node count is automatically set to 2 in the implementation if the given minimum count is less than 2.
DIFGraph[]	graphs(int minNodes, int maxNodes, int graphCount) Generate a bunch of DIF graphs.
void	setMaxFanIn(int maxFanIn) Set the maximal number of edges that can fan into each node.
void	setMaxFanOut(int maxFanOut) Set the maximal number of edges that can fan out of each node.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_graph

protected DIFGraph _graph

The random graph.

_reachability

protected boolean[][] _reachability

Reachability matrix.

_incidence

protected boolean[][] _incidence

Incidence matrix.

Constructor Detail

DIFRandomGraphGenerator

public DIFRandomGraphGenerator()

Null constructor.

Method Detail

graph

public DIFGraph graph(int nodeCount)

Generate a random DIF graph with the given node count. Presently, only Directed Acyclic Graph (DAG) generation is implemented.

Parameters:

nodeCount - The desired node count.

Returns:

The random graph in DIFGraph.

graph

public DIFGraph graph(int minNodes,
                      int maxNodes)

Generate a random DIF graph with the given node count range.Node count is automatically set to 2 in the implementation if the given minimum count is less than 2. The rationale is that data depedence can not happen to graphs with one node only. Presently, only Directed Acyclic Graph (DAG) generation is implemented.

Parameters:

minNodes - The minimal node count.

maxNodes - The maximal node count.

Returns:

The random graph in DIFGraph.

graphs

public DIFGraph[] graphs(int minNodes,
                         int maxNodes,
                         int graphCount)

Generate a bunch of DIF graphs. Node count of each graph is randomly determined within the minimum and maximum parameters. The minimal node count and graph count should be at least two.

Parameters:

minNodes - The minimal node count.

maxNodes - The maximal node count.

graphCount - The desired number of random graphs.

Returns:

Random graphs in array.

setMaxFanIn

public void setMaxFanIn(int maxFanIn)

Set the maximal number of edges that can fan into each node.

Parameters:

maxFanIn - The maximal number of fan-in edges.

setMaxFanOut

public void setMaxFanOut(int maxFanOut)

Set the maximal number of edges that can fan out of each node.

Parameters:

maxFanOut - The maximal number of fan-out edges.

_initialize

protected void _initialize()

Initialize the generator.

_initialize

protected void _initialize(DIFGraph graph,
                           java.lang.Object nodeWeight,
                           java.lang.Object edgeWeight)

Initialize the generator.

Parameters:

graph - The desired dataflow graph type.

nodeWeight - The desired node weight type.

edgeWeight - The desired edge weight type.

_isIncident

protected boolean _isIncident(mocgraph.Node source,
                              mocgraph.Node sink)

Check the existence of an edge connecting the source to the sink. The order of nodes matters since DIF graphs are directed. It is equivalent to DirectedGraph.edgeExists(Node, Node). However, the implementation here is more efficient because an incidence matrix is built along with the random graph generation process. Incidence checking is through retrieving the matrix element rather than a computation from the ground.

Parameters:

source - The source node.

sink - The sink node.

Returns:

True if there is an edge connecting the source to the sink; false otherwise.

_isReachable

protected boolean _isReachable(mocgraph.Node source,
                               mocgraph.Node sink)

Check the existence of any path from the source to the sink. The order of nodes matters since DIF graphs are directed. Reference also reachableNodes() in DirectedGraph. The implementation here is through retreiving matrix elements rather than a computation from the ground.

Parameters:

source - The source node.

sink - The sink node.

Returns:

True if the sink is reachable from the source; false otherwise.

_makeDAG

protected void _makeDAG(int density)

Make a radom Directed Acyclic Graph (DAG).

Parameters:

The - density of the number of edges.

_randomNonNegativeInt

protected int _randomNonNegativeInt(int upperBound)

Return a random non-negative integer for a given bound.

Parameters:

upperBound - The upper bound (exclusive) of the random number.

Returns:

The random non-negative integer.

_reset

protected void _reset(int nodeCount)

Reset all configurations to generate a new random graph.

Parameters:

nodeCount - The desired node count.