Gecode::CpltSet Namespace Reference

Detailed Description

Complete representation of finite integer sets using ROBDD's.

The Gecode::CpltSet namespace contains all functionality required to program propagators and branchings for finite integer set variables, where the variables' domains are represented completely (without approximation) using reduced ordered binary decision diagrams (ROBDDs).

In addition, all propagators and branchings for these variables provided by Gecode are contained as nested namespaces.

Classes

class BddMgr

Manager for CpltSetVars. More...

class VariableOutOfRangeDomain

Exception: Variable created with values too large for domain More...

class GlbLubSpecNoSubset

Exception: Variable created with glb not a subset of lub More...

class VariableOutOfRangeCardinality

Exception: Variable created with wrong cardinality More...

class VariableFailedDomain

Exception: Variable created with failed domain More...

class VariableInvalidDomainSpec

Exception: Variable created with invalid domain specification More...

class ArgumentEmpty

Exception: No arguments available in argument array More...

class ArgumentSizeMismatch

Exception: Arguments are of different size More...

class InvalidRelation

Exception: Invalid relation passed as argument More...

class InvalidProjector

Exception: Invalid projector passed as argument More...

class UnknownBranching

Exception: Unknown value or variable selection passed as argument More...

class NaryCpltSetPropagator

Nary propagator for CpltSet variables. More...

class BinaryCpltSetPropagator

Binary propagator for CpltSet variables. More...

class UnaryCpltSetPropagator

Unary propagator for CpltSet variables. More...

class NaryOneCpltSetPropagator

Propagator for CpltSet variables with n+1 arguments. More...

class NaryTwoCpltSetPropagator

Propagator for CpltSet variables with n+2 arguments. More...

class BinRelDisj

Binary Rel Disjoint Propagator. More...

class Singleton

Singleton channel propagator from IntVar to CpltSetVar. More...

class GlbValues< CpltSetVarImp * >

Iterator for the values in the greatest lower bound of a bdd variable implementation. More...

class LubValues< CpltSetVarImp * >

Iterator for the values in the least upper bound of a bdd variable implementation. More...

class UnknownValues< CpltSetVarImp * >

Iterator for the unknown values of a bdd variable implementation. More...

class GlbValues

Iterate the values in the greatest lower bound of a CpltSetvariable. More...

class LubValues

Iterate the values in the least upper bound of a bdd set variable. More...

class UnknownValues

Iterate the values lub-glb of a bdd set variable. More...

class CpltSetVarImp

Finite integer set variable implementation using a complete domain representation. More...

class BddIterator

Iterator for level-wise iteration over a given bdd. More...

class DomBddIterator

Iterator for level-wise iteration of a variable domain. More...

class GlbValues< CpltSetView >

Iterator for the values in the greatest lower bound of a CpltSetView. More...

class LubValues< CpltSetView >

Value iterator for least upper bound of singleton set view More...

class UnknownValues< CpltSetView >

Iterator for the unknown values of a CpltSetView. More...

class CpltSetView

CpltSet view for CpltSet variables More...

class CpltSetVarImpConf

Dummy configuration for CpltSet-variable implementations. More...

Namespaces

namespace Branch

CpltSet branchings

namespace AtMost

Propagators for intersection constraints with cardinality restrictions.

namespace Distinct

Propagators for distinctness constraints.

namespace Partition

Propagators for partition constraints.

namespace RangeRoots

Propagators for range/roots constraints.

namespace Rel

Propagators for relation constraints.

namespace Select

Propagators for selection constraints.

Enumerations

enum NodeStatus {
INIT = -1, FIX_GLB = 1, FIX_NOT_LUB = 0, FIX_UNKNOWN = 2,
UNDET = 5
}

Functions

void setVariableOrderFromArray (Space *home, const CpltSetVarArray &x)

Ordering all declared bdd variables $x_0, \dots, x_{n-1}$ such that $\forall i\in \{0, \dots, n - 1\}: x_{0_{1}} \prec x_{{n-1}_{1}}, \dots, x_{0_{k-1}} \prec x_{{n-1}_{k-1}}$ .

void conv_hull (bdd &robdd, bdd &hull)

Returns a bdd representing the convex hull of robdd.

