Package com.jgalgo.alg.tree

Class LowestCommonAncestorStaticAbstract

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorStaticAbstract

All Implemented Interfaces:

LowestCommonAncestorStatic

Direct Known Subclasses:

LowestCommonAncestorStaticRmq

public abstract class LowestCommonAncestorStaticAbstract
extends Object
implements LowestCommonAncestorStatic

Abstract class for static LCA data structures.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

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

LowestCommonAncestorStatic.DataStructure<V,E>, LowestCommonAncestorStatic.IDataStructure

Constructor Summary

Constructors

Constructor	Description
LowestCommonAncestorStaticAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V, E> LowestCommonAncestorStatic.DataStructure<V,E>	preProcessTree(Graph<V,E> tree, V root)	Perform a static pre processing of a tree for future LCA (Lowest common ancestor) queries.

Methods inherited from class java.lang.Object

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

Constructor Details

LowestCommonAncestorStaticAbstract

public LowestCommonAncestorStaticAbstract()

Default constructor.

Method Details

preProcessTree

public <V,
E>
LowestCommonAncestorStatic.DataStructure<V,E> preProcessTree(Graph<V,E> tree,
 V root)

Description copied from interface: LowestCommonAncestorStatic

Perform a static pre processing of a tree for future LCA (Lowest common ancestor) queries.

If g is IntGraph, the returned object is LowestCommonAncestorStatic.IDataStructure.

Specified by:

preProcessTree in interface LowestCommonAncestorStatic

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

tree - a tree

root - root of the tree

Returns:

a data structure built from the preprocessing, that can answer LCA queries efficiently