Trie.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): David Salinas
4  *
5  * Copyright (C) 2014 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_
12 #define SKELETON_BLOCKER_INTERNAL_TRIE_H_
13 
14 #include <memory>
15 #include <vector>
16 #include <deque>
17 #include <set>
18 
19 namespace Gudhi {
20 
21 namespace skeleton_blocker {
22 
23 template<typename SimplexHandle>
24 struct Trie {
25  typedef SimplexHandle Simplex;
26  typedef typename SimplexHandle::Vertex_handle Vertex_handle;
27 
28  Vertex_handle v;
29  std::vector<std::shared_ptr<Trie> > childs;
30  // std::vector<std::unique_ptr<Trie> > childs; -> use of deleted function
31  private:
32  const Trie* parent_;
33 
34  public:
35  Trie() : parent_(0) { }
36 
37  Trie(Vertex_handle v_) : v(v_), parent_(0) { }
38 
39  Trie(Vertex_handle v_, Trie* parent) : v(v_), parent_(parent) { }
40 
41  bool operator==(const Trie& other) const {
42  return (v == other.v);
43  }
44 
45  void add_child(Trie* child) {
46  if (child) {
47  std::shared_ptr<Trie> ptr_to_add(child);
48  childs.push_back(ptr_to_add);
49  child->parent_ = this;
50  }
51  }
52 
53  typedef typename Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator;
54 
55  Trie* make_trie(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
56  if (s_it == s_end) {
57  return 0;
58  } else {
59  Trie* res = new Trie(*s_it);
60  Trie* child = make_trie(++s_it, s_end);
61  res->add_child(child);
62  return res;
63  }
64  }
65 
66  private:
67  // go down recursively in the tree while advancing the simplex iterator.
68  // when it reaches a leaf, it inserts the remaining that is not present
69  void add_simplex_helper(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
70  assert(*s_it == v);
71  ++s_it;
72  if (s_it == s_end) return;
73  if (!is_leaf()) {
74  for (auto child : childs) {
75  if (child->v == *s_it)
76  return child->add_simplex_helper(s_it, s_end);
77  }
78  // s_it is not found and needs to be inserted
79  }
80  // not leaf -> remaining of s needs to be inserted
81  Trie * son_with_what_remains_of_s(make_trie(s_it, s_end));
82  add_child(son_with_what_remains_of_s);
83  return;
84  }
85 
86  void maximal_faces_helper(std::vector<Simplex>& res) const {
87  if (is_leaf()) res.push_back(simplex());
88  else
89  for (auto child : childs)
90  child->maximal_faces_helper(res);
91  }
92 
93  public:
97  void add_simplex(const Simplex& s) {
98  if (s.empty()) return;
99  assert(v == s.first_vertex());
100  add_simplex_helper(s.begin(), s.end());
101  }
102 
103  std::vector<Simplex> maximal_faces() const {
104  std::vector<Simplex> res;
105  maximal_faces_helper(res);
106  return res;
107  }
108 
112  void add_vertices_up_to_the_root(Simplex& res) const {
113  res.add_vertex(v);
114  if (parent_)
115  parent_->add_vertices_up_to_the_root(res);
116  }
117 
118  Simplex simplex() const {
119  Simplex res;
120  add_vertices_up_to_the_root(res);
121  return res;
122  }
123 
124  bool is_leaf() const {
125  return childs.empty();
126  }
127 
128  bool is_root() const {
129  return parent_ == 0;
130  }
131 
132  const Trie* parent() {
133  return parent_;
134  }
135 
136  void remove_leaf() {
137  assert(is_leaf());
138  if (!is_root())
139  parent_->childs.erase(this);
140  }
141 
145  bool contains(const Simplex& s) const {
146  Trie const* current = this;
147  if (s.empty()) return true;
148  if (current->v != s.first_vertex()) return false;
149  auto s_pos = s.begin();
150  ++s_pos;
151  while (s_pos != s.end() && current != 0) {
152  bool found = false;
153  for (const auto child : current->childs) {
154  if (child->v == *s_pos) {
155  ++s_pos;
156  current = child.get();
157  found = true;
158  break;
159  }
160  }
161  if (!found) return false;
162  }
163  return current != 0;
164  }
165 
166  Trie* go_bottom_left() {
167  if (is_leaf())
168  return this;
169  else
170  return (*childs.begin())->go_bottom_left();
171  }
172 
173  friend std::ostream& operator<<(std::ostream& stream, const Trie& trie) {
174  stream << "T( " << trie.v << " ";
175  for (auto t : trie.childs)
176  stream << *t;
177  stream << ")";
178  return stream;
179  }
180 };
181 
182 template<typename SimplexHandle>
183 struct Tries {
184  typedef typename SimplexHandle::Vertex_handle Vertex_handle;
185  typedef SimplexHandle Simplex;
186 
187  typedef Trie<Simplex> STrie;
188 
189  template<typename SimpleHandleOutputIterator>
190  Tries(unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) :
191  cofaces_(num_vertices, 0) {
192  for (auto i = 0u; i < num_vertices; ++i)
193  cofaces_[i] = new STrie(Vertex_handle(i));
194  for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) {
195  if (s_it->dimension() >= 1)
196  cofaces_[s_it->first_vertex()]->add_simplex(*s_it);
197  }
198  }
199 
200  ~Tries() {
201  for (STrie* t : cofaces_)
202  delete t;
203  }
204 
205  // return a simplex that consists in all u such uv is an edge and u>v
206 
207  Simplex positive_neighbors(Vertex_handle v) const {
208  Simplex res;
209  for (auto child : cofaces_[v]->childs)
210  res.add_vertex(child->v);
211  return res;
212  }
213 
214  bool contains(const Simplex& s) const {
215  auto first_v = s.first_vertex();
216  return cofaces_[first_v]->contains(s);
217  }
218 
219  friend std::ostream& operator<<(std::ostream& stream, const Tries& tries) {
220  for (auto trie : tries.cofaces_)
221  stream << *trie << std::endl;
222  return stream;
223  }
224 
225  // init_next_dimension must be called first
226 
227  std::vector<Simplex> next_dimension_simplices() const {
228  std::vector<Simplex> res;
229  while (!(to_see_.empty()) && (to_see_.front()->simplex().dimension() == current_dimension_)) {
230  res.emplace_back(to_see_.front()->simplex());
231  for (auto child : to_see_.front()->childs)
232  to_see_.push_back(child.get());
233  to_see_.pop_front();
234  }
235  ++current_dimension_;
236  return res;
237  }
238 
239  void init_next_dimension() const {
240  for (auto trie : cofaces_)
241  to_see_.push_back(trie);
242  }
243 
244  private:
245  mutable std::deque<STrie*> to_see_;
246  mutable int current_dimension_ = 0;
247  std::vector<STrie*> cofaces_;
248 };
249 
250 } // namespace skeleton_blocker
251 
252 namespace skbl = skeleton_blocker;
253 
254 } // namespace Gudhi
255 
256 #endif // SKELETON_BLOCKER_INTERNAL_TRIE_H_
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHI  Version 3.4.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jan 22 2021 10:27:48 for GUDHI by Doxygen 1.9.1