TTK
Loading...
Searching...
No Matches
LowestCommonAncestor.h
Go to the documentation of this file.
1
8
9#pragma once
10
11// ttk includes
12#include <Debug.h>
13#include <RangeMinimumQuery.h>
14// STL includes
15#include <array>
16#include <vector>
17
18namespace ttk {
19
20 class LowestCommonAncestor : virtual public Debug {
21 public:
22 class Node {
23 public:
24 inline void setAncestor(const int &id) {
25 ancestor_ = id;
26 }
27 inline void addSuccessor(const int &id) {
28 successor_.push_back(id);
29 }
30 inline int getNumberOfSuccessors() const {
31 return static_cast<int>(successor_.size());
32 }
33 inline int getAncestorId() const {
34 return ancestor_;
35 }
36 inline int getSuccessorId(const int &id) const {
37 if(id < static_cast<int>(successor_.size())) {
38 return successor_[id];
39 } else {
40 return -1;
41 }
42 }
43
44 protected:
45 int ancestor_{};
46 std::vector<int> successor_{};
47 };
48
50
53 inline int addNode() {
54 node_.emplace_back();
55 int id = static_cast<int>(node_.size());
56 node_[id].setAncestor(id);
57 return id;
58 }
59
60 inline void addNodes(const unsigned int &number) {
61 node_.resize(node_.size() + number);
62 for(unsigned int i = node_.size() - number; i < node_.size(); i++) {
63 node_[i].setAncestor(i);
64 }
65 }
66
68 inline unsigned int getNumberOfNodes() const {
69 return node_.size();
70 }
71
73 inline Node &getNode(const unsigned int &id) {
74 return node_[id];
75 }
76
79 int preprocess();
80
84 inline int query(int i, int j) const {
86 std::swap(i, j);
87 }
88 return nodeOrder_[RMQuery(
90 }
91
92 protected:
93 int computeBlocs();
95 int RMQuery(const int &i, const int &j) const;
96 inline unsigned int min_pos_3(const std::array<int, 3> &triplet) const {
97 if(triplet[0] < triplet[1]) {
98 if(triplet[0] < triplet[2]) {
99 return 0;
100 } else {
101 return 2;
102 }
103 } else {
104 if(triplet[1] < triplet[2]) {
105 return 1;
106 } else {
107 return 2;
108 }
109 }
110 }
111
112 protected:
113 /* Tree structure */
114 std::vector<Node> node_{};
115
116 /* Eulerian Transverse */
117 std::vector<int> nodeOrder_{};
118 std::vector<int> nodeDepth_{};
119 std::vector<int> nodeFirstAppearance_{};
120
121 /* Range Minimum Query */
123 // Boundaries of blocs
124 std::vector<std::pair<int, int>> blocPartition_{};
125 // Min values
126 std::vector<int> blocMinimumValue_{};
127 // RMQ of the blocMinimumValue_ vector
129 // Positions of min values
130 std::vector<int> blocMinimumPosition_{};
131 // All queries for each possible bloc (positions)
132 std::vector<std::vector<std::vector<int>>> normalizedBlocTable_{};
133 // Corresponding normalized bloc for each bloc of nodeDepth_
134 std::vector<int> blocToNormalizedBloc_{};
135 };
136
137} // namespace ttk
Minimalist debugging class.
Definition: Debug.h:88
int getSuccessorId(const int &id) const
Class to answer the lowest common ancestor requests of pairs of nodes in a tree in constant time afte...
int query(int i, int j) const
int RMQuery(const int &i, const int &j) const
std::vector< int > blocMinimumValue_
std::vector< std::pair< int, int > > blocPartition_
std::vector< int > blocMinimumPosition_
Node & getNode(const unsigned int &id)
std::vector< std::vector< std::vector< int > > > normalizedBlocTable_
unsigned int min_pos_3(const std::array< int, 3 > &triplet) const
RangeMinimumQuery< int > blocMinimumValueRMQ_
unsigned int getNumberOfNodes() const
Get the number of nodes in the tree.
std::vector< int > nodeFirstAppearance_
void addNodes(const unsigned int &number)
std::vector< int > blocToNormalizedBloc_
Class to answer range minimum queries in an array in constant time after a linearithmic time preproce...
The Topology ToolKit.
std::tuple< ttk::SimplexId, ttk::SimplexId, ttk::SimplexId > triplet
Persistence pair type (with persistence in double)