Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
ind-set.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2002
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
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#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38using namespace Gecode;
39
47class Graph {
48public:
49 const int n_v;
50 const int n_e;
51 const int* e;
52 Graph(const int n_v0, const int n_e0, const int* e0)
53 : n_v(n_v0), n_e(n_e0), e(e0) {}
54};
55
56const int e_20_10[] = {
57 0, 4, 2,12, 12,14, 18,19, 7,10,
58 9,12, 5,11, 6,15, 3,18, 7,16
59};
60
61const Graph g_20_10(20,10,e_20_10);
62
63const int e_40_20[] = {
64 21,30, 11,30, 19,38, 20,25, 11,24,
65 20,33, 8,39, 4, 5, 6,16, 5,32,
66 0, 9, 5,24, 25,28, 36,38, 14,20,
67 19,25, 11,22, 13,30, 7,36, 15,33
68};
69
70const Graph g_40_20(40, 20, e_40_20);
72
73
80class IndSet : public IntMaximizeScript {
81protected:
83 const Graph& g;
88public:
90 IndSet(const SizeOptions& opt)
91 : IntMaximizeScript(opt),
92 g(opt.size() == 0 ? g_20_10 : g_40_20),
93 v(*this,g.n_v,0,1), k(*this,0,g.n_v) {
94 const int* e = g.e;
95 for (int i = g.n_e; i--; ) {
96 const int* e1 = e++; const int* e2 = e++;
97 rel(*this, v[*e1], BOT_AND, v[*e2], 0);
98 }
99 linear(*this, v, IRT_EQ, k);
100 branch(*this, v, BOOL_VAR_NONE(), BOOL_VAL_MIN());
101 }
102
105 v.update(*this, s.v);
106 k.update(*this, s.k);
107 }
109 virtual Space*
110 copy(void) {
111 return new IndSet(*this);
112 }
114 virtual void
115 print(std::ostream& os) const {
116 os << "\tk = " << k << std::endl
117 << "\tv[] = " << v << std::endl;
118 }
120 virtual IntVar cost(void) const {
121 return k;
122 }
123};
124
125
129int
130main(int argc, char* argv[]) {
131 SizeOptions opt("IndSet");
132 opt.solutions(0);
133 opt.size(1);
134 opt.iterations(2000);
135 opt.parse(argc,argv);
137 return 0;
138}
139
140// STATISTICS: example-any
141
Boolean variable array.
Definition int.hh:808
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
Integer variables.
Definition int.hh:371
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
Graph specification
Definition ind-set.cpp:47
Graph(const int n_v0, const int n_e0, const int *e0)
Definition ind-set.cpp:52
const int * e
Arrays of edges (as vertex pairs)
Definition ind-set.cpp:51
const int n_e
Number of edges.
Definition ind-set.cpp:50
const int n_v
Number of vertices.
Definition ind-set.cpp:49
Example: Independent sets in a graph
Definition ind-set.cpp:80
int main(int argc, char *argv[])
Main-function.
Definition ind-set.cpp:130
IndSet(IndSet &s)
Constructor for cloning s.
Definition ind-set.cpp:104
virtual Space * copy(void)
Copy during cloning.
Definition ind-set.cpp:110
const Graph g_20_10(20, 10, e_20_10)
Main-function.
const Graph g_40_20(40, 20, e_40_20)
Main-function.
IntVar k
How many elements has indipendent set.
Definition ind-set.cpp:87
BoolVarArray v
Whether vertex included in independent set.
Definition ind-set.cpp:85
virtual void print(std::ostream &os) const
Print solution.
Definition ind-set.cpp:115
const Graph & g
Graph used
Definition ind-set.cpp:83
virtual IntVar cost(void) const
Return solution cost.
Definition ind-set.cpp:120
IndSet(const SizeOptions &opt)
Actual model.
Definition ind-set.cpp:90
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
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.
Definition branch.cpp:39
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
@ IRT_EQ
Equality ( )
Definition int.hh:926
Gecode toplevel namespace
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition val.hpp:130
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364