Package com.jgalgo

Interface LowestCommonAncestorStatic


  • public interface LowestCommonAncestorStatic
    Static Lowest Common Ancestor (LCA) algorithm.

    The lowest common ancestor of two vertices in a tree is the vertex that appear in both vertices paths to the root (common ancestor), and its farthest from the root (lowest). Given a tree G=(V,E), we would like to pre process it and then answer queries of the type "what is the lower common ancestor of two vertices u and v?".

    Most implementation of this interface achieve linear or near linear preprocessing time and constant or logarithmic query time.

     
     Graph tree = GraphFactory.newUndirected().newGraph();
     int rt = tree.addVertex();
     int v1 = tree.addVertex();
     int v2 = tree.addVertex();
     int v3 = tree.addVertex();
     int v4 = tree.addVertex();
     int v5 = tree.addVertex();
    
     tree.addEdge(rt, v1);
     tree.addEdge(v1, v2);
     tree.addEdge(v1, v3);
     tree.addEdge(rt, v4);
     tree.addEdge(v4, v5);
    
     LowestCommonAncestorStatic lca = LowestCommonAncestorStatic.newBuilder().build();
     LowestCommonAncestorStatic.DataStructure lcaDS = lca.preProcessTree(tree, rt);
     assert lcaDS.findLowestCommonAncestor(v1, v4) == rt;
     assert lcaDS.findLowestCommonAncestor(v2, v3) == v1;
     assert lcaDS.findLowestCommonAncestor(v4, v5) == v4;
     assert lcaDS.findLowestCommonAncestor(v2, v5) == rt;
     
    Author:
    Barak Ugav