lu.cs.co.graph
Class RandomGraph

java.lang.Object
  |
  +--lu.cs.co.graph.Graph
        |
        +--lu.cs.co.graph.RandomGraph

public class RandomGraph

extends Graph

Constructors for random graphs. Two models for random graphs are supported: in the first, a specified number of edges are inserted at random; in the second, each vertex pair is linked by an edge with a specified probability. There is also a constructor that randomises the edge lengths of a given graph.

All random choices are guided by a random number generator whose seed is a parameter, so identical invocations will construct identical graphs. Java willing, this should happen in a machine-independent fashion.

See Also:

java.util.Random

Fields inherited from class lu.cs.co.graph.Graph

m, n, name

Constructor Summary

RandomGraph(Graph G, int min, int max, long s)
Construct a graph from a given graph by randomising its edge lengths.

RandomGraph(int n, float p, long s)
A random undirected graph with a specified edge probability.

RandomGraph(int n, int m, boolean directed, boolean multi, boolean loops, long s)
Constructs a random graph with a specified number of edges.

RandomGraph(int n, int m, long s)
A random undirected graph with a specified number of edges.

Methods inherited from class lu.cs.co.graph.Graph

degree, edges, findByName, getAdjecencyMatrix, getDistanceMatrix, getEdge, getIndex, getVertex, getVertex, hasEdge, incident, incoming, indegree, index, isDirected, main, outdegree, outgoing, parseGraph, toString, vertices

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

RandomGraph

public RandomGraph(int n,
                   int m,
                   boolean directed,
                   boolean multi,
                   boolean loops,
                   long s)

Constructs a random graph with a specified number of edges. Picks an edge pair at random and if possible inserts an edge between them, subject to the specified restrictions. This process is repeated m times.

Efficiency note: If the graph is simple and dense, this will take a long time, since with good probability, the edge to be inserted is already present. It is a better idea to construct a sparse random graph and complement it with the Graph(Graph,false) constructor.

Parameters:

n - the number of vertices

m - the number of edges

directed - indicates whether edges should be directed

multi - indicates whether multiple (aka. parallel) edges are permitted

loops - indicates whether loops (edges from a vertex to itself) are permitted

s - the seed to be used in all random choices

See Also:

java.util.Random

RandomGraph

public RandomGraph(int n,
                   float p,
                   long s)

A random undirected graph with a specified edge probability. Each edge is present with probability ≤p.

Parameters:

n - the number of vertices

p - the edge probability (should be between 0 and 1)

s - the seed used in all random choices

RandomGraph

public RandomGraph(int n,
                   int m,
                   long s)

A random undirected graph with a specified number of edges. The graph is loop-free and simple.

Parameters:

n - the number of vertices

m - the number of edges

s - the used in all random choices

RandomGraph

public RandomGraph(Graph G,
                   int min,
                   int max,
                   long s)

Construct a graph from a given graph by randomising its edge lengths. The new length is an integer in the range {min,...,max-1}. The copy is constructed using the Graph(Graph,true) constructor.

Parameters:

G - the original graph

min - the minimal edge length

max - one more than the maximal edge length

s - the seed to be used in all random choices