Package com.jgalgo.alg.tree

Class LowestCommonAncestorOfflineAbstract

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorOfflineAbstract

All Implemented Interfaces:

LowestCommonAncestorOffline

Direct Known Subclasses:

LowestCommonAncestorOfflineUnionFind

public abstract class LowestCommonAncestorOfflineAbstract
extends Object
implements LowestCommonAncestorOffline

Abstract class for offline LCA computation.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.LowestCommonAncestorOffline

LowestCommonAncestorOffline.IQueries, LowestCommonAncestorOffline.IResult, LowestCommonAncestorOffline.Queries<V,E>, LowestCommonAncestorOffline.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
LowestCommonAncestorOfflineAbstract()	Default constructor.

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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LowestCommonAncestorOfflineAbstract

public LowestCommonAncestorOfflineAbstract()

Default constructor.

Method Details

findLowestCommonAncestors

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

Description copied from interface: LowestCommonAncestorOffline

Find the lowest common ancestors of the given queries.

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

Specified by:

findLowestCommonAncestors in interface LowestCommonAncestorOffline

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