Package org.jgrapht.generate

Class RandomRegularGraphGenerator<V,E>

java.lang.Object

org.jgrapht.generate.RandomRegularGraphGenerator<V,E>

Type Parameters:

V - graph node type

E - graph edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

public class RandomRegularGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>

Generate a random $d$-regular undirected graph with $n$ vertices. A regular graph is a graph where each vertex has the same degree, i.e. the same number of neighbors.

The algorithm for the simple case, proposed in [SW99] and extending the one for the non-simple case [W99], runs in expected $\mathcal{O}(nd^2)$ time. It has been proved in [KV03] to sample from the space of random d-regular graphs in a way which is asymptotically uniform at random when $d = \mathcal{O}(n^{1/3 - \epsilon})$.

[KV03] Kim, Jeong Han, and Van H. Vu. "Generating random regular graphs." Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. ACM, 2003. [SW99] Steger, Angelika, and Nicholas C. Wormald. "Generating random regular graphs quickly." Combinatorics, Probability and Computing 8.4 (1999): 377-396. [W99] Wormald, Nicholas C. "Models of random regular graphs." London Mathematical Society Lecture Note Series (1999): 239-298.

Author:

Emilio Cruciani

Constructor Summary

Constructors

Constructor	Description
RandomRegularGraphGenerator(int n, int d)	Construct a new RandomRegularGraphGenerator.
RandomRegularGraphGenerator(int n, int d, long seed)	Construct a new RandomRegularGraphGenerator.
RandomRegularGraphGenerator(int n, int d, Random rng)	Construct a new RandomRegularGraphGenerator.

Method Summary

Modifier and Type	Method	Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap)	Generate a random regular graph.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph

Constructor Detail

RandomRegularGraphGenerator

public RandomRegularGraphGenerator(int n,
                                   int d)

Construct a new RandomRegularGraphGenerator.

Parameters:

n - number of nodes

d - degree of nodes

Throws:

IllegalArgumentException - if number of nodes is negative

IllegalArgumentException - if degree is negative

IllegalArgumentException - if degree is greater than number of nodes

IllegalArgumentException - if the value "n * d" is odd

RandomRegularGraphGenerator

public RandomRegularGraphGenerator(int n,
                                   int d,
                                   long seed)

Construct a new RandomRegularGraphGenerator.

Parameters:

n - number of nodes

d - degree of nodes

seed - seed for the random number generator

Throws:

IllegalArgumentException - if number of nodes is negative

IllegalArgumentException - if degree is negative

IllegalArgumentException - if degree is greater than number of nodes

IllegalArgumentException - if the value "n * d" is odd

RandomRegularGraphGenerator

public RandomRegularGraphGenerator(int n,
                                   int d,
                                   Random rng)

Construct a new RandomRegularGraphGenerator.

Parameters:

n - number of nodes

d - degree of nodes

rng - the random number generator to use

Throws:

IllegalArgumentException - if number of nodes is negative

IllegalArgumentException - if degree is negative

IllegalArgumentException - if degree is greater than number of nodes

IllegalArgumentException - if the value "n * d" is odd

Method Detail

generateGraph

public void generateGraph(Graph<V,E> target,
                          Map<String,V> resultMap)

Generate a random regular graph.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - the target graph

resultMap - the result map

Throws:

IllegalArgumentException - if target is not an undirected graph

IllegalArgumentException - if "n == d" and the graph is simple