Trie.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author(s): David Salinas
6  *
7  * Copyright (C) 2014 Inria
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  *
22  */
23 
24 #ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_
25 #define SKELETON_BLOCKER_INTERNAL_TRIE_H_
26 
27 #include <memory>
28 #include <vector>
29 #include <deque>
30 #include <set>
31 
32 namespace Gudhi {
33 
34 namespace skeleton_blocker {
35 
36 template<typename SimplexHandle>
37 struct Trie {
38  typedef SimplexHandle Simplex;
39  typedef typename SimplexHandle::Vertex_handle Vertex_handle;
40 
41  Vertex_handle v;
42  std::vector<std::shared_ptr<Trie> > childs;
43  // std::vector<std::unique_ptr<Trie> > childs; -> use of deleted function
44  private:
45  const Trie* parent_;
46 
47  public:
48  Trie() : parent_(0) { }
49 
50  Trie(Vertex_handle v_) : v(v_), parent_(0) { }
51 
52  Trie(Vertex_handle v_, Trie* parent) : v(v_), parent_(parent) { }
53 
54  bool operator==(const Trie& other) const {
55  return (v == other.v);
56  }
57 
58  void add_child(Trie* child) {
59  if (child) {
60  std::shared_ptr<Trie> ptr_to_add(child);
61  childs.push_back(ptr_to_add);
62  child->parent_ = this;
63  }
64  }
65 
66  typedef typename Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator;
67 
68  Trie* make_trie(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
69  if (s_it == s_end) {
70  return 0;
71  } else {
72  Trie* res = new Trie(*s_it);
73  Trie* child = make_trie(++s_it, s_end);
74  res->add_child(child);
75  return res;
76  }
77  }
78 
79  private:
80  // go down recursively in the tree while advancing the simplex iterator.
81  // when it reaches a leaf, it inserts the remaining that is not present
82  void add_simplex_helper(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
83  assert(*s_it == v);
84  ++s_it;
85  if (s_it == s_end) return;
86  if (!is_leaf()) {
87  for (auto child : childs) {
88  if (child->v == *s_it)
89  return child->add_simplex_helper(s_it, s_end);
90  }
91  // s_it is not found and needs to be inserted
92  }
93  // not leaf -> remaining of s needs to be inserted
94  Trie * son_with_what_remains_of_s(make_trie(s_it, s_end));
95  add_child(son_with_what_remains_of_s);
96  return;
97  }
98 
99  void maximal_faces_helper(std::vector<Simplex>& res) const {
100  if (is_leaf()) res.push_back(simplex());
101  else
102  for (auto child : childs)
103  child->maximal_faces_helper(res);
104  }
105 
106  public:
110  void add_simplex(const Simplex& s) {
111  if (s.empty()) return;
112  assert(v == s.first_vertex());
113  add_simplex_helper(s.begin(), s.end());
114  }
115 
116  std::vector<Simplex> maximal_faces() const {
117  std::vector<Simplex> res;
118  maximal_faces_helper(res);
119  return res;
120  }
121 
125  void add_vertices_up_to_the_root(Simplex& res) const {
126  res.add_vertex(v);
127  if (parent_)
128  parent_->add_vertices_up_to_the_root(res);
129  }
130 
131  Simplex simplex() const {
132  Simplex res;
133  add_vertices_up_to_the_root(res);
134  return res;
135  }
136 
137  bool is_leaf() const {
138  return childs.empty();
139  }
140 
141  bool is_root() const {
142  return parent_ == 0;
143  }
144 
145  const Trie* parent() {
146  return parent_;
147  }
148 
149  void remove_leaf() {
150  assert(is_leaf());
151  if (!is_root())
152  parent_->childs.erase(this);
153  }
154 
158  bool contains(const Simplex& s) const {
159  Trie const* current = this;
160  if (s.empty()) return true;
161  if (current->v != s.first_vertex()) return false;
162  auto s_pos = s.begin();
163  ++s_pos;
164  while (s_pos != s.end() && current != 0) {
165  bool found = false;
166  for (const auto child : current->childs) {
167  if (child->v == *s_pos) {
168  ++s_pos;
169  current = child.get();
170  found = true;
171  break;
172  }
173  }
174  if (!found) return false;
175  }
176  return current != 0;
177  }
178 
179  Trie* go_bottom_left() {
180  if (is_leaf())
181  return this;
182  else
183  return (*childs.begin())->go_bottom_left();
184  }
185 
186  friend std::ostream& operator<<(std::ostream& stream, const Trie& trie) {
187  stream << "T( " << trie.v << " ";
188  for (auto t : trie.childs)
189  stream << *t;
190  stream << ")";
191  return stream;
192  }
193 };
194 
195 template<typename SimplexHandle>
196 struct Tries {
197  typedef typename SimplexHandle::Vertex_handle Vertex_handle;
198  typedef SimplexHandle Simplex;
199 
200  typedef Trie<Simplex> STrie;
201 
202  template<typename SimpleHandleOutputIterator>
203  Tries(unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) :
204  cofaces_(num_vertices, 0) {
205  for (auto i = 0u; i < num_vertices; ++i)
206  cofaces_[i] = new STrie(Vertex_handle(i));
207  for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) {
208  if (s_it->dimension() >= 1)
209  cofaces_[s_it->first_vertex()]->add_simplex(*s_it);
210  }
211  }
212 
213  ~Tries() {
214  for (STrie* t : cofaces_)
215  delete t;
216  }
217 
218  // return a simplex that consists in all u such uv is an edge and u>v
219 
220  Simplex positive_neighbors(Vertex_handle v) const {
221  Simplex res;
222  for (auto child : cofaces_[v]->childs)
223  res.add_vertex(child->v);
224  return res;
225  }
226 
227  bool contains(const Simplex& s) const {
228  auto first_v = s.first_vertex();
229  return cofaces_[first_v]->contains(s);
230  }
231 
232  friend std::ostream& operator<<(std::ostream& stream, const Tries& tries) {
233  for (auto trie : tries.cofaces_)
234  stream << *trie << std::endl;
235  return stream;
236  }
237 
238  // init_next_dimension must be called first
239 
240  std::vector<Simplex> next_dimension_simplices() const {
241  std::vector<Simplex> res;
242  while (!(to_see_.empty()) && (to_see_.front()->simplex().dimension() == current_dimension_)) {
243  res.emplace_back(to_see_.front()->simplex());
244  for (auto child : to_see_.front()->childs)
245  to_see_.push_back(child.get());
246  to_see_.pop_front();
247  }
248  ++current_dimension_;
249  return res;
250  }
251 
252  void init_next_dimension() const {
253  for (auto trie : cofaces_)
254  to_see_.push_back(trie);
255  }
256 
257  private:
258  mutable std::deque<STrie*> to_see_;
259  mutable int current_dimension_ = 0;
260  std::vector<STrie*> cofaces_;
261 };
262 
263 } // namespace skeleton_blocker
264 
265 namespace skbl = skeleton_blocker;
266 
267 } // namespace Gudhi
268 
269 #endif // SKELETON_BLOCKER_INTERNAL_TRIE_H_
Definition: SimplicialComplexForAlpha.h:26
GUDHI  Version 2.2.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Fri Jun 22 2018 08:12:19 for GUDHI by Doxygen 1.8.13