Package org.jgrapht.generate

Class 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 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