1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
8 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
10 */
13 /// \file
14 /// \brief Defines the VarSet class, which represents a set of random variables.
17 #ifndef __defined_libdai_varset_h
18 #define __defined_libdai_varset_h
21 #include <vector>
22 #include <map>
23 #include <ostream>
24 #include <dai/var.h>
25 #include <dai/util.h>
26 #include <dai/smallset.h>
29 namespace dai {
32 /// Represents a set of variables.
33 /** \note A VarSet is implemented using a SmallSet<Var> instead
34 * of the more natural std::set<Var> because of efficiency reasons.
35 * That is, internally, the variables in the set are sorted according
36 * to their labels: the set of variables \f$\{x_l\}_{l\in L}\f$ is
37 * represented as a vector \f$(x_{l(0)},x_{l(1)},\dots,x_{l(|L|-1)})\f$
38 * where \f$l(0) < l(1) < \dots < l(|L|-1)\f$
39 * and \f$L = \{l(0),l(1),\dots,l(|L|-1)\}\f$.
40 */
41 class VarSet : public SmallSet<Var> {
42 public:
43 /// \name Constructors and destructors
44 //@{
45 /// Default constructor (constructs an empty set)
46 VarSet() : SmallSet<Var>() {}
49 VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
51 /// Construct a VarSet with one element, \a v
52 VarSet( const Var &v ) : SmallSet<Var>(v) {}
54 /// Construct a VarSet with two elements, \a v1 and \a v2
55 VarSet( const Var &v1, const Var &v2 ) : SmallSet<Var>(v1,v2) {}
57 /// Construct a VarSet from the range between \a begin and \a end.
58 /** \tparam VarIterator Iterates over instances of type Var.
59 * \param begin Points to first Var to be added.
60 * \param end Points just beyond last Var to be added.
61 * \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
62 */
63 template <typename VarIterator>
64 VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
65 //@}
67 /// \name Queries
68 //@{
69 /// Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in \c *this.
70 /** The number of states of the Cartesian product of the variables in this VarSet
71 * is simply the product of the number of states of each variable in this VarSet.
72 * If \c *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
73 * where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
74 * number of possible values ("states") of variable \f$x_l\f$, the number of
75 * joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
76 */
77 size_t nrStates() const {
78 size_t states = 1;
79 for( VarSet::const_iterator n = begin(); n != end(); n++ )
80 states *= n->states();
81 return states;
82 }
84 /// Calculates the linear index in the Cartesian product of the variables in \c *this that corresponds to a particular joint assignment of the variables, specified by \a states.
85 /** \param states Specifies the states of some variables.
86 * \return The linear index in the Cartesian product of the variables in \c *this
87 * corresponding with the joint assignment specified by \a states, where variables
88 * for which no state is specified are assumed to be in state 0.
89 *
90 * The linear index is calculated as follows. The variables in \c *this are
91 * ordered according to their label (in ascending order); say \c *this corresponds with
92 * the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
93 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
94 * ("states") of variable \f$x_l\f$. The argument \a states corresponds
95 * with a mapping \a s that assigns to each variable \f$x_l\f$ a state \f$s(x_l) \in \{0,1,\dots,S_l-1\}\f$,
96 * where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a states. The linear index \f$S\f$ corresponding
97 * with \a states is now calculated by:
98 * \f{eqnarray*}
99 * S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
100 * &= & s(x_{l(0)}) + s(x_{l(1)}) S_{l(0)} + s(x_{l(2)}) S_{l(0)} S_{l(1)} + \dots + s(x_{l(n-1)}) S_{l(0)} \cdots S_{l(n-2)}.
101 * \f}
102 *
103 * \note If \c *this corresponds with \f$\{x_l\}_{l\in L}\f$, and \a states specifies a state
104 * for each variable \f$x_l\f$ for \f$l\in L\f$, calcState() induces a mapping
105 * \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
106 * maps a joint state to a linear index; this is the inverse of the mapping
107 * \f$\sigma^{-1}\f$ induced by calcStates().
108 */
109 size_t calcState( const std::map<Var, size_t> &states ) const {
110 size_t prod = 1;
111 size_t state = 0;
112 for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
113 std::map<Var, size_t>::const_iterator m = states.find( *n );
114 if( m != states.end() )
115 state += prod * m->second;
116 prod *= n->states();
117 }
118 return state;
119 }
121 /// Calculates the joint assignment of the variables in \c *this corresponding to the linear index \a linearState.
122 /** \param linearState should be smaller than nrStates().
123 * \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in \c *this to its state \f$s(x_l)\f$, as specified by \a linearState.
124 *
125 * The variables in \c *this are ordered according to their label (in ascending order); say \c *this corresponds with
126 * the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
127 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
128 * ("states") of variable \f$x_l\f$ with label \a l.
129 * The mapping \f$s\f$ returned by this function is defined as:
130 * \f{eqnarray*}
131 * s(x_{l(i)}) = \left\lfloor\frac{S \mbox { mod } \prod_{j=0}^{i} S_{l(j)}}{\prod_{j=0}^{i-1} S_{l(j)}}\right\rfloor \qquad \mbox{for all $i=0,\dots,n-1$}.
132 * \f}
133 * where \f$S\f$ denotes the value of \a linearState.
134 *
135 * \note If \c *this corresponds with \f$\{x_l\}_{l\in L}\f$, calcStates() induces a mapping
136 * \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l\f$ that
137 * maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
138 * induced by calcState().
139 */
140 std::map<Var, size_t> calcStates( size_t linearState ) const {
141 std::map<Var, size_t> states;
142 for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
143 states[*n] = linearState % n->states();
144 linearState /= n->states();
145 }
146 DAI_ASSERT( linearState == 0 );
147 return states;
148 }
149 //@}
151 /// \name Input and output
152 //@{
153 /// Writes a VarSet to an output stream
154 friend std::ostream& operator<<( std::ostream &os, const VarSet &vs ) {
155 os << "{";
156 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
157 os << (v != vs.begin() ? ", " : "") << *v;
158 os << "}";
159 return( os );
160 }
161 //@}
162 };
165 } // end of namespace dai
168 /** \example example_varset.cpp
169 * This example shows how to use the Var, VarSet and State classes. It also explains the concept of "states" for VarSets.
170 *
171 * \section Output
172 * \verbinclude examples/example_varset.out
173 *
174 * \section Source
175 */
178 #endif