OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
LCA.h
Go to the documentation of this file.
1
34#pragma once
35
36#include <ogdf/basic/Graph.h>
37
38namespace ogdf {
39
53public:
63 explicit LCA(const Graph& G, node root = nullptr);
64
71 node call(node u, node v) const;
72
74 int level(node v) const { return m_n == 1 ? 0 : m_level[m_representative[v]]; }
75
76private:
77 const node m_root;
78 const int m_n;
79 const int m_len;
80 const int m_rangeJ;
85
90 void dfs(const Graph& G, node root);
91
96 void buildTable();
97
104 const int& sparseTable(int i, int j) const { return m_table[i * m_rangeJ + j - 1]; }
105
106 int& sparseTable(int i, int j) { return m_table[i * m_rangeJ + j - 1]; }
107
109
114 int rmq(int u, int v) const;
115};
116
117}
Includes declaration of graph class.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to comput...
Definition LCA.h:52
int level(node v) const
Returns the level of a node. The level of the root is 0.
Definition LCA.h:74
int & sparseTable(int i, int j)
Definition LCA.h:106
LCA(const Graph &G, node root=nullptr)
Builds the LCA data structure for an arborescence.
Array< int > m_level
L[i] is distance of node E[i] from root.
Definition LCA.h:83
void dfs(const Graph &G, node root)
Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills...
int rmq(int u, int v) const
Returns the internal index pointing to the LCA between two nodes u and v.
node call(node u, node v) const
Returns the LCA of two nodes u and v.
Array< node > m_euler
Euler[i] is i-th node visited in Euler Tour.
Definition LCA.h:81
NodeArray< int > m_representative
Euler[Representative[v]] = v.
Definition LCA.h:82
const int m_rangeJ
always floor(log(m_len)) (size of a row in the table)
Definition LCA.h:80
Array< int > m_table
preprocessed M[i,j] array
Definition LCA.h:84
const int m_n
number of nodes in graph
Definition LCA.h:78
const int m_len
length of the RMQ array (always 2 m_n - 1)
Definition LCA.h:79
const int & sparseTable(int i, int j) const
Access the sparse table at [i, j].
Definition LCA.h:104
const node m_root
the root of the tree
Definition LCA.h:77
void buildTable()
Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101