this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 2012
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#ifndef GECODE_SET_LDSB_HH
35#define GECODE_SET_LDSB_HH
36
37#include <gecode/set.hh>
38#include <gecode/int/ldsb.hh>
39
40/**
41 * \namespace Gecode::Set::LDSB
42 * \brief Symmetry breaking for set variables
43 */
44namespace Gecode { namespace Set { namespace LDSB {
45
46 using namespace Int::LDSB;
47
48 /**
49 * \brief Symmetry-breaking brancher with generic view and value
50 * selection
51 *
52 * Implements view-based branching for an array of views (of type
53 * \a View) on set variables and value (of type \a Val).
54 *
55 */
56 template<class View, int n, class Val, unsigned int a,
57 class Filter, class Print>
58 class LDSBSetBrancher : public LDSBBrancher<View,n,Val,a,Filter,Print> {
59 public:
60 using typename LDSBBrancher<View,n,Val,a,Filter,Print>::Var;
61 /// Position of previous variable that was branched on
62 int _prevPos;
63 /// Number of non-value symmetries
64 int _nNonValueSymmetries;
65 /// Number of value symmetries
66 int _nValueSymmetries;
67 /// Copy of value symmetries from the first node where the current
68 /// variable was branched on.
69 ValueSymmetryImp<View>** _copiedSyms;
70 /// Number of copied symmetries
71 int _nCopiedSyms;
72 /// Set of values used on left branches for the current variable
73 IntSet _leftBranchValues;
74 /**
75 * \brief Is the state of the brancher "stable"?
76 *
77 * The brancher is unstable if we are about to run either "choice"
78 * or "commit", but "updatePart1" has not been run. After
79 * "updatePart1" has been run the brancher is stable, until the
80 * second part of the update is done (in commit).
81 */
82 bool _stable;
83
84 /// Constructor for cloning \a b
85 LDSBSetBrancher(Space& home, LDSBSetBrancher& b);
86 /// Constructor for creation
87 LDSBSetBrancher(Home home,
88 ViewArray<View>& x,
89 ViewSel<View>* vs[n],
90 ValSelCommitBase<View,Val>* vsc,
91 SymmetryImp<View>** syms, int nsyms,
92 BranchFilter<Var> bf,
93 VarValPrint<Var,Val> vvp);
94 /// Return choice
95 virtual const Choice* choice(Space& home);
96 /// Perform commit for choice \a c and alternative \a b
97 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
98 /// Perform cloning
99 virtual Actor* copy(Space& home);
100 /// Brancher post function
101 static void post(Home home,
102 ViewArray<View>& x,
103 ViewSel<View>* vs[n],
104 ValSelCommitBase<View,Val>* vsc,
105 SymmetryImp<View>** _syms,
106 int _nsyms,
107 BranchFilter<Var> bf,
108 VarValPrint<Var,Val> vvp);
109
110 /// Post LDSB brancher
111 template<class View0, int n0, class Val0, unsigned int a0>
112 void postldsbsetbrancher(Home home,
113 ViewArray<View0>& x,
114 ViewSel<View0>* vs[n0],
115 ValSelCommitBase<View0,Val0>* vsc,
116 SymmetryImp<View0>** syms, int nsyms,
117 BranchFilter<typename View0::VarType> bf,
118 VarValPrint<typename View0::VarType,Val0> vvp);
119
120 /**
121 * \brief Part one of the update phase
122 *
123 * If the branching is at a new variable, restore previously
124 * copied value symmetries, do bulk update of values used on left
125 * branches for the previous variable, and make fresh copy of
126 * resulting value symmetries.
127 */
128 void updatePart1(Space& home, int choicePos);
129 };
130
131}}}
132
133namespace Gecode { namespace Int { namespace LDSB {
134
135 template <>
136 ArgArray<Literal>
137 VariableSequenceSymmetryImp<Set::SetView>
138 ::symmetric(Literal l, const ViewArray<Set::SetView>& x) const;
139
140}}}
141
142#include <gecode/set/ldsb/brancher.hpp>
143
144#endif
145
146// STATISTICS: set-branch