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< node >	m_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 54 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

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.

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 76 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 108 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 106 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 83 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 81 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 85 of file LCA.h.

m_n

const int ogdf::LCA::m_n

private

number of nodes in graph

Definition at line 80 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 82 of file LCA.h.

m_representative

NodeArray<int> ogdf::LCA::m_representative

private

Euler[Representative[v]] = v.

Definition at line 84 of file LCA.h.

m_root

const node ogdf::LCA::m_root

private

the root of the tree

Definition at line 79 of file LCA.h.

m_table

Array<int> ogdf::LCA::m_table

private

preprocessed M[i,j] array

Definition at line 86 of file LCA.h.

---

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

• include/ogdf/tree/LCA.h