base.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2007
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Int { namespace Circuit {
template<class View, class Offset>
forceinline
Base<View,Offset>::Base(Home home, ViewArray<View>& x, Offset& o0)
: NaryPropagator<View,Int::PC_INT_DOM>(home,x),
start(0), y(home,x), o(o0) {
home.notice(*this,AP_WEAKLY);
}
template<class View, class Offset>
forceinline
Base<View,Offset>::Base(Space& home, Base<View,Offset>& p)
: NaryPropagator<View,Int::PC_INT_DOM>(home,p), start(p.start) {
o.update(p.o);
y.update(home,p.y);
}
template<class View>
class NodeInfo {
public:
int min, low, pre;
Int::ViewValues<View> v;
};
template<class View>
class TellInfo {
public:
View x; int n;
};
template<class View, class Offset>
ExecStatus
Base<View,Offset>::connected(Space& home) {
int n = x.size();
{
int v = start;
int m = n;
while (x[v].assigned()) {
m--;
v = o(x[v]).val();
// Reached start node again, check whether all nodes have been visited
if (start == v)
return (m == 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
}
start = v;
}
Region r;
typedef typename Offset::ViewType OView;
NodeInfo<OView>* si = r.alloc<NodeInfo<OView> >(n);
unsigned int n_edges = 0;
for (int i=0; i<n; i++) {
n_edges += x[i].size();
si[i].pre=-1;
}
// Stack to remember which nodes have not been processed completely
Support::StaticStack<int,Region> next(r,n);
// Array to remember which mandatory tells need to be done
TellInfo<OView>* eq = r.alloc<TellInfo<OView> >(n);
int n_eq = 0;
// Array to remember which edges need to be pruned
TellInfo<OView>* nq = r.alloc<TellInfo<OView> >(n_edges);
int n_nq = 0;
/*
* Check whether there is a single strongly connected component.
* This is a downstripped version of Tarjan's algorithm as
* the computation of sccs proper is not needed. In addition, it
* checks a mandatory condition for a graph to be Hamiltonian
* (due to Mats Carlsson).
*
* To quote Mats: Suppose you do a depth-first search of the graph.
* In that search, the root node will have a number of child subtrees
* T1, ..., Tn. By construction, if i<j then there is no edge from
* Ti to Tj. The necessary condition for Hamiltonianicity is that
* there be an edge from Ti+1 to Ti, for 0 < i < n.
*
* In addition, we do the following: if there is only a single edge
* from Ti+1 to Ti, then it must be mandatory and the variable must
* be assigned to that value.
*
* The same holds true for a back edge from T0 to the root node.
*
* Then, all edges that reach from Ti+k+1 to Ti can be pruned.
*
*/
{
// Start always at node start
int i = start;
// Counter for scc
int cnt = 0;
// Smallest preorder number of last subtree (initially, the root node)
int subtree_min = 0;
// Largest preorder number of last subtree (initially, the root node)
int subtree_max = 0;
// Number of back edges into last subtree or root
int back = 0;
start:
si[i].min = si[i].pre = si[i].low = cnt++;
si[i].v.init(o(x[i]));
do {
if (si[si[i].v.val()].pre < 0) {
next.push(i);
i=si[i].v.val();
goto start;
} else if ((subtree_min <= si[si[i].v.val()].pre) &&
(si[si[i].v.val()].pre <= subtree_max)) {
back++;
eq[n_eq].x = o(x[i]);
eq[n_eq].n = si[i].v.val();
} else if (si[si[i].v.val()].pre < subtree_min) {
nq[n_nq].x = o(x[i]);
nq[n_nq].n = si[i].v.val();
n_nq++;
}
cont:
if (si[si[i].v.val()].low < si[i].min)
si[i].min = si[si[i].v.val()].low;
++si[i].v;
} while (si[i].v());
if (si[i].min < si[i].low) {
si[i].low = si[i].min;
} else if (i != start) {
// If it is not the first node visited, there is more than one SCC
return ES_FAILED;
}
if (!next.empty()) {
i=next.pop();
if (i == start) {
// No back edge
if (back == 0)
return ES_FAILED;
// Exactly one back edge, make it mandatory (keep topmost entry)
if (back == 1)
n_eq++;
back = 0;
subtree_min = subtree_max+1;
subtree_max = cnt-1;
}
goto cont;
}
// Whether all nodes have been visited
if (cnt != n)
return ES_FAILED;
/*
* Whether there is more than one subtree
*
* This propagation rule is taken from: Kathryn Glenn Francis,
* Peter Stuckey, Explaining Circuit Propagation,
* Constraints (2014) 19:1-29.
*
*/
if (subtree_min > 1) {
for (Int::ViewValues<OView> v(o(x[start])); v(); ++v)
if (si[v.val()].pre < subtree_min) {
nq[n_nq].x = o(x[v.val()]);
nq[n_nq].n = v.val();
n_nq++;
}
}
ExecStatus es = ES_FIX;
// Assign all mandatory edges
while (n_eq-- > 0) {
ModEvent me = eq[n_eq].x.eq(home,eq[n_eq].n);
if (me_failed(me))
return ES_FAILED;
if (me_modified(me))
es = ES_NOFIX;
}
// Remove all edges that would require a non-simple cycle
while (n_nq-- > 0) {
ModEvent me = nq[n_nq].x.nq(home,nq[n_nq].n);
if (me_failed(me))
return ES_FAILED;
if (me_modified(me))
es = ES_NOFIX;
}
// Move start to different node for next run
start = o(x[start]).min();
return es;
}
}
template<class View, class Offset>
ExecStatus
Base<View,Offset>::path(Space& home) {
// Prunes that partial assigned paths are not completed to cycles
int n=x.size();
Region r;
// The path starting at assigned x[i] ends at x[end[j]] which is
// not assigned.
int* end = r.alloc<int>(n);
for (int i=0; i<n; i++)
end[i]=-1;
// A stack that records all indices i such that end[i] != -1
Support::StaticStack<int,Region> tell(r,n);
typedef typename Offset::ViewType OView;
for (int i=0; i<y.size(); i++) {
assert(!y[i].assigned());
// Non-assigned views serve as starting points for assigned paths
Int::ViewValues<OView> v(o(y[i]));
// Try all connected values
do {
int j0=v.val();
// Starting point for not yet followed assigned path found
if (x[j0].assigned() && (end[j0] < 0)) {
// Follow assigned path until non-assigned view:
// all assigned view on the paths can be skipped, as
// if x[i] is assigned to j, then x[j] will only have
// x[i] as predecessor due to propagating distinct.
int j = j0;
do {
j=o(x[j]).val();
} while (x[j].assigned());
// Now there cannot be a cycle from x[j] to x[v.val()]!
// However, the tell cannot be done here as j might be
// equal to i and might hence kill the iterator v!
end[j0]=j; tell.push(j0);
}
++v;
} while (v());
}
// Now do the tells based on the end information
while (!tell.empty()) {
int i = tell.pop();
assert(end[i] >= 0);
GECODE_ME_CHECK(o(x[end[i]]).nq(home,i));
}
return ES_NOFIX;
}
template<class View, class Offset>
forceinline size_t
Base<View,Offset>::dispose(Space& home) {
home.ignore(*this,AP_WEAKLY);
(void) NaryPropagator<View,Int::PC_INT_DOM>::dispose(home);
return sizeof(*this);
}
}}}
// STATISTICS: int-prop
Gecode::ActorLink::next
ActorLink * next(void) const
Definition core.hpp:3128
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::Int::Circuit::Base
Base-class for circuit propagator.
Definition circuit.hh:55
Gecode::Int::Circuit::Base::connected
ExecStatus connected(Space &home)
Check whether the view value graph is strongly connected.
Definition base.hpp:69
Gecode::Int::Circuit::Base::y
ViewArray< View > y
Array for performing value propagation for distinct.
Definition circuit.hh:61
Gecode::Int::Circuit::Base::o
Offset o
Offset transformation.
Definition circuit.hh:63
Gecode::Int::Circuit::Base::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition base.hpp:290
Gecode::Int::Circuit::Base::start
int start
Remember where to start the next time the propagator runs.
Definition circuit.hh:59
Gecode::Int::Circuit::Base::path
ExecStatus path(Space &home)
Ensure path property: prune edges that could give too small cycles.
Definition base.hpp:236
Gecode::Int::Circuit::Base::Base
Base(Space &home, Base &p)
Constructor for cloning p.
Gecode::Int::Circuit::NodeInfo
Information required for non-recursive checking for a single scc.
Definition base.hpp:54
Gecode::Int::Circuit::NodeInfo::v
Int::ViewValues< View > v
Definition base.hpp:57
Gecode::Int::Circuit::NodeInfo::pre
int pre
Definition base.hpp:56
Gecode::Int::Circuit::NodeInfo::low
int low
Definition base.hpp:56
Gecode::Int::Circuit::NodeInfo::min
int min
Definition base.hpp:56
Gecode::Int::Circuit::TellInfo
Information for performing a recorded tell.
Definition base.hpp:62
Gecode::Int::Circuit::TellInfo::x
View x
Definition base.hpp:64
Gecode::Int::Circuit::TellInfo::n
int n
Definition base.hpp:64
Gecode::Int::Offset
Converter with fixed offset.
Definition view.hpp:650
Gecode::Int::Offset::ViewType
OffsetView ViewType
The view type.
Definition view.hpp:653
Gecode::Int::Offset::update
void update(const Offset &o)
Update during cloning.
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::NaryPropagator
n-ary propagator
Definition pattern.hpp:142
Gecode::NaryPropagator::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:513
Gecode::NaryPropagator< View, Int::PC_INT_DOM >::x
ViewArray< View > x
Definition pattern.hpp:145
Gecode::NaryPropagator< View, Int::PC_INT_DOM >::NaryPropagator
NaryPropagator(Space &home, NaryPropagator &p)
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition static-stack.hpp:42
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition static-stack.hpp:116
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::AP_WEAKLY
@ AP_WEAKLY
Definition core.hpp:568
Gecode::Int::Circuit
Circuit propagators
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187