Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to compute lowest common ancestors (LCAs) in arborescences (not arbitrary directed acyclic graphs). More...

#include <ogdf/tree/LCA.h>

Public Member Functions

 LCA (const Graph &G, node root=nullptr)
 Builds the LCA data structure for an arborescence. More...
 
node call (node u, node v) const
 Returns the LCA of two nodes u and v. More...
 
int level (node v) const
 Returns the level of a node. The level of the root is 0. More...
 

Private Member Functions

void buildTable ()
 Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from. More...
 
void dfs (const Graph &G, node root)
 Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills Euler tour and Level arrays. More...
 
int rmq (int u, int v) const
 Returns the internal index pointing to the LCA between two nodes u and v. More...
 
const int & sparseTable (int i, int j) const
 Access the sparse table at [i, j]. More...
 
int & sparseTable (int i, int j)
 

Private Attributes

Array< nodem_euler
 Euler[i] is i-th node visited in Euler Tour. More...
 
const int m_len
 length of the RMQ array (always 2 m_n - 1) More...
 
Array< int > m_level
 L[i] is distance of node E[i] from root. More...
 
const int m_n
 number of nodes in graph More...
 
const int m_rangeJ
 always floor(log(m_len)) (size of a row in the table) More...
 
NodeArray< int > m_representative
 Euler[Representative[v]] = v. More...
 
const node m_root
 the root of the tree More...
 
Array< int > m_table
 preprocessed M[i,j] array More...
 

Detailed Description

Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to compute lowest common ancestors (LCAs) in arborescences (not arbitrary directed acyclic graphs).

This implementation is based on:

(M. Bender, M. Farach-Colton, The LCA problem revisited, LATIN '00, volume 1776 of LNCS, pages 88-94, Springer, 2000)

Definition at line 52 of file LCA.h.

Constructor & Destructor Documentation

◆ LCA()

ogdf::LCA::LCA ( const Graph G,
node  root = nullptr 
)
explicit

Builds the LCA data structure for an arborescence.

If root is not provided, it is computed in additional O(n) time.

Parameters
Gan arborescence
rootoptional root of the arborescence
Precondition
Each node in G is reachable from the root via a unique directed path, that is, G is an arborescence.

Member Function Documentation

◆ buildTable()

void ogdf::LCA::buildTable ( )
private

Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from.

◆ call()

node ogdf::LCA::call ( node  u,
node  v 
) const

Returns the LCA of two nodes u and v.

If u and v are the same node, u itself is defined to be the LCA, not its father.

◆ dfs()

void ogdf::LCA::dfs ( const Graph G,
node  root 
)
private

Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills Euler tour and Level arrays.

◆ level()

int ogdf::LCA::level ( node  v) const
inline

Returns the level of a node. The level of the root is 0.

Definition at line 74 of file LCA.h.

◆ rmq()

int ogdf::LCA::rmq ( int  u,
int  v 
) const
private

Returns the internal index pointing to the LCA between two nodes u and v.

Returns
Internal index pointing to LCA

◆ sparseTable() [1/2]

int& ogdf::LCA::sparseTable ( int  i,
int  j 
)
inlineprivate

Definition at line 111 of file LCA.h.

◆ sparseTable() [2/2]

const int& ogdf::LCA::sparseTable ( int  i,
int  j 
) const
inlineprivate

Access the sparse table at [i, j].

Precondition
0 <= i < m_len and 1 <= j <= m_rangeJ

Definition at line 107 of file LCA.h.

Member Data Documentation

◆ m_euler

Array<node> ogdf::LCA::m_euler
private

Euler[i] is i-th node visited in Euler Tour.

Definition at line 84 of file LCA.h.

◆ m_len

const int ogdf::LCA::m_len
private

length of the RMQ array (always 2 m_n - 1)

Definition at line 82 of file LCA.h.

◆ m_level

Array<int> ogdf::LCA::m_level
private

L[i] is distance of node E[i] from root.

Definition at line 86 of file LCA.h.

◆ m_n

const int ogdf::LCA::m_n
private

number of nodes in graph

Definition at line 81 of file LCA.h.

◆ m_rangeJ

const int ogdf::LCA::m_rangeJ
private

always floor(log(m_len)) (size of a row in the table)

Definition at line 83 of file LCA.h.

◆ m_representative

NodeArray<int> ogdf::LCA::m_representative
private

Euler[Representative[v]] = v.

Definition at line 85 of file LCA.h.

◆ m_root

const node ogdf::LCA::m_root
private

the root of the tree

Definition at line 80 of file LCA.h.

◆ m_table

Array<int> ogdf::LCA::m_table
private

preprocessed M[i,j] array

Definition at line 87 of file LCA.h.


The documentation for this class was generated from the following file: