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/Set.h"
21 #include "polymake/graph/Lattice.h"
22 #include "polymake/graph/graph_iterators.h"
23
24
25 namespace polymake { namespace graph {
26
27 template <typename LType>
find_vertex_node(const LType & HD,Int v)28 Int find_vertex_node(const LType& HD, Int v)
29 {
30 for (const auto n: HD.nodes_of_rank(1))
31 if (HD.face(n).front()==v)
32 return n;
33 throw no_match("vertex node not found");
34 }
35
36 template <typename LType, typename SetType>
find_facet_node(const LType & HD,const GenericSet<SetType> & F)37 Int find_facet_node(const LType& HD, const GenericSet<SetType>& F)
38 {
39 for (const auto f: HD.nodes_of_rank(HD.rank()-1))
40 if (HD.face(f)==F)
41 return f;
42 throw no_match("facet node not found");
43 }
44
45 template <typename LType>
46 class HasseDiagram_facet_iterator
47 : public BFSiterator< Graph<Directed> > {
48 using base_t = BFSiterator< Graph<Directed> >;
49 protected:
50 const LType *HD;
51 Int top_node;
52
valid_position()53 void valid_position()
54 {
55 Int n;
56 while (n = *(*this), HD->out_adjacent_nodes(n).front() != top_node)
57 base_t::operator++();
58 }
59 public:
60 using iterator = HasseDiagram_facet_iterator;
61 using const_iterator = HasseDiagram_facet_iterator;
62
HasseDiagram_facet_iterator()63 HasseDiagram_facet_iterator() : HD(nullptr) {}
64
HasseDiagram_facet_iterator(const LType & HD_arg)65 HasseDiagram_facet_iterator(const LType& HD_arg)
66 : base_t(HD_arg.graph(), HD_arg.bottom_node())
67 , HD(&HD_arg)
68 , top_node(HD_arg.top_node())
69 {
70 if (!at_end() && *(*this)!=top_node) valid_position();
71 }
72
HasseDiagram_facet_iterator(const LType & HD_arg,Int start_node)73 HasseDiagram_facet_iterator(const LType& HD_arg, Int start_node)
74 : base_t(HD_arg.graph(), start_node)
75 , HD(&HD_arg)
76 , top_node(HD_arg.top_node())
77 {
78 if (!at_end() && *(*this)!=top_node) valid_position();
79 }
80
81 iterator& operator++()
82 {
83 queue.pop_front();
84 if (!at_end()) valid_position();
85 return *this;
86 }
87 const iterator operator++(int) { iterator copy(*this); operator++(); return copy; }
88
face()89 const Set<Int>& face() const { return HD->face(*(*this)); }
graph()90 const Graph<Directed>& graph() const { return HD->graph(); }
face(Int n)91 const Set<Int>& face(Int n) const { return HD->face(n); }
92 };
93
94 using Down = std::true_type;
95 using Up = std::false_type;
96
97 template<typename Direction, typename LType>
order_ideal(const Set<Int> & generators,const LType & LF)98 Set<Int> order_ideal(const Set<Int>& generators, const LType& LF)
99 {
100 Set<Int> queue(generators), order_ideal; // make the queue a Set because any given element will be inserted lots of times
101 while (!queue.empty()) {
102 const Int s = queue.front();
103 queue -= s;
104 order_ideal += s;
105 if (Direction::value)
106 queue += LF.in_adjacent_nodes(s);
107 else
108 queue += LF.out_adjacent_nodes(s);
109 }
110 return order_ideal;
111 }
112
113 template<typename HDType>
is_convex_subset(const Set<Int> & Cset,const HDType & LF,bool verbose)114 bool is_convex_subset(const Set<Int>& Cset, const HDType& LF, bool verbose)
115 {
116 // prepare down-sets and up-sets
117 std::vector<Set<Int>> down_set_of(LF.nodes()), up_set_of(LF.nodes());
118 for (const auto& c: Cset) {
119 down_set_of[c] = order_ideal<Down>(scalar2set(c), LF);
120 up_set_of [c] = order_ideal<Up> (scalar2set(c), LF);
121 }
122
123 // check convexity
124 for (Int d1 = 1; d1 <= LF.rank()-2; ++d1) {
125 for (const auto d1node: LF.nodes_of_rank(d1)) {
126 if (!Cset.contains(d1node)) continue;
127
128 for (Int d2 = d1+2; d2 <= LF.rank(); ++d2) {
129 for (const auto d2node: LF.nodes_of_rank(d2)) {
130 if (!Cset.contains(d2node)) continue;
131 const Set<Int> interval = up_set_of[d1node] * down_set_of[d2node];
132 if (incl(interval, Cset) > 0) {
133 if (verbose) cout << "The given set is not convex because "
134 << "it contains " << d1node << "=" << LF.face(d1node)
135 << " and " << d2node << "=" << LF.face(d2node)
136 << ", but not the faces indexed by " << interval - Cset << " which are contained in the interval between them."
137 << endl;
138 return false;
139 }
140 }
141 }
142 }
143 }
144 return true;
145 }
146
147 } }
148
149 namespace pm {
150 template <typename Decoration>
151 struct check_iterator_feature<polymake::graph::HasseDiagram_facet_iterator<Decoration>, end_sensitive> : std::true_type {};
152 }
153
154
155 // Local Variables:
156 // mode:C++
157 // c-basic-offset:3
158 // indent-tabs-mode:nil
159 // End:
160