TarjanLowestCommonAncestor

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	Description
`static class`	`TarjanLowestCommonAncestor.LcaRequestResponse<V>`	Data transfer object for LCA request and response.
`private static class`	`TarjanLowestCommonAncestor.MultiMap<V>`
`private class`	`TarjanLowestCommonAncestor.Worker`

Field Summary

Fields
Modifier and Type Field Description

private Graph<V,E> g

Constructor Summary

Constructors
Constructor Description

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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - g
```
private Graph<V,E> g
```
- 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