Module org.jgrapht.core
Package 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 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

    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 Details

    • 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 - if n is ≤ 0
      java.lang.IllegalArgumentException - if pruferSequence is null
      java.lang.IllegalArgumentException - if pruferSequence is invalid.

    • PruferTreeGenerator

      public PruferTreeGenerator​(int n)
      Construct a new PruferTreeGenerator.
      Parameters:
      n - number of vertices to be generated
      Throws:
      java.lang.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:
      java.lang.IllegalArgumentException - if n is ≤ 0

    • PruferTreeGenerator

      public PruferTreeGenerator​(int n, java.util.Random rng)
      Construct a new PruferTreeGenerator
      Parameters:
      n - number of vertices to be generated
      rng - the random number generator to use
      Throws:
      java.lang.IllegalArgumentException - if n is ≤ 0
      java.lang.NullPointerException - if rng is null

  • Method Details

    • 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 interface GraphGenerator<V,​E,​V>
      Parameters:
      target - the target graph
      resultMap - not used by this generator, can be null
      Throws:
      java.lang.NullPointerException - if target is null
      java.lang.IllegalArgumentException - if target is not undirected
      java.lang.IllegalArgumentException - if target is not empty