Package com.jgalgo.alg.tree

Algorithms specifically for tree graphs, such as LCA or TPM.

Interface Summary

Interface	Description
LowestCommonAncestorDynamic	Dynamic algorithm for Lowest Common Ancestor (LCA) queries.
LowestCommonAncestorDynamic.Vertex	A tree vertex in an LowestCommonAncestorDynamic data structure.
LowestCommonAncestorOffline	An algorithm for computing the lowest common ancestor (LCA) of two vertices in a tree, offline.
LowestCommonAncestorOffline.IQueries	Queries container for LowestCommonAncestorOffline computations for IntGraph.
LowestCommonAncestorOffline.IResult	Result of a LowestCommonAncestorOffline computation for IntGraph.
LowestCommonAncestorOffline.Queries<V,E>	Queries container for LowestCommonAncestorOffline computations.
LowestCommonAncestorOffline.Result<V,E>	Result of a LowestCommonAncestorOffline computation.
LowestCommonAncestorStatic	Static Lowest Common Ancestor (LCA) algorithm.
LowestCommonAncestorStatic.DataStructure<V,E>	Data structure result created from a static LCA pre-processing.
LowestCommonAncestorStatic.IDataStructure	Data structure result created from a static LCA pre-processing for IntGraph.
TreePathMaxima	Tree Path Maxima (TPM) algorithm.
TreePathMaxima.IQueries	Queries container for TreePathMaxima computations for IntGraph.
TreePathMaxima.IResult	A result object for TreePathMaxima algorithm for IntGraph.
TreePathMaxima.Queries<V,E>	Queries container for TreePathMaxima computations.
TreePathMaxima.Result<V,E>	A result object for TreePathMaxima algorithm.

Class Summary

Class	Description
LowestCommonAncestorDynamicGabowInts	Gabow linear dynamic LCA data structure with 32bit word operations.
LowestCommonAncestorDynamicGabowLongs	Gabow linear dynamic LCA data structure with 64bit word operations.
LowestCommonAncestorDynamicGabowSimple	Gabow implementation for dynamic LCA data structure with \(O(\log^2 n)\) amortized time for addLeaf() operation.
LowestCommonAncestorOfflineAbstract	Abstract class for offline LCA computation.
LowestCommonAncestorOfflineUnionFind	Offline LCA algorithm based on Union-Find data structure.
LowestCommonAncestorStaticAbstract	Abstract class for static LCA data structures.
LowestCommonAncestorStaticRmq	Static LCA implementation using RMQ.
TreePathMaximaAbstract	Abstract class for TPM computations.
TreePathMaximaHagerup	Hagerup's Tree Path Maxima (TPM) linear time algorithm.
Trees	Static methods class for tree graphs.