Interface LowestCommonAncestorOffline

All Known Implementing Classes:

LowestCommonAncestorOfflineAbstract, LowestCommonAncestorOfflineUnionFind

public interface LowestCommonAncestorOffline

An algorithm for computing the lowest common ancestor (LCA) of two vertices in a tree, offline.

Given a rooted tree, the lowest common ancestor (LCA) of two vertices u and v is the lowest vertex (farthest to root) that has both u and v as descendants. The offline version of this problem is given a tree and a set of pairs of vertices, find the LCA of each pair. There are also the static and online versions of this problem.

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

Author:

Barak Ugav

See Also:

• LowestCommonAncestorStatic
• LowestCommonAncestorDynamic

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	LowestCommonAncestorOffline.IQueries	Queries container for LowestCommonAncestorOffline computations for IntGraph.
static interface	LowestCommonAncestorOffline.IResult	Result of a LowestCommonAncestorOffline computation for IntGraph.
static interface	LowestCommonAncestorOffline.Queries<V,E>	Queries container for LowestCommonAncestorOffline computations.
static interface	LowestCommonAncestorOffline.Result<V,E>	Result of a LowestCommonAncestorOffline computation.

Method Summary

Modifier and Type	Method	Description
<V, E> LowestCommonAncestorOffline.Result<V,E>	findLowestCommonAncestors(Graph<V,E> tree, V root, LowestCommonAncestorOffline.Queries<V,E> queries)	Find the lowest common ancestors of the given queries.
static LowestCommonAncestorOffline	newInstance()	Create a new offline LCA algorithm object.

Method Details

findLowestCommonAncestors

<V,
E> LowestCommonAncestorOffline.Result<V,E> findLowestCommonAncestors(Graph<V,E> tree,
 V root,
 LowestCommonAncestorOffline.Queries<V,E> queries)

Find the lowest common ancestors of the given queries.

If g is IntGraph, the returned object is LowestCommonAncestorOffline.IResult.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

tree - the tree

root - the root of the tree

queries - the queries

Returns:

the lowest common ancestors of the given queries

newInstance

static LowestCommonAncestorOffline newInstance()

Create a new offline LCA algorithm object.

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

Returns:

a default implementation of LowestCommonAncestorOffline