Package org.graph4j.converters

Class PruferTreeEncoder

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.converters.PruferTreeEncoder

public class PruferTreeEncoder
extends SimpleGraphAlgorithm

Encodes a tree to its Prufer sequence. 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

Field Summary

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
PruferTreeEncoder(Graph tree)	Creates a new encoder.

Method Summary

Modifier and Type	Method	Description
int[]	createSequence()	Encodes a tree to its Prufer sequence.

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

PruferTreeEncoder

public PruferTreeEncoder(Graph tree)

Creates a new encoder. The constructor does not verify if the input graph is actually a tree.

Parameters:

tree - the input tree.

Method Details

createSequence

public int[] createSequence()

Encodes a tree to its Prufer sequence.

Returns:

the Prufer sequence of the tree.

Throws:

NotATreeException - if the graph is not a tree.