bdd bdd_vars (bdd &domain)

Returns a bdd representing all variables of domain.

bdd cardeq (int offset, int c, int n, int r)

Build the ROBDD for $ |x|=c$ .

bdd cardlqgq (int offset, int cl, int cr, int n, int r)

Build the ROBDD for $cl \leq |x| \leq cr$ .

bdd cardcheck (int xtab, int offset, int cl, int cr)

Build the ROBDD for $cl \leq |x| \leq cr$ .

bdd lexlt (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)

bdd lexlq (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)

bdd lexltrev (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)

bdd lexlqrev (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)

void extcache_mark (Support::DynamicArray< bdd > &nodes, int n, int &l, int &r, int &markref)

void extcache_unmark (Support::DynamicArray< bdd > &nodes, int n, int &l, int &r, int &markref)

void extcardbounds (int &markref, bdd &, int &n, int &l, int &r, bool &singleton, int &_level, Support::DynamicArray< bdd > &nodes, int &curmin, int &curmax)

void getcardbounds (bdd &c, int &curmin, int &curmax)

void testConsistency (const IntSet &glb, const IntSet &lub, const int cardMin, const int cardMax, const char *location)

Check whether range specifications for initialization are consistent.

template<class View>

void variableorder (ViewArray< View > &x)

template<class View, class View1>

void variableorder (ViewArray< View > &x, ViewArray< View1 > &y)

template<class I, class View0, class View1>

bdd extcardeq (Gecode::Iter::Ranges::ValCache< I > &inter, View0 &x, View1 &y, unsigned int c, int n, int)

Build the ROBDD for $ |x|=c$ .

template<class I, class View0, class View1>

bdd extcardlqgq (Gecode::Iter::Ranges::ValCache< I > &inter, View0 &x, View1 &y, unsigned int cl, unsigned int cr, int n, int r)

Build the ROBDD for $cl \leq |x| \leq cr$ .

template<class View0, class View1>

bdd extcardcheck (View0 &x, View1 &y, unsigned int cl, unsigned int cr)

Build the ROBDD for $cl \leq |x \cap y| \leq cr$ .

template<class I>

bdd cardConst (int, int xoff, int xmin, int cl, int cr, I &is)

GECODE_CPLTSET_EXPORT void extcache_mark (SharedArray< bdd > &nodes, int n, int &l, int &r, int &markref)

GECODE_CPLTSET_EXPORT void extcache_unmark (SharedArray< bdd > &nodes, int n, int &l, int &r, int &markref)

GECODE_CPLTSET_EXPORT void extcardbounds (int &markref, bdd &c, int &n, int &l, int &r, bool &singleton, int &_level, SharedArray< bdd > &nodes, int &curmin, int &curmax, Gecode::IntSet &out)

template<class View>

void quantify (bdd &p, View &x)

bool printBddDom (std::ostream &os, int off, int min, int width, bool first, char *profile, bdd &r)

Print the domain represented by r to os.

Variables

BddMgr manager

GECODE_CPLTSET_EXPORT
VarDisposer< CpltSetVarImp > vtd

Enumeration Type Documentation

enum Gecode::CpltSet::NodeStatus

Enumerator:

INIT
FIX_GLB
FIX_NOT_LUB
FIX_UNKNOWN
UNDET

Definition at line 42 of file var-imp.icc.

Function Documentation

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::setVariableOrderFromArray	(	Space *	home,
		const CpltSetVarArray &	x
	)

Ordering all declared bdd variables $x_0, \dots, x_{n-1}$ such that $\forall i\in \{0, \dots, n - 1\}: x_{0_{1}} \prec x_{{n-1}_{1}}, \dots, x_{0_{k-1}} \prec x_{{n-1}_{k-1}}$ .

Definition at line 44 of file array.cc.

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::conv_hull	(	bdd &	robdd,
		bdd &	hull
	)

Returns a bdd representing the convex hull of robdd.

Definition at line 43 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::bdd_vars ( bdd & robdd )

Returns a bdd representing all variables of domain.

Definition at line 60 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::cardeq	(	int	offset,
		int	c,
		int	n,
		int	r
	)

Build the ROBDD for $ |x|=c$ .

