|
|||
|
|
|
|||
|
|
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. | |
| node | call (node u, node v) const |
Returns the LCA of two nodes u and v. | |
| int | level (node v) const |
| Returns the level of a node. The level of the root is 0. | |
Private Member Functions | |
| void | buildTable () |
| Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from. | |
| 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. | |
| int | rmq (int u, int v) const |
Returns the internal index pointing to the LCA between two nodes u and v. | |
| const int & | sparseTable (int i, int j) const |
Access the sparse table at [i, j]. | |
| int & | sparseTable (int i, int j) |
Private Attributes | |
| Array< node > | m_euler |
| Euler[i] is i-th node visited in Euler Tour. | |
| const int | m_len |
| length of the RMQ array (always 2 m_n - 1) | |
| Array< int > | m_level |
| L[i] is distance of node E[i] from root. | |
| const int | m_n |
| number of nodes in graph | |
| const int | m_rangeJ |
| always floor(log(m_len)) (size of a row in the table) | |
| NodeArray< int > | m_representative |
| Euler[Representative[v]] = v. | |
| const node | m_root |
| the root of the tree | |
| Array< int > | m_table |
| preprocessed M[i,j] array | |
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)
Builds the LCA data structure for an arborescence.
If root is not provided, it is computed in additional O(n) time.
| G | an arborescence |
| root | optional root of the arborescence |
G is reachable from the root via a unique directed path, that is, G is an arborescence.
|
private |
Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from.
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.
Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills Euler tour and Level arrays.
Returns the internal index pointing to the LCA between two nodes u and v.