org.jgrapht.alg

Class TarjanLowestCommonAncestor<V,E>

java.lang.Object

org.jgrapht.alg.TarjanLowestCommonAncestor<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class TarjanLowestCommonAncestor<V,E>
extends Object

Used to calculate Tarjan's Lowest Common Ancestors Algorithm

Author:

Leo Crawford

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TarjanLowestCommonAncestor.LcaRequestResponse<V> Data transfer object for LCA request and response.

Constructor Summary

Constructors

Constructor and Description
TarjanLowestCommonAncestor(Graph<V,E> g) Create an instance with a reference to the graph that we will find LCAs for

Method Summary

Modifier and Type	Method and Description
List<V>	calculate(V start, List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr) Calculate the LCM's between a set of pairs (a and b) treating start as the root we want to search from, and setting the LCA of each pair in its LCA field.
V	calculate(V start, V a, V b) Calculate the LCM between a and b treating start as the root we want to search from.

Methods inherited from class java.lang.Object

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

Constructor Detail

TarjanLowestCommonAncestor

public TarjanLowestCommonAncestor(Graph<V,E> g)

Create an instance with a reference to the graph that we will find LCAs for

Parameters:

g - the input graph

Method Detail

calculate

public V calculate(V start,
                   V a,
                   V b)

Calculate the LCM between a and b treating start as the root we want to search from.

Parameters:

start - the root of subtree

a - the first vertex

b - the second vertex

Returns:

the least common ancestor

calculate

public List<V> calculate(V start,
                         List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr)

Calculate the LCM's between a set of pairs (a and b) treating start as the root we want to search from, and setting the LCA of each pair in its LCA field.

Parameters:

start - the root of the subtree

lrr - a list of requests-response objects. The answer if stored on these objects at the LCA field.

Returns:

the LCMs