Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
SubsetEnumerator.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Array.h>
36#include <ogdf/basic/basic.h>
37
38#include <algorithm>
39#include <functional>
40#include <ostream>
41#include <string>
42
43namespace ogdf {
44template<class E>
45class List;
46
48
96template<typename T>
98protected:
99 bool m_valid;
103
104 void initSubset(int card) {
105 if (card >= 0 && card <= m_subset.size()) {
106 m_index.init(card);
107 for (int i = 0; i < card; ++i) {
108 m_index[i] = i;
109 }
110 m_valid = true;
111 }
112 }
113
114public:
120 template<typename ContainerType>
121 explicit SubsetEnumerator(const ContainerType& set)
122 : m_valid(false), m_maxCard(-1), m_subset(set.size()) {
123 for (auto x : set) {
124 m_subset.push(x);
125 }
126 }
127
129 void begin(int low, int high) {
130 if (high >= low) {
131 m_maxCard = high;
133 initSubset(low);
134 } else {
135 m_valid = false;
136 }
137 }
138
140 void begin(int card) { begin(card, card); }
141
143 void begin() { begin(0, m_subset.size()); }
144
146 int size() const { return m_index.size(); }
147
151
154 bool valid() const { return m_valid; }
155
157 bool hasMember(const T& element) const {
158 for (int index : m_index) {
159 if (element == m_subset[index]) {
160 return true;
161 }
162 }
163 return false;
164 }
165
167 T operator[](int i) const {
168 OGDF_ASSERT(i >= 0);
169 OGDF_ASSERT(i < m_index.size());
170 return m_subset[m_index[i]];
171 }
172
174 void next() {
175 if (m_valid) {
176 const int t = m_index.size();
177 if (t == 0) { // last (empty) subset has been found
178 if (t < m_maxCard) {
179 initSubset(t + 1);
180 } else {
181 m_valid = false;
182 }
183 return;
184 }
185 const int n = m_subset.size();
186 int i;
187 for (i = t - 1; m_index[i] == i + n - t; --i) {
188 if (i == 0) { // the last subset of this cardinality has been found
189 if (t < m_maxCard) {
190 initSubset(t + 1);
191 } else {
192 m_valid = false;
193 }
194 return;
195 }
196 }
197 for (++m_index[i]; i < t - 1; ++i) {
198 m_index[i + 1] = m_index[i] + 1;
199 }
200 }
201 }
202
204 void forEachMember(std::function<void(const T&)> func) const {
205 for (int index : m_index) {
206 func(m_subset[index]);
207 }
208 }
209
211 void list(List<T>& subset) const {
212 forEachMember([&](const T& member) { subset.pushBack(member); });
213 }
214
216 void array(Array<T>& array) const {
217 array.init(m_index.size());
218 for (int i = 0; i < m_index.size(); ++i) {
219 array[i] = m_subset[m_index[i]];
220 }
221 }
222
224 void forEachMemberAndNonmember(std::function<void(const T&)> funcIn,
225 std::function<void(const T&)> funcNotIn) const {
226 for (int i = 0, j = 0; i < m_subset.size(); ++i) {
227 if (j < m_index.size() && m_index[j] == i) {
228 funcIn(m_subset[i]);
229 ++j;
230 } else {
231 funcNotIn(m_subset[i]);
232 }
233 }
234 }
235
237 template<typename ContainerType>
238 void getSubsetAndComplement(ContainerType& subset, ContainerType& complement,
239 std::function<void(ContainerType&, T)> func) const {
240 forEachMemberAndNonmember([&](const T& member) { func(subset, member); },
241 [&](const T& nonmember) { func(complement, nonmember); });
242 }
243
245 void list(List<T>& subset, List<T>& complement) const {
246 getSubsetAndComplement<List<T>>(subset, complement,
247 [](List<T>& lc, T element) { lc.pushBack(element); });
248 }
249
251 bool testForAll(std::function<bool(const T&)> predicate) const {
252 for (int index : m_index) {
253 if (!predicate(m_subset[index])) {
254 return false;
255 }
256 }
257 return true;
258 }
259
261 void print(std::ostream& os, string delim = " ") const {
262 if (valid()) {
263 if (size() > 0) {
264 os << m_subset[m_index[0]];
265 for (int i = 1; i < size(); ++i) {
266 os << delim << m_subset[m_index[i]];
267 }
268 }
269 } else {
270 os << "<<invalid subset>>";
271 }
272 }
273};
274
275template<class T>
276std::ostream& operator<<(std::ostream& os, const SubsetEnumerator<T>& subset) {
277 subset.print(os);
278 return os;
279}
280
281}
Declaration and implementation of Array class and Array algorithms.
Declaration and implementation of ArrayBuffer class.
Basic declarations, included by all source files.
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:64
void push(E e)
Puts a new element in the buffer.
INDEX size() const
Returns number of elements in the buffer.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:219
void init()
Reinitializes the array to an array with empty index set.
Definition Array.h:372
INDEX size() const
Returns the size (number of elements) of the array.
Definition Array.h:302
Doubly linked lists (maintaining the length of the list).
Definition List.h:1451
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1547
Enumerator for k-subsets of a given type.
void begin(int low, int high)
Initializes the SubsetEnumerator to enumerate subsets of cardinalities from low to high.
void print(std::ostream &os, string delim=" ") const
Prints subset to output stream os using delimiter delim.
int size() const
Returns the cardinality of the subset.
void forEachMemberAndNonmember(std::function< void(const T &)> funcIn, std::function< void(const T &)> funcNotIn) const
Calls funcIn for each subset member and funcNotIn for each other element of the set.
SubsetEnumerator(const ContainerType &set)
Constructor.
bool valid() const
Checks if the current subset is valid. If not, the subset is either not initialized or all subsets ha...
void begin()
Initializes the SubsetEnumerator to enumerate all subsets.
void begin(int card)
Initializes the SubsetEnumerator to enumerate subsets of given cardinality.
int numberOfMembersAndNonmembers() const
Returns the cardinality of the (super-)set. This is the maximum size that can be used for a subset.
void array(Array< T > &array) const
Obtains an array of the subset members.
T operator[](int i) const
Gets a member of subset by index (starting from 0).
void getSubsetAndComplement(ContainerType &subset, ContainerType &complement, std::function< void(ContainerType &, T)> func) const
Obtains a container of the subset members and a container of the other elements of the set.
void list(List< T > &subset) const
Obtains (appends) a list of the subset members.
bool testForAll(std::function< bool(const T &)> predicate) const
Tests predicate for all subset members.
void forEachMember(std::function< void(const T &)> func) const
Calls func for each member in the subset.
void next()
Obtains the next subset if possible. The result should be checked using the valid() method.
ArrayBuffer< T > m_subset
void list(List< T > &subset, List< T > &complement) const
Obtains (appends) a list of the subset members and a list of the other elements of the set.
bool hasMember(const T &element) const
Checks in O(subset cardinality) whether element is a member of the subset.
void complement(Graph &G, bool directed=false, bool allowSelfLoops=false)
Computes the complement of G.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:52
The namespace for all OGDF objects.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition Array.h:983