Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

LCA.h
Go to the documentation of this file.
1 
34 #pragma once
35 
36 #include <ogdf/basic/Graph.h>
37 
38 namespace ogdf {
39 
53 public:
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
75  {
76  return m_n == 1 ? 0 : m_level[m_representative[v]];
77  }
78 
79 private:
80  const node m_root;
81  const int m_n;
82  const int m_len;
83  const int m_rangeJ;
88 
93  void dfs(const Graph &G, node root);
94 
99  void buildTable();
100 
106  const int &sparseTable(int i, int j) const
108  {
109  return m_table[i * m_rangeJ + j - 1];
110  }
111  int &sparseTable(int i, int j)
112  {
113  return m_table[i * m_rangeJ + j - 1];
114  }
116 
121  int rmq(int u, int v) const;
122 };
123 
124 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::LCA::level
int level(node v) const
Returns the level of a node. The level of the root is 0.
Definition: LCA.h:74
Graph.h
Includes declaration of graph class.
ogdf::LCA::sparseTable
int & sparseTable(int i, int j)
Definition: LCA.h:111
ogdf::LCA::m_root
const node m_root
the root of the tree
Definition: LCA.h:80
ogdf::LCA::m_n
const int m_n
number of nodes in graph
Definition: LCA.h:81
ogdf::NodeArray< int >
ogdf::LCA::m_representative
NodeArray< int > m_representative
Euler[Representative[v]] = v.
Definition: LCA.h:85
ogdf::Array< node >
ogdf::LCA::m_rangeJ
const int m_rangeJ
always floor(log(m_len)) (size of a row in the table)
Definition: LCA.h:83
ogdf::LCA::m_table
Array< int > m_table
preprocessed M[i,j] array
Definition: LCA.h:87
ogdf::LCA
Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to comput...
Definition: LCA.h:52
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::LCA::m_level
Array< int > m_level
L[i] is distance of node E[i] from root.
Definition: LCA.h:86
ogdf::LCA::m_len
const int m_len
length of the RMQ array (always 2 m_n - 1)
Definition: LCA.h:82
ogdf::LCA::m_euler
Array< node > m_euler
Euler[i] is i-th node visited in Euler Tour.
Definition: LCA.h:84
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169