Generated on for Gecode by doxygen 1.17.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(
243 data.alphabet.begin(),data.alphabet.end(),item)-data.alphabet.begin());
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
345 : Propagator(home,p), projection(home,p.projection),
349 list.update(home,p.list);
350 length.update(home,p.length);
351 frequency.update(home,p.frequency);
352 }
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 {
360 return PropCost::linear(PropCost::HI,projection.data.items.size());
361 }
362
363 void reschedule(Space& home) override {
364 list.reschedule(home,*this);
365 length.reschedule(home,*this,Int::PC_INT_BND);
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);
379 while (true) {
380 while ((consumed < size) && list[consumed].assigned()) {
381 if (!projection.advance(list[consumed].val()))
382 return ES_FAILED;
383 consumed++;
384 }
385 GECODE_ME_CHECK(frequency.lq(home,projection.support()));
386 if ((consumed == size) && (length.max() == size)) {
387 GECODE_ME_CHECK(frequency.eq(home,projection.support()));
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)) {
395 GECODE_ME_CHECK(frequency.eq(home,projection.support()));
396 return home.ES_SUBSUMED(*this);
397 }
398 frequent_items = projection.frequent(region);
400 first = consumed;
401 }
402 if (frequent_items.size() == 0) {
404 GECODE_ME_CHECK(frequency.eq(home,projection.support()));
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
Passing integer arguments.
Definition int.hh:653
Value iterator for integer sets.
Definition int.hh:352
Integer sets.
Definition int.hh:179
Integer variables.
Definition int.hh:390
Integer view for integer variables.
Definition view.hpp:129
Open list of integer variables.
Definition int.hh:1076
View interface to a space-local list with an open length.
Definition int.hh:1044
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
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1086
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Regular expressions over integer values.
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.
int size(void) const
Return number of elements.
Computation spaces.
Definition core.hpp:1787
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 .
Definition count.cpp:40
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
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.