Package org.jgrapht.generate
Class PruferTreeGenerator<V,E>
- java.lang.Object
-
- org.jgrapht.generate.PruferTreeGenerator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphGenerator<V,E,V>
public class PruferTreeGenerator<V,E> extends java.lang.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 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, java.util.Random rng)
Construct a new PruferTreeGenerator
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
generateGraph(Graph<V,E> target, java.util.Map<java.lang.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:
java.lang.IllegalArgumentException
- ifn
is ≤ 0java.lang.IllegalArgumentException
- ifpruferSequence
isnull
java.lang.IllegalArgumentException
- ifpruferSequence
is invalid.
-
PruferTreeGenerator
public PruferTreeGenerator(int n)
Construct a new PruferTreeGenerator.- Parameters:
n
- number of vertices to be generated- Throws:
java.lang.IllegalArgumentException
- ifn
is ≤ 0
-
PruferTreeGenerator
public PruferTreeGenerator(int n, long seed)
Construct a new PruferTreeGenerator.- Parameters:
n
- number of vertices to be generatedseed
- seed for the random number generator- Throws:
java.lang.IllegalArgumentException
- ifn
is ≤ 0
-
PruferTreeGenerator
public PruferTreeGenerator(int n, java.util.Random rng)
Construct a new PruferTreeGenerator- Parameters:
n
- number of vertices to be generatedrng
- the random number generator to use- Throws:
java.lang.IllegalArgumentException
- ifn
is ≤ 0java.lang.NullPointerException
- ifrng
isnull
-
-
Method Detail
-
generateGraph
public void generateGraph(Graph<V,E> target, java.util.Map<java.lang.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 interfaceGraphGenerator<V,E,V>
- Parameters:
target
- the target graphresultMap
- not used by this generator, can be null- Throws:
java.lang.NullPointerException
- iftarget
isnull
java.lang.IllegalArgumentException
- iftarget
is not undirectedjava.lang.IllegalArgumentException
- iftarget
is not empty
-
-