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
38 using namespace Gecode;
39
40 /**
41 * \name %Graph specification for independent sets
42 *
43 * \relates IndSet
44 */
45 //@{
46 /// %Graph specification
47 class Graph {
48 public:
49 const int n_v; ///< Number of vertices
50 const int n_e; ///< Number of edges
51 const int* e; ///< Arrays of edges (as vertex pairs)
Graph(const int n_v0,const int n_e0,const int * e0)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
56 const 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
61 const Graph g_20_10(20,10,e_20_10);
62
63 const 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
70 const Graph g_40_20(40, 20, e_40_20);
71 //@}
72
73
74 /**
75 * \brief %Example: Independent sets in a graph
76 *
77 * \ingroup Example
78 *
79 */
80 class IndSet : public IntMaximizeScript {
81 protected:
82 /// %Graph used
83 const Graph& g;
84 /// Whether vertex included in independent set
85 BoolVarArray v;
86 /// How many elements has indipendent set
87 IntVar k;
88 public:
89 /// Actual model
IndSet(const SizeOptions & opt)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
103 /// Constructor for cloning \a s
IndSet(IndSet & s)104 IndSet(IndSet& s) : IntMaximizeScript(s), g(s.g) {
105 v.update(*this, s.v);
106 k.update(*this, s.k);
107 }
108 /// Copy during cloning
109 virtual Space*
copy(void)110 copy(void) {
111 return new IndSet(*this);
112 }
113 /// Print solution
114 virtual void
print(std::ostream & os) const115 print(std::ostream& os) const {
116 os << "\tk = " << k << std::endl
117 << "\tv[] = " << v << std::endl;
118 }
119 /// Return solution cost
cost(void) const120 virtual IntVar cost(void) const {
121 return k;
122 }
123 };
124
125
126 /** \brief Main-function
127 * \relates IndSet
128 */
129 int
main(int argc,char * argv[])130 main(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);
136 IntMaximizeScript::run<IndSet,BAB,SizeOptions>(opt);
137 return 0;
138 }
139
140 // STATISTICS: example-any
141
142