Package com.jgalgo.alg.tree

Class TreePathMaximaHagerup

java.lang.Object

com.jgalgo.alg.tree.TreePathMaximaAbstract

com.jgalgo.alg.tree.TreePathMaximaHagerup

All Implemented Interfaces:

TreePathMaxima

public class TreePathMaximaHagerup
extends TreePathMaximaAbstract

Hagerup's Tree Path Maxima (TPM) linear time algorithm.

The algorithm runs in \(O(n + m)\) where \(n\) is the number of vertices in the tree and \(m\) is the number of queries. It also uses \(O(n + m)\) space.

Based on 'Linear verification for spanning trees' by J Komlos (1985), 'A Simpler Minimum Spanning Tree Verification Algorithm' by V King (1997) and 'An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees' by T Hagerup (2009).

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.TreePathMaxima

TreePathMaxima.IQueries, TreePathMaxima.IResult, TreePathMaxima.Queries<V,E>, TreePathMaxima.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
TreePathMaximaHagerup()	Create a new TPM object.

Method Summary

Modifier and Type	Method	Description
void	setBitsLookupTablesEnable(boolean enable)	Enable/disable the use of bits lookup tables.

Methods inherited from class com.jgalgo.alg.tree.TreePathMaximaAbstract

computeHeaviestEdgeInTreePaths

Methods inherited from class java.lang.Object

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

Constructor Details

TreePathMaximaHagerup

public TreePathMaximaHagerup()

Create a new TPM object.

Please prefer using TreePathMaxima.newInstance() to get a default implementation for the TreePathMaxima interface.

Method Details

setBitsLookupTablesEnable

public void setBitsLookupTablesEnable(boolean enable)

Enable/disable the use of bits lookup tables.

Some operations on integers such such as popcount (Integer.bitCount(int)) or ctz (Integer.numberOfTrailingZeros(int)) are assumed to be implemented in \(O(1)\) by the algorithm. According to theoretical papers its possible to implement this operations in 'real' \(O(1)\) with lookup tables. In practice, integers are 32bit numbers and all such operations are fast without any lookup tables.

This method enable or disable the use of bits lookup tables.

Parameters:

enable - if true bits lookup table will be constructed and used, else methods from Integer will be used.