iota-0.1.0.0

Safe Haskell	Safe-Inferred
Language	GHC2021

Data.Graph.Tree.LCA

Synopsis

data LCA = LCA {
- firstIndexLCA :: Vector Int
- rmqLCA :: RMQ (Int, Vertex)
}
buildLCA :: Unbox w => SparseGraph w -> Vertex -> LCA
queryLCA :: LCA -> Vertex -> Vertex -> Vertex
queryDepth :: LCA -> Vertex -> Int
queryDist :: LCA -> Vertex -> Vertex -> Int

Documentation

data LCA Source #

Constructors

LCA
Fields firstIndexLCA :: Vector Int first index in Euler Tour rmqLCA :: RMQ (Int, Vertex) Euler Tour RMQ (depth, vertex)

buildLCA :: Unbox w => SparseGraph w -> Vertex -> LCA Source #

queryLCA :: LCA -> Vertex -> Vertex -> Vertex Source #

O(1)

queryDepth :: LCA -> Vertex -> Int Source #

O(1)

queryDist :: LCA -> Vertex -> Vertex -> Int Source #

O(1)