Package org.jgrapht.alg
Class TarjanLowestCommonAncestor.Worker
- java.lang.Object
-
- org.jgrapht.alg.TarjanLowestCommonAncestor.Worker
-
- Enclosing class:
- TarjanLowestCommonAncestor<V,E>
private class TarjanLowestCommonAncestor.Worker extends java.lang.Object
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Worker(java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.List<V>
calculate(V u)
Calculates the LCM as described by http://en.wikipedia.org/wiki/Tarjan's_off-line_lowest_common_ancestors_algorithmfunction TarjanOLCA(u) MakeSet(u); u.ancestor := u; for each v in u.children do TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.colour := black; for each v such that {u,v} in P do if v.colour == black print "Tarjan's Lowest Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + ".";
-
-
-
Field Detail
-
black
private java.util.Set<V> black
-
lrr
private java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr
-
lrrMap
private TarjanLowestCommonAncestor.MultiMap<V> lrrMap
-
-
Constructor Detail
-
Worker
private Worker(java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr)
-
-
Method Detail
-
calculate
private java.util.List<V> calculate(V u)
Calculates the LCM as described by http://en.wikipedia.org/wiki/Tarjan's_off-line_lowest_common_ancestors_algorithmfunction TarjanOLCA(u) MakeSet(u); u.ancestor := u; for each v in u.children do TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.colour := black; for each v such that {u,v} in P do if v.colour == black print "Tarjan's Lowest Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + ".";
- Parameters:
u
- the starting node (called recursively)- Returns:
- the LCM if found, if not null
-
-