Package com.jgalgo

Interface LowestCommonAncestorDynamic

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 nodes, while supporting LCA queries.

 
 LowestCommonAncestorDynamic lca = LowestCommonAncestorDynamic.newBuilder().build();
 Node rt = lca.initTree();
 Node n1 = lca.addLeaf(rt);
 Node n2 = lca.addLeaf(rt);
 Node n3 = lca.addLeaf(n1);

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

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

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	LowestCommonAncestorDynamic.Builder	A builder for LowestCommonAncestorDynamic objects.
static interface	LowestCommonAncestorDynamic.Node	A tree node in an LowestCommonAncestorDynamic data structure.

Method Summary

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

Method Detail

initTree

LowestCommonAncestorDynamic.Node initTree()

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

Returns:

the new root node

Throws:

IllegalStateException - if the tree is not empty

addLeaf

LowestCommonAncestorDynamic.Node addLeaf(LowestCommonAncestorDynamic.Node parent)

Add a new leaf node to the tree.

Parameters:

parent - parent of the new node

Returns:

the new node

findLowestCommonAncestor

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

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

Parameters:

u - the first node

v - the second node

Returns:

the lowest common ancestor of the two nodes

size

int size()

Get the number of nodes in the tree.

Returns:

number of nodes in the tree

clear

void clear()

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

newBuilder

static LowestCommonAncestorDynamic.Builder newBuilder()

Create a new dynamic LCA algorithm builder.

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

Returns:

a new builder that can build LowestCommonAncestorDynamic objects