1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Siargey Kachanovich
*
* Copyright (C) 2019 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef PERMUTAHEDRAL_REPRESENTATION_H_
#define PERMUTAHEDRAL_REPRESENTATION_H_
#include <gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h>
#include <utility> // for std::make_pair
namespace Gudhi {
namespace coxeter_triangulation {
/**
* \class Permutahedral_representation
* \brief A class that stores the permutahedral representation of a simplex
* in a Coxeter triangulation or a Freudenthal-Kuhn triangulation.
*
* \ingroup coxeter_triangulation
*
* \details The data structure is a record consisting of a range that
* represents the vertex and a range that represents the ordered set
* partition, both of which identify the simplex in the triangulation.
*
* \tparam Vertex_ needs to be a random-access range.
* \tparam Ordered_set_partition_ needs to be a a random-access range that consists of
* random-access ranges.
*/
template <class Vertex_, class Ordered_set_partition_>
class Permutahedral_representation {
typedef Permutahedral_representation<Vertex_, Ordered_set_partition_> Self;
public:
/** \brief Type of the vertex. */
typedef Vertex_ Vertex;
/** \brief Type of the ordered partition. */
typedef Ordered_set_partition_ OrderedSetPartition;
/** \brief Permutahedral_representation constructor from a vertex and an ordered set partition.
*
* @param[in] vertex Vertex.
* @param[in] partition Ordered set partition.
*
* \details If the size of vertex is d, the ranges in partition must consist
* of the integers 0,...,d without repetition or collision between the ranges.
*/
Permutahedral_representation(const Vertex& vertex, const OrderedSetPartition& partition)
: vertex_(vertex), partition_(partition) {}
/** \brief Constructor for an empty permutahedral representation that does not correspond
* to any simplex.
*/
Permutahedral_representation() {}
/** \brief Dimension of the simplex. */
std::size_t dimension() const { return partition_.size() - 1; }
/** \brief Lexicographically-minimal vertex. */
Vertex& vertex() { return vertex_; }
/** \brief Lexicographically-minimal vertex. */
const Vertex& vertex() const { return vertex_; }
/** \brief Ordered set partition. */
OrderedSetPartition& partition() { return partition_; }
/** \brief Identifying vertex. */
const OrderedSetPartition& partition() const { return partition_; }
/** \brief Equality operator.
* Returns true if an only if both vertex and the ordered set partition coincide.
*/
bool operator==(const Permutahedral_representation& other) const {
if (dimension() != other.dimension()) return false;
if (vertex_ != other.vertex_) return false;
for (std::size_t k = 0; k < partition_.size(); ++k)
if (partition_[k] != other.partition_[k]) return false;
return true;
}
/** \brief Inequality operator.
* Returns true if an only if either vertex or the ordered set partition are different.
*/
bool operator!=(const Permutahedral_representation& other) const { return !(*this == other); }
typedef Gudhi::coxeter_triangulation::Vertex_iterator<Self> Vertex_iterator;
typedef boost::iterator_range<Vertex_iterator> Vertex_range;
/** \brief Returns a range of vertices of the simplex.
* The type of vertices is Vertex.
*/
Vertex_range vertex_range() const { return Vertex_range(Vertex_iterator(*this), Vertex_iterator()); }
typedef Gudhi::coxeter_triangulation::Face_iterator<Self> Face_iterator;
typedef boost::iterator_range<Face_iterator> Face_range;
/** \brief Returns a range of permutahedral representations of faces of the simplex.
* @param[in] value_dim The dimension of the faces. Must be between 0 and the dimension of the simplex.
*/
Face_range face_range(std::size_t value_dim) const {
return Face_range(Face_iterator(*this, value_dim), Face_iterator());
}
/** \brief Returns a range of permutahedral representations of facets of the simplex.
* The dimension of the simplex must be strictly positive.
*/
Face_range facet_range() const { return Face_range(Face_iterator(*this, dimension() - 1), Face_iterator()); }
typedef Gudhi::coxeter_triangulation::Coface_iterator<Self> Coface_iterator;
typedef boost::iterator_range<Coface_iterator> Coface_range;
/** \brief Returns a range of permutahedral representations of cofaces of the simplex.
* @param[in] value_dim The dimension of the cofaces. Must be between the dimension of the simplex and the ambient
* dimension (the size of the vertex).
*/
Coface_range coface_range(std::size_t value_dim) const {
return Coface_range(Coface_iterator(*this, value_dim), Coface_iterator());
}
/** \brief Returns a range of permutahedral representations of cofacets of the simplex.
* The dimension of the simplex must be strictly different from the ambient dimension (the size of the vertex).
*/
Coface_range cofacet_range() const {
return Coface_range(Coface_iterator(*this, dimension() + 1), Coface_iterator());
}
/** \brief Returns true, if the simplex is a face of other simplex.
*
* @param[in] other A simplex that is potential a coface of the current simplex.
*/
bool is_face_of(const Permutahedral_representation& other) const {
using Part = typename OrderedSetPartition::value_type;
if (other.dimension() < dimension()) return false;
if (other.vertex_.size() != vertex_.size())
std::cerr << "Error: Permutahedral_representation::is_face_of: incompatible ambient dimensions.\n";
Vertex v_self = vertex_, v_other = other.vertex_;
auto self_partition_it = partition_.begin();
auto other_partition_it = other.partition_.begin();
while (self_partition_it != partition_.end()) {
while (other_partition_it != other.partition_.end() && v_self != v_other) {
const Part& other_part = *other_partition_it++;
if (other_partition_it == other.partition_.end()) return false;
for (const auto& k : other_part) v_other[k]++;
}
if (other_partition_it == other.partition_.end()) return false;
const Part& self_part = *self_partition_it++;
if (self_partition_it == partition_.end()) return true;
for (const auto& k : self_part) v_self[k]++;
}
return true;
}
private:
Vertex vertex_;
OrderedSetPartition partition_;
};
/** \brief Print a permutahedral representation to a stream.
* \ingroup coxeter_triangulation
*
* @param[in] os The output stream.
* @param[in] simplex A simplex represented by its permutahedral representation.
*/
template <class Vertex, class OrderedSetPartition>
std::ostream& operator<<(std::ostream& os, const Permutahedral_representation<Vertex, OrderedSetPartition>& simplex) {
// vertex part
os << "(";
if (simplex.vertex().empty()) {
os << ")";
return os;
}
auto v_it = simplex.vertex().begin();
os << *v_it++;
for (; v_it != simplex.vertex().end(); ++v_it) os << ", " << *v_it;
os << ")";
// ordered partition part
using Part = typename OrderedSetPartition::value_type;
auto print_part = [&os](const Part& p) {
os << "{";
if (p.empty()) {
os << "}";
}
auto p_it = p.begin();
os << *p_it++;
for (; p_it != p.end(); ++p_it) os << ", " << *p_it;
os << "}";
};
os << " [";
if (simplex.partition().empty()) {
os << "]";
return os;
}
auto o_it = simplex.partition().begin();
print_part(*o_it++);
for (; o_it != simplex.partition().end(); ++o_it) {
os << ", ";
print_part(*o_it);
}
os << "]";
return os;
}
} // namespace coxeter_triangulation
} // namespace Gudhi
#endif // PERMUTAHEDRAL_REPRESENTATION_H_
|
