Class TarjanLowestCommonAncestor.Worker

    • 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_algorithm function 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 + ".";
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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_algorithm function 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