Definition at line 77 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::cardlqgq	(	int	offset,
		int	cl,
		int	cr,
		int	n,
		int	r
	)

Build the ROBDD for $cl \leq |x| \leq cr$ .

Definition at line 113 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::cardcheck	(	int	xtab,
		int	offset,
		int	cl,
		int	cr
	)

Build the ROBDD for $cl \leq |x| \leq cr$ .

Definition at line 210 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::lexlt	(	unsigned int &	xoff,
		unsigned int &	yoff,
		unsigned int &	range,
		int	n
	)

Definition at line 251 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::lexlq	(	unsigned int &	xoff,
		unsigned int &	yoff,
		unsigned int &	range,
		int	n
	)

Definition at line 262 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::lexltrev	(	unsigned int &	xoff,
		unsigned int &	yoff,
		unsigned int &	range,
		int	n
	)

Definition at line 274 of file support.cc.

GECODE_CPLTSET_EXPORT bdd Gecode::CpltSet::lexlqrev	(	unsigned int &	xoff,
		unsigned int &	yoff,
		unsigned int &	range,
		int	n
	)

Definition at line 285 of file support.cc.

void Gecode::CpltSet::extcache_mark	(	Support::DynamicArray< bdd > &	nodes,
		int	n,
		int &	l,
		int &	r,
		int &	markref
	)

Definition at line 298 of file support.cc.

void Gecode::CpltSet::extcache_unmark	(	Support::DynamicArray< bdd > &	nodes,
		int	n,
		int &	l,
		int &	r,
		int &	markref
	)

Definition at line 322 of file support.cc.

void Gecode::CpltSet::extcardbounds	(	int &	markref,
		bdd &	,
		int &	n,
		int &	l,
		int &	r,
		bool &	singleton,
		int &	_level,
		Support::DynamicArray< bdd > &	nodes,
		int &	curmin,
		int &	curmax
	)

Definition at line 345 of file support.cc.

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::getcardbounds	(	bdd &	c,
		int &	curmin,
		int &	curmax
	)

Definition at line 628 of file support.cc.

void Gecode::CpltSet::testConsistency	(	const IntSet &	glb,
		const IntSet &	lub,
		const int	cardMin,
		const int	cardMax,
		const char *	location
	)			`[inline]`

Check whether range specifications for initialization are consistent.

Definition at line 42 of file support.icc.

template<class View>

void Gecode::CpltSet::variableorder ( ViewArray< View > & x ) [inline]

Definition at line 102 of file support.icc.

template<class View, class View1>

void Gecode::CpltSet::variableorder	(	ViewArray< View > &	x,
		ViewArray< View1 > &	y
	)			`[inline]`

Definition at line 149 of file support.icc.

template<class I, class View0, class View1>

bdd Gecode::CpltSet::extcardeq	(	Gecode::Iter::Ranges::ValCache< I > &	inter,
		View0 &	x,
		View1 &	y,
		unsigned int	c,
		int	n,
		int
	)			`[inline]`

Build the ROBDD for $ |x|=c$ .

Definition at line 235 of file support.icc.

template<class I, class View0, class View1>

bdd Gecode::CpltSet::extcardlqgq	(	Gecode::Iter::Ranges::ValCache< I > &	inter,
		View0 &	x,
		View1 &	y,
		unsigned int	cl,
		unsigned int	cr,
		int	n,
		int	r
	)			`[inline]`

Build the ROBDD for $cl \leq |x| \leq cr$ .

Definition at line 287 of file support.icc.

template<class View0, class View1>

bdd Gecode::CpltSet::extcardcheck	(	View0 &	x,
		View1 &	y,
		unsigned int	cl,
		unsigned int	cr
	)			`[inline]`

Build the ROBDD for $cl \leq |x \cap y| \leq cr$ .

Definition at line 426 of file support.icc.

template<class I>

bdd Gecode::CpltSet::cardConst	(	int	,
		int	xoff,
		int	xmin,
		int	cl,
		int	cr,
		I &	is
	)			`[inline]`

Definition at line 511 of file support.icc.

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::extcache_mark	(	SharedArray< bdd > &	nodes,
		int	n,
		int &	l,
		int &	r,
		int &	markref
	)

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::extcache_unmark	(	SharedArray< bdd > &	nodes,
		int	n,
		int &	l,
		int &	r,
		int &	markref
	)

