Package org.graph4j.converters

Class PruferTreeDecoder

java.lang.Object
org.graph4j.converters.PruferTreeDecoder
public class PruferTreeDecoder extends Object
Decodes a Prufer sequence to a tree. The sequence must contain values from 0 to the length of the sequence plus 2, representing the vertex numbers of the resulting tree. The time complexity is O(|V|). See: "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."
Author:
Cristian Frăsinaru

  • Constructor Details

    • PruferTreeDecoder

      public PruferTreeDecoder(int[] pruferCode)
      Creates a new decoder.
      Parameters:
      pruferCode - the Prufer sequence.

  • Method Details

    • createTree

      public Graph createTree()
      Decodes a Prufer sequence to a tree.
      Returns:
      the tree corresponding to the Prufer sequence.