1 /* Copyright (c) 1997-2021
2 Ewgenij Gawrilow, Michael Joswig, and the polymake team
3 Technische Universität Berlin, Germany
4 https://polymake.org
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version: http://www.gnu.org/licenses/gpl.txt.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15 --------------------------------------------------------------------------------
16 */
17
18 #pragma once
19
20 #include "polymake/Array.h"
21 #include "polymake/PowerSet.h"
22 #include "polymake/graph/ShrinkingLattice.h"
23 #include "polymake/graph/LatticeTools.h"
24 #include "polymake/list"
25 #include <string>
26
27 /** Tools to treat simplicial complexes.
28 *
29 * A simplicial complex is represented as a list of its FACETS, encoded as their vertex sets.
30 * Therefore any container of GenericSet of Int (template <typename Complex>) may be used to
31 * represent a complex. In the following std::list< polymake::Set<Int> >, polymake::PowerSet<Int>
32 * and polymake::Array< polymake::Set<Int> > are used.
33 */
34
35 namespace polymake { namespace topaz {
36
37 using graph::HasseDiagram_facet_iterator;
38 using graph::Lattice;
39 using graph::ShrinkingLattice;
40 using graph::lattice::BasicDecoration;
41
42 // Computes the k_skeleton of a simplicial complex.
43 template <typename Complex>
44 PowerSet<Int> k_skeleton(const Complex& C, const Int k);
45
46 template <typename Complex, typename TSet>
47 struct link_helper {
48 typedef pm::same_value_container<const TSet&> same_set;
49 typedef pm::SelectedContainerPairSubset< const Complex&, same_set, operations::includes >
50 selected_facets;
51 typedef pm::SelectedContainerPairSubset< const Complex&, same_set,
52 operations::composed21<operations::includes, std::logical_not<bool> > >
53 deletion_type;
54 typedef pm::TransformedContainerPair< selected_facets, same_set, operations::sub >
55 result_type;
56 };
57
58 // Computes the star of a given face F.
59 template <typename Complex, typename TSet>
star(const Complex & C,const GenericSet<TSet,Int> & F)60 auto star(const Complex& C, const GenericSet<TSet, Int>& F)
61 {
62 using helper = link_helper<Complex, TSet>;
63 return typename helper::selected_facets(C, typename helper::same_set(F.top()));
64 }
65
66 // Computes the deletion of a given face F.
67 template <typename Complex, typename TSet>
deletion(const Complex & C,const GenericSet<TSet,Int> & F)68 auto deletion(const Complex& C, const GenericSet<TSet, Int>& F)
69 {
70 using helper = link_helper<Complex, TSet>;
71 return typename helper::deletion_type(C, typename helper::same_set(F.top()));
72 }
73
74 // Computes the link of a given face F.
75 template <typename Complex, typename TSet>
link(const Complex & C,const GenericSet<TSet,Int> & F)76 auto link(const Complex& C, const GenericSet<TSet, Int>& F)
77 {
78 using helper = link_helper<Complex, TSet>;
79 return typename helper::result_type(star(C, F), typename helper::same_set(F.top()));
80 }
81
82 struct star_maker {
83 typedef HasseDiagram_facet_iterator<Lattice<BasicDecoration>> argument_type;
84 typedef const Set<Int>& result_type;
85
operatorstar_maker86 result_type operator() (const argument_type& it) const { return it.face(); }
87 };
88
89 struct link_maker {
90 Int start_face;
start_facelink_maker91 link_maker(Int start_arg = -1) : start_face(start_arg) {}
92
93 typedef HasseDiagram_facet_iterator<Lattice<BasicDecoration>> argument_type;
94 typedef pm::LazySet2<const Set<Int>&, const Set<Int>&, pm::set_difference_zipper> result_type;
95
operatorlink_maker96 result_type operator() (const argument_type& it) const { return it.face()-it.face(start_face); }
97 };
98
99 // Enumerates the star of a face (specified by it's index in the HasseDiagram.
100 typedef pm::unary_transform_iterator<HasseDiagram_facet_iterator<Lattice<BasicDecoration> >, star_maker> star_enumerator;
101
102 inline
star_in_HD(const Lattice<BasicDecoration> & HD,const Int f)103 star_enumerator star_in_HD(const Lattice<BasicDecoration>& HD, const Int f)
104 {
105 return HasseDiagram_facet_iterator<Lattice<BasicDecoration> >(HD,f);
106 }
107
108 // Enumerates the link of a face (specified by it's index in the HasseDiagram.
109 typedef pm::unary_transform_iterator<HasseDiagram_facet_iterator<Lattice<BasicDecoration>>, link_maker> link_enumerator;
110
111 inline
link_in_HD(const Lattice<BasicDecoration> & HD,const Int f)112 link_enumerator link_in_HD(const Lattice<BasicDecoration>& HD, const Int f)
113 {
114 return link_enumerator(HasseDiagram_facet_iterator<Lattice<BasicDecoration>>(HD,f), f);
115 }
116
117 // Enumerates the vertex star of a complex represented as a Hasse Diagram and a given vertex v.
118 inline
vertex_star_in_HD(const Lattice<BasicDecoration> & HD,const Int v)119 star_enumerator vertex_star_in_HD(const Lattice<BasicDecoration>& HD, const Int v)
120 {
121 return star_in_HD(HD, find_vertex_node(HD,v));
122 }
123
124 // Computes the vertex link of a complex represented as a Hasse Diagram and a given vertex v.
125 inline
vertex_link_in_HD(const Lattice<BasicDecoration> & HD,const Int v)126 link_enumerator vertex_link_in_HD(const Lattice<BasicDecoration>& HD, const Int v)
127 {
128 return link_in_HD(HD, find_vertex_node(HD,v));
129 }
130
131 // Computes the vertex set of the link of the vertex v.
132 Set<Int> vertices_of_vertex_link(const Lattice<BasicDecoration>& HD, const Int v);
133
134 class out_degree_checker {
135 public:
136 typedef void argument_type;
137 typedef bool result_type;
138
degree(degree_arg)139 out_degree_checker(Int degree_arg = 0) : degree(degree_arg) { }
140
141 template <typename Iterator>
operator()142 result_type operator() (const Iterator& node_it) const
143 {
144 return node_it.out_degree()==degree;
145 }
146 protected:
147 Int degree;
148 };
149
150 // Computes the boundary complex (= ridges contained in one facet only)
151 // of a PSEUDO_MANIFOLD. The complex is encoded as a Hasse Diagrams.
152
153 template<typename SeqType>
154 inline
boundary_of_pseudo_manifold(const Lattice<BasicDecoration,SeqType> & PM)155 auto boundary_of_pseudo_manifold(const Lattice<BasicDecoration, SeqType>& PM)
156 {
157 return attach_selector(select(PM.decoration(), PM.nodes_of_rank(PM.rank()-2)), out_degree_checker(1));
158 }
159
160 // Removes the vertex star of v from a complex C, represented as a Hasse Diagram.
161 void remove_vertex_star(ShrinkingLattice<BasicDecoration>& HD, const Int v);
162
163 // Removes a facet F from a simplicial complex, represented as a Hasse Diagram.
164 template <typename TSet>
165 void remove_facet(ShrinkingLattice<BasicDecoration>& HD, const GenericSet<TSet, Int>& F);
166
167 // Checks whether a 1-complex (graph) is a 1-ball or 1-sphere.
168 // return values: 1=true, 0=false, -1=undef (does not occur here)
169 template <typename Complex, typename VertexSet>
170 Int is_ball_or_sphere(const Complex& C, const GenericSet<VertexSet>& V, int_constant<1>);
171
172 // Checks whether a 2-complex is a 2-ball or 2-sphere.
173 // return values: 1=true, 0=false, -1=undef (does not occur here)
174 template <typename Complex, typename VertexSet>
175 Int is_ball_or_sphere(const Complex& C, const GenericSet<VertexSet>& V, int_constant<2>);
176
177 // Checks whether a 1-complex (graph) is a manifold.
178 // return values: 1=true, 0=false, -1=undef (does not occur here)
179 template <typename Complex, typename VertexSet>
180 Int is_manifold(const Complex& C, const GenericSet<VertexSet>& V, int_constant<1>, Int* bad_link_p = nullptr);
181
182 // Heuristic check whether a complex of arbitrary dimension d is a manifold.
183 // If not, *bad_link_p = vertex whose link is neither a ball nor a sphere
184 // return values: 1=true, 0=false, -1=undef
185 template <typename Complex, typename VertexSet, int d>
186 Int is_manifold(const Complex& C, const GenericSet<VertexSet>& V, int_constant<d>, Int* bad_link_p = nullptr);
187
188 // heuristic sphere checking
189 // return values: 1=true, 0=false, -1=undef
190 template <typename Complex, int d>
191 Int is_ball_or_sphere(const Complex& C, int_constant<d>);
192
193 // The same for a trusted complex (pure, without gaps in vertex numbering)
194 // return values: 1=true, 0=false, -1=undef
195 template <typename Complex, int d>
is_ball_or_sphere(const Complex & C,Int n_vertices,int_constant<d>)196 Int is_ball_or_sphere(const Complex& C, Int n_vertices, int_constant<d>)
197 {
198 return is_ball_or_sphere(C, sequence(0,n_vertices), int_constant<d>());
199 }
200
201 template <typename Complex, int d>
202 // return values: 1=true, 0=false, -1=undef
203 Int is_manifold(const Complex& C, int_constant<d>, Int* bad_link_p = nullptr);
204
205 // The same for a trusted complex (pure, without gaps in vertex numbering)
206 // return values: 1=true, 0=false, -1=undef
207 template <typename Complex, int d>
208 Int is_manifold(const Complex& C, Int n_vertices, int_constant<d>, Int* bad_link_p = nullptr)
209 {
210 return is_manifold(C, sequence(0,n_vertices), int_constant<d>(), bad_link_p);
211 }
212
213 /// Adjusts the vertex numbers to 0..n-1.
214 /// @retval true if the numbering has been adjusted
215 template <typename Complex, typename Set>
216 bool adj_numbering(Complex& C, const Set& V);
217
218 // Checks whether a complex, represented as a Hasse Diagram, is a closed pseudo manifold.
219 bool is_closed_pseudo_manifold(const Lattice<BasicDecoration>& HD, bool known_pure);
220
221 // Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold
222 // and computes its boundary.
223 template <typename OutputIterator>
224 bool is_pseudo_manifold(const Lattice<BasicDecoration>& HD, bool known_pure, OutputIterator boundary_consumer, Int* bad_face_p = nullptr);
225
226 // Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold.
227 inline
228 bool is_pseudo_manifold(const Lattice<BasicDecoration>& HD, bool known_pure, Int* bad_face_p = nullptr)
229 {
230 return is_pseudo_manifold(HD, known_pure, black_hole<Set<Int>>(), bad_face_p);
231 }
232
233 bool is_pure(const Lattice<BasicDecoration>& HD);
234
235 // checks whether a flag of faces, represented by a Set<Set<Int>>,
236 // lies completely in the boundary of a complex, which is represented by an IncidenceMatrix
237 inline
on_boundary(const Set<Set<Int>> & label,const IncidenceMatrix<> & VIF)238 bool on_boundary(const Set<Set<Int>>& label, const IncidenceMatrix<>& VIF)
239 {
240 Set<Int> face;
241 for (auto lit = entire(label); !lit.at_end(); ++lit)
242 face += *lit;
243
244 for (auto rit = entire(rows(VIF)); !rit.at_end(); ++rit)
245 if (!(face - *rit).size())
246 return true; // it's contained in the boundary
247
248 return false;
249 }
250
251 // The torus.
252 Array<Set<Int>> torus_facets();
253
254 // The real projective plane.
255 Array<Set<Int>> real_projective_plane_facets();
256
257 // The complex projective plane.
258 Array<Set<Int>> complex_projective_plane_facets();
259
260 } }
261
262 #include "polymake/topaz/complex_tools.tcc"
263 #include "polymake/topaz/subcomplex_tools.tcc"
264 #include "polymake/topaz/1D_tools.tcc"
265 #include "polymake/topaz/2D_tools.tcc"
266
267
268 // Local Variables:
269 // mode:C++
270 // c-basic-offset:3
271 // indent-tabs-mode:nil
272 // End:
273