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 = GraphFactory.newUndirected().newGraph(); 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 forLowestCommonAncestorStatic
objects.static interface
LowestCommonAncestorStatic.DataStructure
Data structure result created from a static LCA pre-processing.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods 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 treeroot
- 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
-
-