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 java.lang.Object

Used to calculate Tarjan's Lowest Common Ancestors Algorithm

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
java.util.List<V>	calculate(V start, java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr) Calculate the LCMs 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

equals, 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 java.util.List<V> calculate(V start,
                                   java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr)

Calculate the LCMs 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