Package com.jgalgo.alg.tree

Interface LowestCommonAncestorDynamic

All Known Implementing Classes:

LowestCommonAncestorDynamicGabowInts, LowestCommonAncestorDynamicGabowLongs, LowestCommonAncestorDynamicGabowSimple

public interface LowestCommonAncestorDynamic

Dynamic algorithm for Lowest Common Ancestor (LCA) queries.

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). Algorithm implementing this interface support modifying the tree by adding leafs as children to existing parents vertices, while supporting LCA queries.

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

 
 LowestCommonAncestorDynamic lca = LowestCommonAncestorDynamic.newInstance();
 LowestCommonAncestorDynamic.Vertex rt = lca.initTree();
 LowestCommonAncestorDynamic.Vertex n1 = lca.addLeaf(rt);
 LowestCommonAncestorDynamic.Vertex n2 = lca.addLeaf(rt);
 LowestCommonAncestorDynamic.Vertex n3 = lca.addLeaf(n1);

 assert lca.findLowestCommonAncestor(n1, n2) == rt;
 assert lca.findLowestCommonAncestor(n1, n3) == n1;

 LowestCommonAncestorDynamic.Vertex n4 = lca.addLeaf(n1);
 assert lca.findLowestCommonAncestor(n1, n4) == n1;
 

Author:

Barak Ugav

See Also:

LowestCommonAncestorStatic, LowestCommonAncestorOffline

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	LowestCommonAncestorDynamic.Vertex	A tree vertex in an LowestCommonAncestorDynamic data structure.

Method Summary

Modifier and Type	Method	Description
LowestCommonAncestorDynamic.Vertex	addLeaf(LowestCommonAncestorDynamic.Vertex parent)	Add a new leaf vertex to the tree.
void	clear()	Clear the data structure by removing all vertices in the tree.
LowestCommonAncestorDynamic.Vertex	findLowestCommonAncestor(LowestCommonAncestorDynamic.Vertex u, LowestCommonAncestorDynamic.Vertex v)	Find the lowest common ancestor of two vertices in the tree.
LowestCommonAncestorDynamic.Vertex	initTree()	Initialize the tree the LCA will operate on and create a root vertex.
static LowestCommonAncestorDynamic	newInstance()	Create a new algorithm for dynamic LCA queries.
int	size()	Get the number of vertices in the tree.

Method Detail

initTree

LowestCommonAncestorDynamic.Vertex initTree()

Initialize the tree the LCA will operate on and create a root vertex.

Returns:

the new root vertex

Throws:

IllegalStateException - if the tree is not empty

addLeaf

LowestCommonAncestorDynamic.Vertex addLeaf(LowestCommonAncestorDynamic.Vertex parent)

Add a new leaf vertex to the tree.

Parameters:

parent - parent of the new vertex

Returns:

the new vertex

findLowestCommonAncestor

LowestCommonAncestorDynamic.Vertex findLowestCommonAncestor(LowestCommonAncestorDynamic.Vertex u,
                                                            LowestCommonAncestorDynamic.Vertex v)

Find the lowest common ancestor of two vertices in the tree.

Parameters:

u - the first vertex

v - the second vertex

Returns:

the lowest common ancestor of the two vertices

size

int size()

Get the number of vertices in the tree.

Returns:

number of vertices in the tree

clear

void clear()

Clear the data structure by removing all vertices in the tree.

newInstance

static LowestCommonAncestorDynamic newInstance()

Create a new algorithm for dynamic LCA queries.

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

Returns:

a default implementation of LowestCommonAncestorDynamic