Package org.jgrapht.alg
Class TarjanLowestCommonAncestor<V,E>
- java.lang.Object
-
- org.jgrapht.alg.TarjanLowestCommonAncestor<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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
-
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
andb
) treatingstart
as the root we want to search from, and setting the LCA of each pair in its LCA fieldV
calculate(V start, V a, V b)
Calculate the LCM betweena
andb
treatingstart
as the root we want to search from.
-
-
-
Method Detail
-
calculate
public V calculate(V start, V a, V b)
Calculate the LCM betweena
andb
treatingstart
as the root we want to search from.- Parameters:
start
- the root of subtreea
- the first vertexb
- 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
andb
) treatingstart
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 subtreelrr
- a list of requests-response objects. The answer if stored on these objects at the LCA field.- Returns:
- the LCMs
-
-