GECODE_CPLTSET_EXPORT void Gecode::CpltSet::extcardbounds	(	int &	markref,
		bdd &	c,
		int &	n,
		int &	l,
		int &	r,
		bool &	singleton,
		int &	_level,
		SharedArray< bdd > &	nodes,
		int &	curmin,
		int &	curmax,
		Gecode::IntSet &	out
	)

template<class View>

void Gecode::CpltSet::quantify	(	bdd &	p,
		View &	x
	)			`[inline]`

Definition at line 686 of file support.icc.

bool Gecode::CpltSet::printBddDom	(	std::ostream &	os,
		int	off,
		int	min,
		int	width,
		bool	first,
		char *	profile,
		bdd &	r
	)

Print the domain represented by r to os.

Definition at line 67 of file print.cc.

Variable Documentation

GECODE_CPLTSET_EXPORT BddMgr Gecode::CpltSet::manager

Definition at line 55 of file bddmanager.cc.

GECODE_CPLTSET_EXPORT VarDisposer<CpltSetVarImp> Gecode::CpltSet::vtd

Definition at line 922 of file cpltset.cc.


Classes
class	BddMgr
	Manager for CpltSetVars. More...
class	VariableOutOfRangeDomain
	Exception: Variable created with values too large for domain More...
class	GlbLubSpecNoSubset
	Exception: Variable created with glb not a subset of lub More...
class	VariableOutOfRangeCardinality
	Exception: Variable created with wrong cardinality More...
class	VariableFailedDomain
	Exception: Variable created with failed domain More...
class	VariableInvalidDomainSpec
	Exception: Variable created with invalid domain specification More...
class	ArgumentEmpty
	Exception: No arguments available in argument array More...
class	ArgumentSizeMismatch
	Exception: Arguments are of different size More...
class	InvalidRelation
	Exception: Invalid relation passed as argument More...
class	InvalidProjector
	Exception: Invalid projector passed as argument More...
class	UnknownBranching
	Exception: Unknown value or variable selection passed as argument More...
class	NaryCpltSetPropagator
	Nary propagator for CpltSet variables. More...
class	BinaryCpltSetPropagator
	Binary propagator for CpltSet variables. More...
class	UnaryCpltSetPropagator
	Unary propagator for CpltSet variables. More...
class	NaryOneCpltSetPropagator
	Propagator for CpltSet variables with n+1 arguments. More...
class	NaryTwoCpltSetPropagator
	Propagator for CpltSet variables with n+2 arguments. More...
class	BinRelDisj
	Binary Rel Disjoint Propagator. More...
class	Singleton
	Singleton channel propagator from IntVar to CpltSetVar. More...
class	GlbValues< CpltSetVarImp * >
	Iterator for the values in the greatest lower bound of a bdd variable implementation. More...
class	LubValues< CpltSetVarImp * >
	Iterator for the values in the least upper bound of a bdd variable implementation. More...
class	UnknownValues< CpltSetVarImp * >
	Iterator for the unknown values of a bdd variable implementation. More...
class	GlbValues
	Iterate the values in the greatest lower bound of a CpltSetvariable. More...
class	LubValues
	Iterate the values in the least upper bound of a bdd set variable. More...
class	UnknownValues
	Iterate the values lub-glb of a bdd set variable. More...
class	CpltSetVarImp
	Finite integer set variable implementation using a complete domain representation. More...
class	BddIterator
	Iterator for level-wise iteration over a given bdd. More...
class	DomBddIterator
	Iterator for level-wise iteration of a variable domain. More...
class	GlbValues< CpltSetView >
	Iterator for the values in the greatest lower bound of a CpltSetView. More...
class	LubValues< CpltSetView >
	Value iterator for least upper bound of singleton set view More...
class	UnknownValues< CpltSetView >
	Iterator for the unknown values of a CpltSetView. More...
class	CpltSetView
	CpltSet view for CpltSet variables More...
class	CpltSetVarImpConf
	Dummy configuration for CpltSet-variable implementations. More...
Namespaces
namespace	Branch
	CpltSet branchings
namespace	AtMost
	Propagators for intersection constraints with cardinality restrictions.
