Package com.jgalgo.alg.tree

Interface LowestCommonAncestorStatic

All Known Implementing Classes:

LowestCommonAncestorStaticAbstract, LowestCommonAncestorStaticRmq

public interface LowestCommonAncestorStatic

Static Lowest Common Ancestor (LCA) algorithm.

The lowest common ancestor of two vertices in a tree is the vertex that appear in both vertices paths to the root (common ancestor), and its farthest from the root (lowest). Given a tree $G=(V,E)$, we would like to pre process it and then answer queries of the type "what is the lower common ancestor of two vertices $u$ and $v$?".

Most implementations of this interface achieve linear or near linear preprocessing time and constant or logarithmic query time.

Use newInstance() to get a default implementation of this interface.

 
 Graph<String, Integer> tree = Graph.newUndirected();
 tree.addVertex("Grandfather Bob");
 tree.addVertex("Father John");
 tree.addVertex("Me");
 tree.addVertex("Sister Jane");
 tree.addVertex("Uncle Nick");
 tree.addVertex("Cousin Alice");

 tree.addEdge("Grandfather Bob", "Father John", 1957);
 tree.addEdge("Father John", "Me", 1985);
 tree.addEdge("Father John", "Sister Jane", 1987);
 tree.addEdge("Grandfather Bob", "Uncle Nick", 1960);
 tree.addEdge("Uncle Nick", "Cousin Alice", 1990);

 LowestCommonAncestorStatic lca = LowestCommonAncestorStatic.newInstance();
 LowestCommonAncestorStatic.DataStructure<String, Integer> lcaDS = lca.preProcessTree(tree, "Grandfather Bob");
 assert lcaDS.findLowestCommonAncestor("Father John", "Uncle Nick").equals("Grandfather Bob");
 assert lcaDS.findLowestCommonAncestor("Me", "Sister Jane").equals("Father John");
 assert lcaDS.findLowestCommonAncestor("Uncle Nick", "Cousin Alice").equals("Uncle Nick");
 assert lcaDS.findLowestCommonAncestor("Me", "Cousin Alice").equals("Grandfather Bob");
 

Author:

Barak Ugav

See Also:

• LowestCommonAncestorDynamic
• LowestCommonAncestorOffline

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	LowestCommonAncestorStatic.DataStructure<V,E>	Data structure result created from a static LCA pre-processing.
static interface	LowestCommonAncestorStatic.IDataStructure	Data structure result created from a static LCA pre-processing for IntGraph.

Method Summary

Modifier and Type	Method	Description
static LowestCommonAncestorStatic	newInstance()	Create a new algorithm for static LCA queries.
<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.

Method Details

preProcessTree

<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.

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

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

newInstance

static LowestCommonAncestorStatic newInstance()

Create a new algorithm for static LCA queries.

This is the recommended way to instantiate a new LowestCommonAncestorStatic object.

Returns:

a default implementation of LowestCommonAncestorStatic