Package com.jgalgo

Interface LowestCommonAncestorStatic

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 implementation of this interface achieve linear or near linear preprocessing time and constant or logarithmic query time.

 
 Graph tree = Graph.newBuilderUndirected().build();
 int rt = tree.addVertex();
 int v1 = tree.addVertex();
 int v2 = tree.addVertex();
 int v3 = tree.addVertex();
 int v4 = tree.addVertex();
 int v5 = tree.addVertex();

 tree.addEdge(rt, v1);
 tree.addEdge(v1, v2);
 tree.addEdge(v1, v3);
 tree.addEdge(rt, v4);
 tree.addEdge(v4, v5);

 LowestCommonAncestorStatic lca = LowestCommonAncestorStatic.newBuilder().build();
 LowestCommonAncestorStatic.DataStructure lcaDS = lca.preProcessTree(tree, rt);
 assert lcaDS.findLowestCommonAncestor(v1, v4) == rt;
 assert lcaDS.findLowestCommonAncestor(v2, v3) == v1;
 assert lcaDS.findLowestCommonAncestor(v4, v5) == v4;
 assert lcaDS.findLowestCommonAncestor(v2, v5) == rt;
 

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	LowestCommonAncestorStatic.Builder	A builder for LowestCommonAncestorStatic objects.
static interface	LowestCommonAncestorStatic.DataStructure	Data structure result created from a static LCA pre-processing.

Method Summary

Modifier and Type	Method	Description
static LowestCommonAncestorStatic.Builder	newBuilder()	Create a new static LCA algorithm builder.
LowestCommonAncestorStatic.DataStructure	preProcessTree(Graph tree, int root)	Perform a static pre processing of a tree for future LCA (Lowest common ancestor) queries.

Method Detail

preProcessTree

LowestCommonAncestorStatic.DataStructure preProcessTree(Graph tree,
                                                        int root)

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

Parameters:

tree - a tree

root - root of the tree

Returns:

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

newBuilder

static LowestCommonAncestorStatic.Builder newBuilder()

Create a new static LCA algorithm builder.

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

Returns:

a new builder that can build LowestCommonAncestorStatic objects