namespace	Distinct
	Propagators for distinctness constraints.
namespace	Partition
	Propagators for partition constraints.
namespace	RangeRoots
	Propagators for range/roots constraints.
namespace	Rel
	Propagators for relation constraints.
namespace	Select
	Propagators for selection constraints.
Enumerations
enum	NodeStatus { INIT = -1, FIX_GLB = 1, FIX_NOT_LUB = 0, FIX_UNKNOWN = 2, UNDET = 5 }
Functions
void	setVariableOrderFromArray (Space *home, const CpltSetVarArray &x)
	Ordering all declared bdd variables $x_0, \dots, x_{n-1}$ such that $\forall i\in \{0, \dots, n - 1\}: x_{0_{1}} \prec x_{{n-1}_{1}}, \dots, x_{0_{k-1}} \prec x_{{n-1}_{k-1}}$ .
void	conv_hull (bdd &robdd, bdd &hull)
	Returns a bdd representing the convex hull of robdd.
bdd	bdd_vars (bdd &domain)
	Returns a bdd representing all variables of domain.
bdd	cardeq (int offset, int c, int n, int r)
	Build the ROBDD for .
bdd	cardlqgq (int offset, int cl, int cr, int n, int r)
	Build the ROBDD for $cl \leq \|x\| \leq cr$ .
bdd	cardcheck (int xtab, int offset, int cl, int cr)
	Build the ROBDD for $cl \leq \|x\| \leq cr$ .
bdd	lexlt (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)
bdd	lexlq (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)
bdd	lexltrev (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)
bdd	lexlqrev (unsigned int &xoff, unsigned int &yoff, unsigned int &range, int n)
void	extcache_mark (Support::DynamicArray< bdd > &nodes, int n, int &l, int &r, int &markref)
void	extcache_unmark (Support::DynamicArray< bdd > &nodes, int n, int &l, int &r, int &markref)
void	extcardbounds (int &markref, bdd &, int &n, int &l, int &r, bool &singleton, int &_level, Support::DynamicArray< bdd > &nodes, int &curmin, int &curmax)
void	getcardbounds (bdd &c, int &curmin, int &curmax)
void	testConsistency (const IntSet &glb, const IntSet &lub, const int cardMin, const int cardMax, const char *location)
	Check whether range specifications for initialization are consistent.
template<class View>
void	variableorder (ViewArray< View > &x)
template<class View, class View1>
void	variableorder (ViewArray< View > &x, ViewArray< View1 > &y)
template<class I, class View0, class View1>
bdd	extcardeq (Gecode::Iter::Ranges::ValCache< I > &inter, View0 &x, View1 &y, unsigned int c, int n, int)
	Build the ROBDD for .
template<class I, class View0, class View1>
bdd	extcardlqgq (Gecode::Iter::Ranges::ValCache< I > &inter, View0 &x, View1 &y, unsigned int cl, unsigned int cr, int n, int r)
	Build the ROBDD for $cl \leq \|x\| \leq cr$ .
template<class View0, class View1>
bdd	extcardcheck (View0 &x, View1 &y, unsigned int cl, unsigned int cr)
	Build the ROBDD for $cl \leq \|x \cap y\| \leq cr$ .
template<class I>
bdd	cardConst (int, int xoff, int xmin, int cl, int cr, I &is)
GECODE_CPLTSET_EXPORT void	extcache_mark (SharedArray< bdd > &nodes, int n, int &l, int &r, int &markref)
GECODE_CPLTSET_EXPORT void	extcache_unmark (SharedArray< bdd > &nodes, int n, int &l, int &r, int &markref)
GECODE_CPLTSET_EXPORT void	extcardbounds (int &markref, bdd &c, int &n, int &l, int &r, bool &singleton, int &_level, SharedArray< bdd > &nodes, int &curmin, int &curmax, Gecode::IntSet &out)
template<class View>
void	quantify (bdd &p, View &x)
bool	printBddDom (std::ostream &os, int off, int min, int width, bool first, char *profile, bdd &r)
	Print the domain represented by r to os.
Variables
BddMgr	manager
GECODE_CPLTSET_EXPORT VarDisposer< CpltSetVarImp >	vtd