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 Detail

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