Simplex_tree_star_simplex_iterators.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): Clément Maria
4 *
5 * Copyright (C) 2020 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef SIMPLEX_TREE_SIMPLEX_TREE_STAR_SIMPLEX_ITERATORS_H_
12#define SIMPLEX_TREE_SIMPLEX_TREE_STAR_SIMPLEX_ITERATORS_H_
13
14#include <gudhi/Debug_utils.h>
15#include <boost/iterator/iterator_facade.hpp>
16#include <boost/version.hpp>
17#include <boost/iterator/filter_iterator.hpp>
18
19#include <vector>
20#include <stdexcept>
21#include <utility> // for std::move
22#include <functional> // for std::greater
23#include <algorithm> // for std::includes
24
25namespace Gudhi {
26
45template <class SimplexTree>
46class Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator
47 : public boost::iterator_facade<Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator<SimplexTree>,
48 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
49 public:
50 using Simplex_handle = typename SimplexTree::Simplex_handle;
51 using Siblings = typename SimplexTree::Siblings;
53 using Node = typename SimplexTree::Node;
54 using Static_vertex_vector = typename SimplexTree::Static_vertex_vector;
55
68 class is_coface {
69 public:
70 is_coface() : cpx_(nullptr) {}
71 is_coface(SimplexTree const* cpx, Static_vertex_vector&& simp) : cpx_(cpx), simp_(simp) {}
72
73 // Return true iff traversing the Node upwards to the root reads a
74 // coface of simp_
75 bool operator()(const typename SimplexTree::Hooks_simplex_base& curr_hooks) {
76 const Node& curr_node = static_cast<const Node&>(curr_hooks);
77 Simplex_handle sh = cpx_->simplex_handle_from_node(curr_node);
78 // first Node must always have label simp_.begin(); we assume it is true
79 auto&& rng = cpx_->simplex_vertex_range(sh);
80 auto rng_it = rng.begin();
81 GUDHI_CHECK(*rng_it == simp_.front(), std::invalid_argument("first Node must always have label simp_.begin()"));
82 auto simp_it = simp_.begin();
83 // is simp_ a face of the simplex defined by sh ?
84 return std::includes(++rng_it, rng.end(), ++simp_it, simp_.end(), std::greater<Vertex_handle>());
85 }
86
87 private:
88 SimplexTree const* cpx_;
89 Static_vertex_vector simp_; // vertices of simplex, in reverse order
90 };
91
92 typedef boost::filter_iterator<is_coface, typename SimplexTree::List_max_vertex::const_iterator>
93 Filtered_cofaces_simplex_iterator;
94 // any end() iterator
95 Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator() : predicate_(), st_(nullptr) {}
96
97 Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator(SimplexTree const* cpx,
98 Static_vertex_vector&& simp)
99 : predicate_(cpx, std::move(simp)), st_(cpx) {
100 GUDHI_CHECK(!simp.empty(), std::invalid_argument("cannot call for cofaces of an empty simplex"));
101 const auto list_ptr = st_->nodes_by_label(simp.front());
102 GUDHI_CHECK(list_ptr != nullptr, std::runtime_error("invalid call to cofaces forest"));
103
104 it_ = boost::make_filter_iterator(predicate_, list_ptr->begin(), list_ptr->end());
105 end_ = boost::make_filter_iterator(predicate_, list_ptr->end(), list_ptr->end());
106 const Node& curr_node = static_cast<const Node&>(*it_);
107 sh_ = st_->simplex_handle_from_node(curr_node);
108 }
109
110 private:
111 friend class boost::iterator_core_access;
112
113 // valid when iterating along the SAME list of max vertex.
114 bool equal(Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator const& other) const {
115 if (other.st_ == nullptr) {
116 return (st_ == nullptr);
117 }
118 if (st_ == nullptr) {
119 return false;
120 }
121 return (it_ == other.it_);
122 }
123
124 Simplex_handle const& dereference() const { return sh_; }
125
126 void increment() {
127 if (++it_ == end_) {
128 st_ = nullptr;
129 } //== end
130 else { // update sh_
131 const Node& curr_node = static_cast<const Node&>(*it_);
132 sh_ = st_->simplex_handle_from_node(curr_node);
133 }
134 }
135
136 // given a Node of label max_v, returns true if the associated simplex is a coface of the simplex {..., max_v}. The
137 // predicate stores the vertices of the simplex whose star we compute.
138 is_coface predicate_;
139 SimplexTree const* st_;
140 // filtered iterators over Nodes, filtered with predicate_
141 Filtered_cofaces_simplex_iterator it_;
142 Filtered_cofaces_simplex_iterator end_;
143 // current Simplex_handle corresponding to Node pointed at by it_
144 Simplex_handle sh_;
145};
146
159template <class SimplexTree>
161 : public boost::iterator_facade<Simplex_tree_optimized_star_simplex_iterator<SimplexTree>,
162 typename SimplexTree::Simplex_handle const, boost::forward_traversal_tag> {
163 public:
164 using Simplex_handle = typename SimplexTree::Simplex_handle;
165 using Siblings = typename SimplexTree::Siblings;
166 using Vertex_handle = typename SimplexTree::Vertex_handle;
167 using Node = typename SimplexTree::Node;
168 using Static_vertex_vector = typename SimplexTree::Static_vertex_vector;
169
170 // any end() iterator
172
173 Simplex_tree_optimized_star_simplex_iterator(SimplexTree const* cpx, Static_vertex_vector&& simp)
174 : st_(cpx), it_(cpx, std::move(simp)), end_(), sh_(*it_), sib_(st_->self_siblings(sh_)), children_stack_() {
175 if (it_ == end_) {
176 st_ = nullptr;
177 return;
178 } // no coface subtree => end()
179 is_root_ = true;
180 sh_ = *it_; // sh_ is the root
181 sib_ = st_->self_siblings(sh_); // Siblings containing sh_
182 if (st_->has_children(sh_)) {
183 children_stack_.push_back(st_->children(sh_));
184 }
185 return; // first root of coface subtree
186 }
187
188 private:
189 friend class boost::iterator_core_access;
190
191 // valid when iterating along the SAME list of max vertex.
192 bool equal(Simplex_tree_optimized_star_simplex_iterator const& other) const {
193 if (other.st_ == nullptr) {
194 return (st_ == nullptr);
195 }
196 if (st_ == nullptr) {
197 return false;
198 }
199 return (&(sh_->second) == &(other.sh_->second));
200 }
201
202 Simplex_handle const& dereference() const { return sh_; }
203
204 /* Go to the next valid Simplex_handle for a coface, using a breadth first
205 * search approach.
206 *
207 * Invariant:
208 *
209 * sh_ is a coface,
210 * sib_ the Siblings containing sh_,
211 * it_ the root of a coface subtree, such that dim_root_ <= exact_dim_cofaces_.
212 * bfs_queue contains Siblings inside the coface subtree.
213 *
214 * Additionally,
215 *
216 * - computing all cofaces: sh_ points to a coface of any dimension. bfs_queue
217 * contains a collection of Siblings* that must be considered (as well as there
218 * children). These are all sets of children of simplices in
219 * [ sib_->members().begin(), sh_ ]
220 */
221 void increment_all_cofaces() {
222 ++sh_; // next sibling
223 // if no more sibling or root of coface tree, go down or to next subtree
224 if (is_root_ || sh_ == sib_->members().end()) {
225 is_root_ = false;
226 if (!children_stack_.empty()) {
227 sib_ = children_stack_.back();
228 children_stack_.pop_back();
229 sh_ = sib_->members().begin(); // don't track dimensions
230 if (st_->has_children(sh_)) {
231 children_stack_.push_back(st_->children(sh_));
232 }
233 } else { // bfs_queue == empty, go to root of next coface subtree
234 if (++it_ == end_) {
235 st_ = nullptr;
236 return;
237 } // no more subtree => end()
238 is_root_ = true;
239 sh_ = *it_; // sh_ is the root
240 sib_ = st_->self_siblings(sh_); // Siblings containing sh_
241 if (st_->has_children(sh_)) {
242 children_stack_.push_back(st_->children(sh_));
243 }
244 return; // next root of coface
245 }
246 } else { // sh_ is valid, simply add its children to the queue
247 if (st_->has_children(sh_)) {
248 children_stack_.push_back(st_->children(sh_));
249 }
250 }
251 }
252
253 // For cofaces, enumerating all the star and testing which simplices have the right dimension is suboptimal.
254 // This could be optimized later.
255 void increment() { increment_all_cofaces(); }
256
257 // Let s be the simplex in a complex C whose star is
258 // iterated through. Let max_v denote the maximal label of vertices in s.
259 SimplexTree const* st_; // Simplex tree for complex C
260 // The cofaces of s form a subforest of the simplex tree. The roots of trees in this
261 // forest have label max_v.
262 //[it_,end_) == range of Simplex_handles of the roots of the cofaces trees (any dim)
263 Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator<SimplexTree> it_;
264 Simplex_tree_optimized_cofaces_rooted_subtrees_simplex_iterator<SimplexTree> end_;
265 // curr Simplex_handle, returned by operator*, pointing to a coface of s
266 Simplex_handle sh_;
267 // set of siblings containing sh_ in the Simplex_tree
268 Siblings const* sib_; //
269 // Save children in a list to avoid calling sib_->members().find(.)
270 std::vector<Siblings const*> children_stack_;
271 // true iff sh_ points to the root of a coface subtree
272 bool is_root_;
273};
274
275} // namespace Gudhi
276
277#endif // SIMPLEX_TREE_SIMPLEX_TREE_STAR_SIMPLEX_ITERATORS_H_
Predicate to check whether an input SimplexTree::Node represents a coface of a simplex simp_,...
Definition: Simplex_tree_star_simplex_iterators.h:68
Iterator over the simplices of the star of a simplex.
Definition: Simplex_tree_star_simplex_iterators.h:162
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:98
Siblings const * self_siblings(SimplexHandle sh) const
Definition: Simplex_tree.h:1154
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const
Returns a range over the vertices of a simplex.
Definition: Simplex_tree.h:369
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by the given simplex handle has children.
Definition: Simplex_tree.h:874
Dictionary::const_iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:192
Simplex_tree_siblings< Simplex_tree, Dictionary > Siblings
Set of nodes sharing a same parent in the simplex tree.
Definition: Simplex_tree.h:136
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:119
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14
STL namespace.
Node of a simplex tree with filtration value and simplex key.
Definition: Simplex_tree_node_explicit_storage.h:40
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15