com.tensegrity.graph.model
Class GraphGeneration

java.lang.Object
  com.tensegrity.graph.model.GraphGeneration

public class GraphGeneration

extends java.lang.Object

This class has code that generates different sorts of graphs that are used frequently or that are some sort of standard graphs. These graphs are used for debugging and testing graph algorithms and might also be of interest for api users or even final-customers. One important method is provided to allow generation of subgraphs from given graphs with constraining nodes and lists to certain subsets of the sets of nodes and lists in the source graph.

Version:

$Id: GraphGeneration.java,v 1.29 2004/09/10 14:37:56 SharokhKhani Exp $

Author:

S. Rutz

Nested Class Summary

static class

GraphGeneration.TreeRandomizer Helper class for randomization.

Method Summary

static Graph	buildSubgraph(Graph graph, java.util.Iterator nodes, java.util.Iterator edges) Builds a subgraph from the given graph and the given lists of nodes and edges.
static Graph	completeGraph(int n_nodes) Generates a complete graph.
static Graph	gridGraph(int n) Generates a digraph that looks like a grid of size n * n.
static Graph	randomCircular(int n_nodes) Generates a random-circular Graph.
static Graph	randomGraph(int n_nodes, int n_edges) Generates a random graph.
static Graph	randomTree(int n_nodes) Generates a random-tree Graph.
static Graph	randomWorkflow_old(int n_nodes, int n_edges) Generates a random-workflow Graph.
static Graph	randomWorkflow(int n_nodes) Generates a random Graph with workflow characteristics.
static Graph	starGraph(int n) Generates a star-graph.
static Graph	treeGraph(int levels, int leavesPerNode) Generates a tree graph.
static Graph	treeGraph(int levels, int leavesPerNode, GraphGeneration.TreeRandomizer randomizer) Generates a tree graph.

Methods inherited from class java.lang.Object

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

Method Detail

buildSubgraph

public static final Graph buildSubgraph(Graph graph,
                                        java.util.Iterator nodes,
                                        java.util.Iterator edges)
                                 throws GraphException

Builds a subgraph from the given graph and the given lists of nodes and edges. These lists contain elements that are part of the source graph.

Parameters:

graph - the original graph

nodes - the nodes to use for building the subgraph.

edges - the edges to use for building the subgraph.

Returns:

a new subgraph with deep copied independant fields.

Throws:

GraphException - thrown if building failed.

gridGraph

public static Graph gridGraph(int n)
                       throws GraphException

Generates a digraph that looks like a grid of size n * n.

Parameters:

n - the number of nodes per column and row.

Returns:

a digraph that looks like a grid of size n * n.

Throws:

GraphException - thrown if building failed.

starGraph

public static Graph starGraph(int n)
                       throws GraphException

Generates a star-graph.

Parameters:

n - number of outer nodes.

Returns:

the generated Graph.

Throws:

GraphException - thrown if building failed.

treeGraph

public static Graph treeGraph(int levels,
                              int leavesPerNode)
                       throws GraphException

Generates a tree graph.

Parameters:

levels - depth of the tree.

Returns:

the generated tree-graph

Throws:

GraphException - thrown if building failed.

treeGraph

public static Graph treeGraph(int levels,
                              int leavesPerNode,
                              GraphGeneration.TreeRandomizer randomizer)
                       throws GraphException

Generates a tree graph.

Parameters:

levels - depth of the tree.

randomizer - the tree randomizer

Returns:

the generated tree-graph

Throws:

GraphException - thrown if building failed.

completeGraph

public static Graph completeGraph(int n_nodes)
                           throws GraphException

Generates a complete graph.

Parameters:

n_nodes - the number of nodes.

Returns:

the generated Graph.

Throws:

GraphException - thrown if building failed.

randomGraph

public static Graph randomGraph(int n_nodes,
                                int n_edges)
                         throws GraphException

Generates a random graph. The number of edges must be less or equal to ((n_nodes * n_nodes) - n_nodes). If this is not the case, an IllegalGraphException is thrown.

Parameters:

n_nodes - number of nodes to create

n_edges - number of edges to create

Returns:

the generated graph

Throws:

GraphException - thrown if building failed.

randomCircular

public static Graph randomCircular(int n_nodes)
                            throws GraphException

Generates a random-circular Graph.

Parameters:

n_nodes - the number of nodes.

Returns:

the generated Graph.

Throws:

GraphException - thrown if the generation fails.

randomWorkflow

public static Graph randomWorkflow(int n_nodes)
                            throws GraphException

Generates a random Graph with workflow characteristics.

Parameters:

n_nodes - number of nodes in the Graph.

Returns:

the generated workflow Graph.

Throws:

GraphException - thrown if generation failed.

randomWorkflow_old

public static Graph randomWorkflow_old(int n_nodes,
                                       int n_edges)
                                throws GraphException

Generates a random-workflow Graph.

Parameters:

n_nodes - the number of nodes to create.

n_edges - the number of edges to create.

Returns:

the generated Graph.

Throws:

GraphException - thrown if the generation fails.

randomTree

public static Graph randomTree(int n_nodes)
                        throws GraphException

Generates a random-tree Graph.

Parameters:

n_nodes - the number of nodes.

Returns:

the generated Graph.

Throws:

GraphException - thrown if the generation fails.