org.jgrapht.generate

Class PruferTreeGenerator<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

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

Generates a random tree using Prüfer sequences.

A Prüfer sequence of length $n$ is randomly generated and converted into the corresponding tree.

This implementation is inspired by "X. Wang, L. Wang and Y. Wu, "An Optimal Algorithm for Prufer Codes," Journal of Software Engineering and Applications, Vol. 2 No. 2, 2009, pp. 111-115. doi: 10.4236/jsea.2009.22016." and has a running time of $O(n)$.

Author:

Alexandru Valeanu

Constructor Summary

Constructors

Constructor and Description
PruferTreeGenerator(int n) Construct a new PruferTreeGenerator.
PruferTreeGenerator(int[] pruferSequence) Construct a new PruferTreeGenerator from an input Prüfer sequence.
PruferTreeGenerator(int n, long seed) Construct a new PruferTreeGenerator.
PruferTreeGenerator(int n, Random rng) Construct a new PruferTreeGenerator

Method Summary

Modifier and Type	Method and Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap) Generates a tree.

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

PruferTreeGenerator

public PruferTreeGenerator(int[] pruferSequence)

Construct a new PruferTreeGenerator from an input Prüfer sequence. Note that the size of the generated tree will be $l+2$ where $l$ is the length of the input sequence. The Prüfer sequence must contain integers between $0$ and $l+1$ (inclusive). Note: In this case, the same tree will be generated every time.

Parameters:

pruferSequence - the input Prüfer sequence

Throws:

IllegalArgumentException - if n is ≤ 0

IllegalArgumentException - if pruferSequence is null

IllegalArgumentException - if pruferSequence is invalid.

PruferTreeGenerator

public PruferTreeGenerator(int n)

Construct a new PruferTreeGenerator.

Parameters:

n - number of vertices to be generated

Throws:

IllegalArgumentException - if n is ≤ 0

PruferTreeGenerator

public PruferTreeGenerator(int n,
                           long seed)

Construct a new PruferTreeGenerator.

Parameters:

n - number of vertices to be generated

seed - seed for the random number generator

Throws:

IllegalArgumentException - if n is ≤ 0

PruferTreeGenerator

public PruferTreeGenerator(int n,
                           Random rng)

Construct a new PruferTreeGenerator

Parameters:

n - number of vertices to be generated

rng - the random number generator to use

Throws:

IllegalArgumentException - if n is ≤ 0

NullPointerException - if rng is null

Method Detail

generateGraph

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

Generates a tree.

Note: An exception will be thrown if the target graph is not empty (i.e. contains at least one vertex)

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - the target graph

resultMap - not used by this generator, can be null

Throws:

NullPointerException - if target is null

IllegalArgumentException - if target is not undirected

IllegalArgumentException - if target is not empty