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 #include "polymake/hash_map"
19 #include "polymake/FaceMap.h"
20 #include "polymake/Bitset.h"
21 #include <sstream>
22
23 namespace polymake { namespace topaz {
24
25 template <typename Complex, typename Set>
adj_numbering(Complex & C,const Set & V)26 bool adj_numbering(Complex& C, const Set& V)
27 {
28 if (V.empty())
29 return false;
30
31 const bool renumber= V.front()!=0 || V.back()+1!=V.size();
32
33 if (renumber) {
34 hash_map<Int, Int> vertex_map(V.size());
35 Int count = 0;
36 for (auto s_it=entire(V); !s_it.at_end(); ++s_it, ++count)
37 vertex_map[*s_it]=count;
38
39 for (auto c_it=entire(C); !c_it.at_end(); ++c_it) {
40 typename Complex::value_type f;
41 for (auto s_it=entire(*c_it); !s_it.at_end(); ++s_it)
42 f += vertex_map[*s_it];
43 *c_it = f;
44 }
45 }
46
47 return renumber;
48 }
49
50 template <typename OutputIterator>
is_pseudo_manifold(const Lattice<BasicDecoration> & HD,bool known_pure,OutputIterator boundary_consumer,Int * bad_face_p)51 bool is_pseudo_manifold(const Lattice<BasicDecoration>& HD, bool known_pure, OutputIterator boundary_consumer, Int* bad_face_p)
52 {
53 if (HD.in_degree(HD.top_node())==0)
54 return true;
55
56 if (!known_pure && !is_pure(HD)) {
57 if (bad_face_p) *bad_face_p=-1;
58 return false;
59 }
60
61 for (const auto n : HD.nodes_of_rank(HD.rank()-2)) {
62 const Int d = HD.out_degree(n);
63 if (d > 2) {
64 if (bad_face_p) *bad_face_p=n;
65 return false;
66 }
67 if (!is_derived_from_instance_of<OutputIterator, pm::black_hole>::value && d == 1)
68 *boundary_consumer++ = HD.face(n);
69 }
70
71 return true;
72 }
73
74 // return values: 1=true, 0=false, -1=undef
75 template <typename Complex, int d>
is_ball_or_sphere(const Complex & C,int_constant<d>)76 Int is_ball_or_sphere(const Complex& C, int_constant<d>)
77 {
78 if (POLYMAKE_DEBUG) {
79 if (C.empty())
80 throw std::runtime_error("is_ball_or_sphere: empty complex");
81 }
82 // compute the vertex set and test whether C is a pure d-complex
83 Set<Int> V;
84 for (auto c_it=entire(C); !c_it.at_end(); ++c_it) {
85 V += *c_it;
86 if (POLYMAKE_DEBUG) {
87 if (c_it->size() > d+1) {
88 std::ostringstream err;
89 pm::wrap(err) << "is_ball_or_sphere: Dimension of " << *c_it << " is greater than " << d;
90 throw std::runtime_error(err.str());
91 }
92 }
93 if (c_it->size()!=d+1) // complex is not pure
94 return 0;
95 }
96 return is_ball_or_sphere(C, V, int_constant<d>());
97 }
98
99 // return values: 1=true, 0=false, -1=undef
100 template <typename Complex, int d>
is_manifold(const Complex & C,int_constant<d>,Int * bad_link_p)101 Int is_manifold(const Complex& C, int_constant<d>, Int* bad_link_p)
102 {
103 if (POLYMAKE_DEBUG) {
104 if (C.empty())
105 throw std::runtime_error("is_manifold: empty complex");
106 }
107 // compute the vertex set and test whether C is a pure 1-complex
108 Set<Int> V;
109 for (auto c_it=entire(C); !c_it.at_end(); ++c_it) {
110 V+=*c_it;
111 if (POLYMAKE_DEBUG) {
112 if (c_it->size() > d+1) {
113 std::ostringstream err;
114 err << "is_manifold: Dimension of " << *c_it << " is greater than " << d;
115 throw std::runtime_error(err.str());
116 }
117 }
118 if (c_it->size()!=d+1) { // complex is not pure
119 if (bad_link_p) *bad_link_p=-1;
120 return 0;
121 }
122 }
123 return is_manifold(C, V, int_constant<d>(), bad_link_p);
124 }
125
126 // return values: 1=true, 0=false, -1=undef
127 template <typename Complex, typename VertexSet, int d>
is_manifold(const Complex & C,const GenericSet<VertexSet> & V,int_constant<d>,Int * bad_link_p)128 Int is_manifold(const Complex& C, const GenericSet<VertexSet>& V, int_constant<d>, Int* bad_link_p)
129 {
130 // iterate over the vertices and test if their links are (d-1)-balls or (d-1)-spheres
131 for (auto it=entire(V.top()); !it.at_end(); ++it) {
132 const Int bos = is_ball_or_sphere(link(C, scalar2set(*it)), int_constant<d-1>());
133 if (bos <= 0) { // false or undef
134 if (bad_link_p) *bad_link_p = *it;
135 return bos;
136 }
137 }
138 return 1;
139 }
140
141 } }
142
143 // Local Variables:
144 // mode:C++
145 // c-basic-offset:3
146 // indent-tabs-mode:nil
147 // End:
148