Represents a set of variables. More...

#include <dai/varset.h>

Inheritance diagram for dai::VarSet:

Public Member Functions
Constructors and destructors
	VarSet ()
	Default constructor (constructs an empty set) More...

	VarSet (const SmallSet< Var > &x)
	Construct from SmallSet<Var> x. More...

	VarSet (const Var &v)
	Construct a VarSet with one element, v. More...

	VarSet (const Var &v1, const Var &v2)
	Construct a VarSet with two elements, v1 and v2. More...

template<typename VarIterator >
	VarSet (VarIterator begin, VarIterator end, size_t sizeHint=0)
	Construct a VarSet from the range between begin and end. More...

Queries
BigInt	nrStates () const
	Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in `*this`. More...

Public Member Functions inherited from dai::SmallSet< Var >
	SmallSet ()
	Default constructor (constructs an empty set) More...

	SmallSet (const Var &t)
	Construct a set consisting of one element. More...

	SmallSet (const Var &t1, const Var &t2)
	Construct a set consisting of two elements. More...

	SmallSet (TIterator begin, TIterator end, size_t sizeHint)
	Construct a SmallSet from a range of elements. More...

SmallSet &	insert (const Var &t)
	Inserts t into `*this`. More...

SmallSet &	erase (const Var &t)
	Erases t from `*this`. More...

SmallSet	operator/ (const SmallSet &x) const
	Set-minus operator: returns all elements in `*this`, except those in x. More...

SmallSet	operator\| (const SmallSet &x) const
	Set-union operator: returns all elements in `*this`, plus those in x. More...

SmallSet	operator& (const SmallSet &x) const
	Set-intersection operator: returns all elements in `*this` that are also contained in x. More...

SmallSet &	operator/= (const SmallSet &x)
	Erases from `*this` all elements in x. More...

SmallSet &	operator/= (const Var &t)
	Erases one element. More...

SmallSet &	operator\|= (const SmallSet &x)
	Adds to `*this` all elements in x. More...

SmallSet &	operator\|= (const Var &t)
	Adds one element. More...

SmallSet &	operator&= (const SmallSet &x)
	Erases from `*this` all elements not in x. More...

bool	operator<< (const SmallSet &x) const
	Returns `true` if `*this` is a subset of x. More...

bool	operator>> (const SmallSet &x) const
	Returns `true` if x is a subset of `*this`. More...

bool	intersects (const SmallSet &x) const
	Returns `true` if `*this` and x have elements in common. More...

bool	contains (const Var &t) const
	Returns `true` if `*this` contains the element t. More...

std::vector< Var >::size_type	size () const
	Returns number of elements. More...

bool	empty () const
	Returns whether `*this` is empty. More...

std::vector< Var > &	elements ()
	Returns reference to the elements. More...

const std::vector< Var > &	elements () const
	Returns constant reference to the elements. More...

iterator	begin ()
	Returns iterator that points to the first element. More...

const_iterator	begin () const
	Returns constant iterator that points to the first element. More...

iterator	end ()
	Returns iterator that points beyond the last element. More...

const_iterator	end () const
	Returns constant iterator that points beyond the last element. More...

reverse_iterator	rbegin ()
	Returns reverse iterator that points to the last element. More...

const_reverse_iterator	rbegin () const
	Returns constant reverse iterator that points to the last element. More...

reverse_iterator	rend ()
	Returns reverse iterator that points beyond the first element. More...

const_reverse_iterator	rend () const
	Returns constant reverse iterator that points beyond the first element. More...

Var &	front ()
	Returns reference to first element. More...

const Var &	front () const
	Returns constant reference to first element. More...

Var &	back ()
	Returns reference to last element. More...

const Var &	back () const
	Returns constant reference to last element. More...

std::string	toString () const
	Formats a SmallSet as a string. More...

Input and output
std::string	toString () const
	Formats a VarSet as a string. More...

std::ostream &	operator<< (std::ostream &os, const VarSet &vs)
	Writes a VarSet to an output stream. More...

Additional Inherited Members
Public Types inherited from dai::SmallSet< Var >
typedef std::vector< Var >::const_iterator	const_iterator
	Constant iterator over the elements. More...

typedef std::vector< Var >::iterator	iterator
	Iterator over the elements. More...

typedef std::vector< Var >::const_reverse_iterator	const_reverse_iterator
	Constant reverse iterator over the elements. More...

typedef std::vector< Var >::reverse_iterator	reverse_iterator
	Reverse iterator over the elements. More...

Detailed Description

Represents a set of variables.

Note: A VarSet is implemented using a SmallSet<Var> instead of the more natural std::set<Var> because of efficiency reasons. That is, internally, the variables in the set are sorted ascendingly according to their labels.

Examples:: example_permute.cpp, example_sprinkler.cpp, example_varset.cpp, and uai2010-aie-solver.cpp.

Constructor & Destructor Documentation

dai::VarSet::VarSet ( )

inline

Default constructor (constructs an empty set)

dai::VarSet::VarSet ( const SmallSet< Var > & x )

inline

Construct from SmallSet<Var> x.

dai::VarSet::VarSet ( const Var & v )

inline

Construct a VarSet with one element, v.

dai::VarSet::VarSet	(	const Var &	v1,
		const Var &	v2
	)

inline

Construct a VarSet with two elements, v1 and v2.

template<typename VarIterator >

dai::VarSet::VarSet	(	VarIterator	begin,
		VarIterator	end,
		size_t	sizeHint = `0`
	)

inline

Construct a VarSet from the range between begin and end.

Template Parameters

VarIterator Iterates over instances of type Var.

Parameters

begin	Points to first Var to be added.
end	Points just beyond last Var to be added.
sizeHint	For efficiency, the number of elements can be speficied by sizeHint.

Member Function Documentation

BigInt dai::VarSet::nrStates ( ) const

inline

Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in *this.

The number of states of the Cartesian product of the variables in this VarSet is simply the product of the number of states of each variable in this VarSet. If *this corresponds with the set $\{x_l\}_{l\in L}$ , where variable $x_l$ has label $l$ , and denoting by $S_l$ the number of possible values ("states") of variable $x_l$ , the number of joint configurations of the variables in $\{x_l\}_{l\in L}$ is given by $\prod_{l\in L} S_l$ .