LCA.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
 
namespace ogdf {
 
class OGDF_EXPORT LCA {
public:
    explicit LCA(const Graph& G, node root = nullptr);
 
    node call(node u, node v) const;
 
    int level(node v) const { return m_n == 1 ? 0 : m_level[m_representative[v]]; }
 
private:
    const node m_root; 
    const int m_n; 
    const int m_len; 
    const int m_rangeJ; 
    Array<node> m_euler; 
    NodeArray<int> m_representative; 
    Array<int> m_level; 
    Array<int> m_table; 
 
    void dfs(const Graph& G, node root);
 
    void buildTable();
 
    const int& sparseTable(int i, int j) const { return m_table[i * m_rangeJ + j - 1]; }
 
    int& sparseTable(int i, int j) { return m_table[i * m_rangeJ + j - 1]; }
 
 
    int rmq(int u, int v) const;
};
 
}