Generated on for Gecode by doxygen 1.18.0
common-pattern.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Private modelling support for the common-pattern example.
4 * Copyright Mikael Zayenz Lagerkvist, 2026.
5 * Distributed under the MIT license; see LICENSE.
6 */
7
8#ifndef GECODE_EXAMPLES_COMMON_PATTERN_HH
9#define GECODE_EXAMPLES_COMMON_PATTERN_HH
10
11#include <gecode/int.hh>
12#include <gecode/minimodel.hh>
13
14#include <algorithm>
15#include <charconv>
16#include <functional>
17#include <istream>
18#include <sstream>
19#include <stdexcept>
20#include <string>
21#include <vector>
22
23namespace PatternMining {
24
25 using namespace Gecode;
26 typedef std::vector<std::vector<int>> Sequences;
27
28 enum class Format { LETTERS, INTEGERS, SPMF };
29 enum class Language { DEFAULT, NONE, MOTIF, RE10, RE14, RE2 };
30
32 inline std::vector<int>
33 read_sequence(const std::string& line, Format format) {
34 std::vector<int> sequence;
35 if (format == Format::LETTERS) {
36 for (char a : line) {
37 if ((a < 'A') || (a > 'Z'))
38 throw std::invalid_argument("Letter sequences must contain A..Z only");
39 sequence.push_back(a-'A'+1);
40 }
41 } else {
42 std::istringstream stream(line);
43 std::string token;
44 bool open_itemset = false;
45 bool ended = false;
46 while (stream >> token) {
47 int item;
48 const auto parsed = std::from_chars(token.data(),token.data()+token.size(),item);
49 if ((parsed.ec != std::errc()) || (parsed.ptr != token.data()+token.size()))
50 throw std::invalid_argument("Invalid integer item");
51 if (ended)
52 throw std::invalid_argument("Items after SPMF sequence end");
53 if ((format == Format::SPMF) && (item == -1)) {
54 if (!open_itemset)
55 throw std::invalid_argument("Empty SPMF itemset");
56 open_itemset = false;
57 } else if ((format == Format::SPMF) && (item == -2)) {
58 if (open_itemset)
59 throw std::invalid_argument("Missing SPMF itemset end");
60 ended = true;
61 } else {
62 if ((item <= 0) || (item > Int::Limits::max) ||
63 ((format == Format::SPMF) && open_itemset))
64 throw std::invalid_argument("Expected positive items; SPMF itemsets must be singletons");
65 sequence.push_back(item);
66 open_itemset = true;
67 }
68 }
69 if (!stream.eof() || ((format == Format::SPMF) && !ended))
70 throw std::invalid_argument("Invalid sequence or missing SPMF sequence end");
71 }
72 if (sequence.empty())
73 throw std::invalid_argument("Empty sequence");
74 return sequence;
75 }
76
78 inline Sequences
79 read_database(std::istream& stream, Format format) {
80 Sequences input;
81 std::string line;
82 while (std::getline(stream,line)) {
83 if (!line.empty() && (line.back() == '\r'))
84 line.pop_back();
85 if (line.empty() || ((format == Format::SPMF) &&
86 ((line[0] == '#') || (line[0] == '%') || (line[0] == '@'))))
87 continue;
88 input.push_back(read_sequence(line,format));
89 }
90 if (!stream.eof() || input.empty())
91 throw std::invalid_argument("Cannot read a nonempty sequence database");
92 return input;
93 }
94
96 inline int
97 minimum_support(const std::string& percent, int sequences) {
98 unsigned long long numerator = 0;
99 unsigned long long scale = 1;
100 bool decimal = false;
101 for (char c : percent) {
102 if ((c == '.') && !decimal) {
103 decimal = true;
104 } else if ((c >= '0') && (c <= '9')) {
105 numerator = numerator*10 + (c-'0');
106 if (decimal)
107 scale *= 10;
108 if ((numerator > 100000000ULL) || (scale > 1000000ULL))
109 throw std::invalid_argument("Support needs at most six decimals");
110 } else {
111 throw std::invalid_argument("Support must be a percentage in (0,100]");
112 }
113 }
114 if ((numerator == 0) || (numerator > 100*scale))
115 throw std::invalid_argument("Support must be a percentage in (0,100]");
116 const unsigned long long denominator = 100*scale;
117 return static_cast<int>((sequences*numerator+denominator-1)/denominator);
118 }
119
121 class Database {
122 public:
133
134 explicit Database(const Sequences& input) {
135 if (input.empty())
136 throw std::invalid_argument("Empty database");
137 std::vector<int> symbols;
138 for (const std::vector<int>& sequence : input) {
139 if (sequence.empty() ||
140 (sequence.size() >= static_cast<size_t>(Int::Limits::max)-symbols.size()))
141 throw std::invalid_argument("Empty sequence or database too large");
142 for (int item : sequence) {
143 if ((item <= 0) || (item > Int::Limits::max))
144 throw std::invalid_argument("Item IDs must be positive Gecode integers");
145 symbols.push_back(item);
146 }
147 }
148 items.init(static_cast<int>(symbols.size()));
149 std::sort(symbols.begin(),symbols.end());
150 symbols.erase(std::unique(symbols.begin(),symbols.end()),symbols.end());
151 alphabet.init(static_cast<int>(symbols.size()));
152 std::copy(symbols.begin(),symbols.end(),alphabet.begin());
153 ends.init(static_cast<int>(input.size()));
154 last_ends.init(static_cast<int>(input.size()));
155 Region region;
156 int* seen = region.alloc<int>(alphabet.size());
157 std::fill(seen,seen+alphabet.size(),-1);
158 std::vector<int> last;
159 int position = 0;
160 int record = 0;
161 for (const std::vector<int>& sequence : input) {
162 const int start = position;
163 for (int item : sequence)
164 items[position++] = static_cast<int>(std::lower_bound(
165 symbols.begin(),symbols.end(),item)-symbols.begin());
166 ends[record] = position;
167 for (int j=position; j-- > start; )
168 if (seen[items[j]] != record) {
169 seen[items[j]] = record;
170 last.push_back(j);
171 }
172 last_ends[record++] = static_cast<int>(last.size());
173 }
174 last_positions.init(static_cast<int>(last.size()));
175 std::copy(last.begin(),last.end(),last_positions.begin());
176 }
177
178 IntSet domain(void) const { return IntSet(alphabet.begin(),alphabet.size()); }
179
180 int max_length(void) const {
181 int bound = 0;
182 int start = 0;
183 for (int end : ends) {
184 bound = std::max(bound,end-start);
185 start = end;
186 }
187 return bound;
188 }
189
191 int support(const std::vector<int>& pattern) const {
192 int count = 0;
193 int start = 0;
194 for (int end : ends) {
195 size_t matched = 0;
196 for (int i=start; (i<end) && (matched<pattern.size()); i++)
197 if (alphabet[items[i]] == pattern[matched])
198 matched++;
199 count += matched == pattern.size();
200 start = end;
201 }
202 return count;
203 }
204 };
205
216 protected:
217 struct Suffix {
219 int begin;
220 };
222 int size;
223 public:
226
227 Projection(Space& home, const Database& database, int support)
228 : suffixes(home.alloc<Suffix>(database.ends.size())),
229 size(database.ends.size()), data(database), threshold(support) {
230 for (int i=0; i<size; i++)
231 suffixes[i] = {i,(i == 0) ? 0 : data.ends[i-1]};
232 }
233
234 Projection(Space& home, const Projection& p)
235 : suffixes(home.alloc<Suffix>(p.size)), size(p.size),
237 std::copy(p.suffixes,p.suffixes+size,suffixes);
238 }
239
241 bool advance(int item) {
242 const int rank = static_cast<int>(std::lower_bound(
244 if ((rank == data.alphabet.size()) || (data.alphabet[rank] != item))
245 return false;
246 int n = 0;
247 for (int i=0; i<size; i++) {
248 const int sequence = suffixes[i].sequence;
249 int pos = suffixes[i].begin;
250 const int end = data.ends[sequence];
251 while ((pos < end) && (data.items[pos] != rank))
252 pos++;
253 if (pos < end)
254 suffixes[n++] = {sequence,pos+1};
255 }
256 size = n;
257 return size >= threshold;
258 }
259
260 int support(void) const { return size; }
261
269 IntSet frequent(Region& region) const {
270 const int d = data.alphabet.size();
271 int* count = region.alloc<int>(d);
272 std::fill(count,count+d,0);
273 for (int i=0; i<size; i++) {
274 const int sequence = suffixes[i].sequence;
275 const int start = (sequence == 0) ? 0 : data.last_ends[sequence-1];
276 for (int j=start; j<data.last_ends[sequence]; j++) {
277 const int pos = data.last_positions[j];
278 if (pos < suffixes[i].begin)
279 break;
280 count[data.items[pos]]++;
281 }
282 }
283 int* values = region.alloc<int>(d);
284 int n = 0;
285 for (int a=0; a<d; a++)
286 if (count[a] >= threshold)
287 values[n++] = data.alphabet[a];
288 return IntSet(values,n);
289 }
290
292 int remaining(Region& region) const {
293 int* sizes = region.alloc<int>(size);
294 for (int i=0; i<size; i++)
295 sizes[i] = data.ends[suffixes[i].sequence]-suffixes[i].begin;
296 std::nth_element(sizes,sizes+threshold-1,sizes+size,std::greater<int>());
297 return sizes[threshold-1];
298 }
299 };
300
319 class OpenProjection : public Propagator {
320 protected:
330
332 const Database& database, int support, IntVar count)
333 : Propagator(home), list(pattern), length(pattern.length()), frequency(count),
334 projection(home,database,support), consumed(0),
335 subscribed(pattern.known_length()), cached_prefix(-1) {
336 home.notice(*this,AP_DISPOSE);
337 list.subscribe(home,*this);
338 length.subscribe(home,*this,Int::PC_INT_BND);
339 for (int i=0; i<subscribed; i++)
340 if (!list[i].assigned())
341 list[i].subscribe(home,*this,Int::PC_INT_VAL);
342 }
343
353
354 public:
355 Actor* copy(Space& home) override {
356 return new (home) OpenProjection(home,*this);
357 }
358
359 PropCost cost(const Space&, const ModEventDelta&) const override {
361 }
362
363 void reschedule(Space& home) override {
364 list.reschedule(home,*this);
366 for (int i=consumed; i<subscribed; i++)
367 if (!list[i].assigned())
368 list[i].reschedule(home,*this,Int::PC_INT_VAL);
369 }
370
371 ExecStatus propagate(Space& home, const ModEventDelta&) override {
372 const int size = list.known_length();
373 // Refilter earlier positions only when the assigned prefix changes.
374 int first = subscribed;
375 for (int i=subscribed; i<size; i++)
376 if (!list[i].assigned())
377 list[i].subscribe(home,*this,Int::PC_INT_VAL,false);
378 subscribed = size;
379 while (true) {
380 while ((consumed < size) && list[consumed].assigned()) {
381 if (!projection.advance(list[consumed].val()))
382 return ES_FAILED;
383 consumed++;
384 }
386 if ((consumed == size) && (length.max() == size)) {
388 return home.ES_SUBSUMED(*this);
389 }
390 if (cached_prefix != consumed) {
391 Region region;
392 const int extension_bound = projection.remaining(region);
393 GECODE_ME_CHECK(length.lq(home,consumed+extension_bound));
394 if ((consumed == size) && (length.max() == size)) {
396 return home.ES_SUBSUMED(*this);
397 }
400 first = consumed;
401 }
402 if (frequent_items.size() == 0) {
405 return home.ES_SUBSUMED(*this);
406 }
407 for (int i=first; i<size; i++) {
409 GECODE_ME_CHECK(list[i].inter_v(home,values,false));
410 }
411 first = size;
412 if ((consumed == size) || !list[consumed].assigned())
413 return ES_FIX;
414 }
415 }
416
417 size_t dispose(Space& home) override {
418 home.ignore(*this,AP_DISPOSE);
419 list.cancel(home,*this);
420 length.cancel(home,*this,Int::PC_INT_BND);
421 if (!home.failed())
422 for (int i=consumed; i<subscribed; i++)
423 if (!list[i].assigned())
424 list[i].cancel(home,*this,Int::PC_INT_VAL);
425 list.~OpenViewList();
426 projection.~Projection();
427 frequent_items.~IntSet();
428 (void) Propagator::dispose(home);
429 return sizeof(*this);
430 }
431
432 static void post(Home home, OpenViewList<Int::IntView> pattern,
433 const Database& database, int support, IntVar count) {
434 (void) new (home) OpenProjection(home,pattern,database,support,count);
435 }
436 };
437
439 inline IntVar
441 const Database& database, int support) {
442 if (home.failed())
443 return IntVar();
444 if ((support < 1) || (support > database.ends.size())) {
445 home.fail();
446 return IntVar();
447 }
448 IntVar count(home,support,database.ends.size());
450 database,support,count);
451 return count;
452 }
453
455 inline REG
456 language(Language name, const Database& database) {
457 if (name == Language::RE10)
458 return *REG(1) + REG(2) + (REG(2) | REG(3)) + *REG(4) +
459 REG(5) + *REG(6) + (REG(7) | REG(8)) + *REG(9);
460 if (name == Language::RE14)
461 return *REG(1) + (REG(17) | (REG(2) + *REG(19) +
462 (REG(2) | REG(3)))) + *REG(4) + REG(5) + *(REG(9) | REG(19)) +
463 (REG(6) | REG(8)) + *REG(7) + REG(18);
464 REG alphabet(IntArgs(database.alphabet.size(),database.alphabet.begin()));
465 if (name == Language::MOTIF)
466 return REG(1) + *alphabet + REG(3);
467 return (REG(19) | REG(20)) + alphabet + (REG(18) | REG(11));
468 }
469
470}
471
472#endif
473
474// STATISTICS: example-any
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
void fail(void)
Mark space as failed.
Definition core.hpp:4284
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4293
IntArgs(void)
Allocate empty array.
Definition array.hpp:42
Value iterator for integer sets.
Definition int.hh:352
Integer sets.
Definition int.hh:179
unsigned int size(void) const
Return size (cardinality) of set.
IntSet(void)
Initialize as empty set.
Definition int-set-1.hpp:47
Integer variables.
Definition int.hh:390
IntVar(void)
Default constructor.
Definition int.hpp:47
Integer view for integer variables.
Definition view.hpp:129
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Open list of integer variables.
Definition int.hh:1076
View interface to a space-local list with an open length.
Definition int.hh:1044
void reschedule(Space &home, Propagator &p)
Reschedule p for construction of positions.
int known_length(void) const
Return the number of constructed positions.
void update(Space &home, OpenViewList< View > &s)
Update during cloning.
void cancel(Space &home, Propagator &p)
Cancel the subscription of p to construction of positions.
void subscribe(Space &home, Propagator &p)
Subscribe p to construction of positions.
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Regular expressions over integer values.
REG(void)
Initialize as empty sequence (epsilon).
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
iterator begin(void)
Return an iterator at the beginning of the array.
iterator end(void)
Return an iterator past the end of the array.
int size(void) const
Return number of elements.
void init(int n)
Initialize as array with n elements.
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition view.hpp:567
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:527
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
Immutable input, with dense ranks internally and original IDs externally.
IntSharedArray ends
Exclusive record ends in items.
Database(const Sequences &input)
IntSet domain(void) const
IntSharedArray last_ends
Exclusive record ends in last_positions.
int support(const std::vector< int > &pattern) const
Count supporting records, rather than embeddings within a record.
IntSharedArray items
Concatenated item ranks.
IntSharedArray alphabet
Rank-to-ID mapping.
IntSharedArray last_positions
Each item's last position per record, in decreasing position order.
int cached_prefix
Prefix length at which the item filter and length bound were computed.
OpenProjection(Home home, OpenViewList< Int::IntView > pattern, const Database &database, int support, IntVar count)
size_t dispose(Space &home) override
Delete actor and return its size.
OpenProjection(Space &home, OpenProjection &p)
PropCost cost(const Space &, const ModEventDelta &) const override
Cost function.
void reschedule(Space &home) override
Schedule function.
OpenViewList< Int::IntView > list
static void post(Home home, OpenViewList< Int::IntView > pattern, const Database &database, int support, IntVar count)
ExecStatus propagate(Space &home, const ModEventDelta &) override
Propagation function.
Actor * copy(Space &home) override
Create copy.
Suffixes of records supporting the assigned pattern prefix.
Projection(Space &home, const Database &database, int support)
Projection(Space &home, const Projection &p)
bool advance(int item)
Extend the prefix by one item and report whether enough records support it.
int remaining(Region &region) const
The threshold-th largest suffix length bounds every frequent extension.
IntSet frequent(Region &region) const
Items occurring in at least threshold supporting suffixes.
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
const int max
Largest allowed integer value.
Definition int.hh:121
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:90
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
ExecStatus
Definition core.hpp:479
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
std::vector< int > read_sequence(const std::string &line, Format format)
Read positive integer items or A..Z (represented by item IDs 1..26).
int minimum_support(const std::string &percent, int sequences)
Round the support percentage (at most six decimals) up to a record count.
IntVar frequent(Home home, OpenIntVarList pattern, const Database &database, int support)
Enforce minimum support and return its exact count when the pattern is complete.
REG language(Language name, const Database &database)
Built-in motif and benchmark languages described in CommonPattern.
std::vector< std::vector< int > > Sequences
Sequences read_database(std::istream &stream, Format format)
Read one sequence per line, counting duplicate rows as distinct records.