Generated on for Gecode by doxygen 1.18.0
common-pattern.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35
36#include "common-pattern.hh"
37
38#include <fstream>
39#include <memory>
40
41using namespace Gecode;
42
45protected:
54 std::unique_ptr<PatternMining::Database> input;
55 std::vector<int> required_items;
57public:
59 : Options("CommonPattern"),
60 _sequences("sequences","comma-separated sequences over A..Z","ABCBC,BABC,ABDC"),
61 _file("file","sequence database; one sequence per line",""),
62 _support("support","minimum supporting sequences, as a percentage","100"),
63 _required("required","items that must occur, comma-separated letters or IDs",""),
64 _format("format","database format",
65 static_cast<int>(PatternMining::Format::LETTERS)),
66 _language("language","pattern language",
67 static_cast<int>(PatternMining::Language::DEFAULT)),
68 _min_length("min-length","minimum pattern length",1),
69 _motif("motif","default language starts with A and ends with C",true),
70 threshold(0) {
71 _format.add(static_cast<int>(PatternMining::Format::LETTERS),"letters");
72 _format.add(static_cast<int>(PatternMining::Format::INTEGERS),"integers");
73 _format.add(static_cast<int>(PatternMining::Format::SPMF),"spmf");
75 "default","use -motif");
76 _language.add(static_cast<int>(PatternMining::Language::NONE),"none");
77 _language.add(static_cast<int>(PatternMining::Language::MOTIF),"motif");
78 _language.add(static_cast<int>(PatternMining::Language::RE10),"re10");
79 _language.add(static_cast<int>(PatternMining::Language::RE14),"re14");
80 _language.add(static_cast<int>(PatternMining::Language::RE2),"re2");
82 add(_file);
83 add(_format);
88 add(_motif);
89 }
90
92 void read(void) {
94 throw std::invalid_argument("Minimum length must be a positive Gecode integer");
96 const std::string filename(_file.value());
97 if (filename.empty()) {
99 throw std::invalid_argument("Integer and SPMF formats require -file");
100 const std::string text(_sequences.value());
101 if (text.empty() || text.back() == ',')
102 throw std::invalid_argument("Expected comma-separated nonempty A..Z sequences");
103 std::istringstream stream(text);
104 std::string sequence;
105 while (std::getline(stream,sequence,','))
106 sequences.push_back(PatternMining::read_sequence(
108 } else {
109 std::ifstream stream(filename);
110 sequences = PatternMining::read_database(stream,format());
111 }
112 input.reset(new PatternMining::Database(sequences));
114 const std::string items(_required.value());
115 if (!items.empty()) {
116 if (items.back() == ',')
117 throw std::invalid_argument("Empty required item");
118 std::istringstream stream(items);
119 std::string item;
120 while (std::getline(stream,item,',')) {
121 const std::vector<int> parsed = PatternMining::read_sequence(item,
124 if (parsed.size() != 1)
125 throw std::invalid_argument("Required items must be single letters or IDs");
126 required_items.push_back(parsed[0]);
127 }
128 }
129 }
130
131 const PatternMining::Database& database(void) const { return *input; }
132 const std::vector<int>& required(void) const { return required_items; }
133 int support(void) const { return threshold; }
134 int min_length(void) const { return static_cast<int>(_min_length.value()); }
136 return static_cast<PatternMining::Format>(_format.value());
137 }
138 bool letters(void) const { return format() == PatternMining::Format::LETTERS; }
140 const auto selected = static_cast<PatternMining::Language>(_language.value());
141 if (selected == PatternMining::Language::DEFAULT)
144 return selected;
145 }
146};
147
190protected:
195public:
197
199 : IntMaximizeScript(opt), database(opt.database()), letters(opt.letters()) {
201 rel(*this,pattern.length(),IRT_GQ,opt.min_length());
202 frequency = PatternMining::frequent(*this,pattern,database,opt.support());
203 if (opt.language() != PatternMining::Language::NONE)
205 if (!opt.required().empty()) {
206 REG alphabet(IntArgs(database.alphabet));
207 for (int item : opt.required())
208 extensional(*this,pattern,*alphabet + REG(item) + *alphabet);
209 }
211 }
212
213 IntVar cost(void) const override { return pattern.length(); }
214
220
221 Space* copy(void) override { return new CommonPattern(*this); }
222
223 void print(std::ostream& os) const override {
224 os << "\t";
225 for (int i=0; i<pattern.known_length(); i++) {
226 if (i && !letters)
227 os << ' ';
228 if (pattern[i].assigned()) {
229 const int item = pattern[i].val();
230 if (letters)
231 os << static_cast<char>('A'+item-1);
232 else
233 os << item;
234 } else {
235 os << pattern[i];
236 }
237 }
238 os << " (length " << pattern.length()
239 << ", support " << frequency << '/' << database.ends.size()
240 << ")" << std::endl;
241 }
242};
243
247int
248main(int argc, char* argv[]) {
250 opt.solutions(0);
251 opt.search(CommonPattern::SEARCH_DFS);
252 opt.search(CommonPattern::SEARCH_BAB,"bab","find a longest pattern");
253 opt.search(CommonPattern::SEARCH_DFS,"dfs","enumerate frequent patterns");
254 opt.parse_strict(argc,argv);
255 try {
256 opt.read();
257 } catch (const std::invalid_argument& error) {
258 std::cerr << error.what() << std::endl;
259 return 1;
260 }
261 if (opt.search() == CommonPattern::SEARCH_DFS)
263 else
265 return 0;
266}
267
268// STATISTICS: example-any
Sequence database and restrictions on the patterns to mine.
Driver::StringValueOption _support
int min_length(void) const
PatternMining::Language language(void) const
std::vector< int > required_items
Driver::StringValueOption _file
std::unique_ptr< PatternMining::Database > input
void read(void)
Validate external input before constructing a space.
Driver::UnsignedIntOption _min_length
bool letters(void) const
Driver::StringOption _format
PatternMining::Format format(void) const
Driver::StringOption _language
int support(void) const
Driver::StringValueOption _required
Driver::StringValueOption _sequences
const PatternMining::Database & database(void) const
Driver::BoolOption _motif
const std::vector< int > & required(void) const
int main(int argc, char *argv[])
Main-function.
CommonPattern(const CommonPatternOptions &opt)
IntVar cost(void) const override
void print(std::ostream &os) const override
Print a solution to os.
PatternMining::Database database
OpenIntVarList pattern
Space * copy(void) override
CommonPattern(CommonPattern &s)
void add(Driver::BaseOption &o)
Add new option o.
Boolean option.
Definition driver.hh:305
void value(bool v)
Set default value to v.
Definition options.hpp:141
static void run(const Options &opt, Script *s=nullptr)
String-valued option (integer value defined by strings).
Definition driver.hh:189
void add(int v, const char *o, const char *h=nullptr)
Add option value for value v, string o, and help text h.
void value(int v)
Set default value to v.
Definition options.hpp:58
String-valued option.
Definition driver.hh:153
void value(const char *v)
Set default value to v.
Unsigned integer option.
Definition driver.hh:244
void value(unsigned int v)
Set default value to v.
Definition options.hpp:91
IntArgs(void)
Allocate empty array.
Definition array.hpp:42
Integer variables.
Definition int.hh:390
Open list of integer variables.
Definition int.hh:1076
OpenIntVarList(void)
Construct an uninitialized list.
void update(Space &home, OpenVarList< Var > &s)
Update during cloning.
int known_length(void) const
Return the number of constructed positions (their values may be unassigned).
IntVar length(void) const
Return the eventual-length variable.
Options(const char *s)
Initialize options for script with name s.
Regular expressions over integer values.
REG(void)
Initialize as empty sequence (epsilon).
int size(void) const
Return number of elements.
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
Immutable input, with dense ranks internally and original IDs externally.
IntSharedArray ends
Exclusive record ends in items.
IntSet domain(void) const
IntSharedArray alphabet
Rank-to-ID mapping.
Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > > IntMaximizeScript
Base-class for scripts for finding solution of highest integer cost.
Definition driver.hh:1015
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:1230
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
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.