Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
conflict-graph.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, 2014
8  *
9  * Last modified:
10  * $Date: 2014-08-28 14:29:11 +0200 (Thu, 28 Aug 2014) $ by $Author: schulte $
11  * $Revision: 14203 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
39 
40 namespace Gecode { namespace Int { namespace BinPacking {
41 
44  assert(!(p.none(nodes()) && x.none(nodes())));
45  // Iterate over neighbors of pivot node
46  Nodes n(node[pivot(p,x)].n);
47  // Iterate over elements of p
48  Nodes i(p);
49  // The loop iterates over elements in i - n
50  while (i() < nodes()) {
51  int iv = i(), nv = n();
52  if ((n() < nodes()) && (iv == nv)) {
53  ++i; ++n;
54  } else if ((n() < nodes()) && (iv > nv)) {
55  ++n;
56  } else {
57  ++i; ++n;
58 
59  Region reg(home);
60 
61  // Found i.val() to be in i - n
62 
63  NodeSet np, nx;
64  np.allocate(reg,nodes());
65  nx.allocate(reg,nodes());
66 
67  bool empty = NodeSet::iwn(np,p,nx,x,node[iv].n,nodes());
68 
69  p.excl(iv); x.incl(iv);
70 
71  // Update current clique
72  cur.incl(iv,node[iv].w);
73 
74  if (empty) {
75  // Found a max clique
77  } else {
78  GECODE_ES_CHECK(bk(np,nx));
79  }
80 
81  // Reset current clique
82  cur.excl(iv,node[iv].w);
83  }
84  }
85  return ES_OK;
86  }
87 
88 }}}
89 
90 // STATISTICS: int-prop
91 
int nodes(void) const
Return number of nodes.
Node * node
The nodes in the graph.
Definition: bin-packing.hh:241
Handle to region.
Definition: region.hpp:61
ExecStatus clique(void)
Report the current clique.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool none(unsigned int sz) const
Test whether no bits are set.
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
Example: Bin packing
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ExecStatus
Definition: core.hpp:523
Execution is okay.
Definition: core.hpp:527
void allocate(Region &r, int n)
Allocate node set for n nodes.
Gecode toplevel namespace
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
void incl(int i, unsigned int w)
Include node i with weight w.
void excl(int i, unsigned int w)
Exclude node i with weight w.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)