OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::LCA Class Reference

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.

◆ 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
 G an arborescence root optional 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.

◆ 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.

◆ m_euler

 Array 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 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 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 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:
• include/ogdf/tree/LCA.h