c8c3629502fcc97358ca3b3316f191747a75fddf
[libdai.git] / include / dai / varset.h
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
6 Radboud University Nijmegen, The Netherlands
7
8 This file is part of libDAI.
9
10 libDAI is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14
15 libDAI is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with libDAI; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25
26 /// \file
27 /// \brief Defines VarSet class
28
29
30 #ifndef __defined_libdai_varset_h
31 #define __defined_libdai_varset_h
32
33
34 #include <vector>
35 #include <map>
36 #include <cassert>
37 #include <ostream>
38 #include <dai/var.h>
39 #include <dai/util.h>
40 #include <dai/smallset.h>
41
42
43 namespace dai {
44
45
46 /// Represents a set of variables.
47 /** The variables in the set are sorted according to their labels.
48 * \note A VarSet is implemented using a SmallSet<Var> instead
49 * of the more natural std::set<Var> because of efficiency reasons.
50 */
51 class VarSet : public SmallSet<Var> {
52 public:
53 /// Default constructor
54 VarSet() : SmallSet<Var>() {}
55
56 /// Copy constructor
57 VarSet( const VarSet &x ) : SmallSet<Var>(x) {}
58
59 /// Assignment operator
60 VarSet& operator=( const VarSet &x ) {
61 if( this != &x ) {
62 SmallSet<Var>::operator=( x );
63 }
64 return *this;
65 }
66
67 /// Construct from SmallSet<Var>
68 VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
69
70 /// Calculates the number of states of this VarSet.
71 /** The number of states of the Cartesian product of the variables in this VarSet
72 * is simply the product of the number of states of each variable in this VarSet.
73 * If *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
74 * where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
75 * number of possible values ("states") of variable \f$x_l\f$, the number of
76 * joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
77 */
78 size_t nrStates() {
79 size_t states = 1;
80 for( VarSet::const_iterator n = begin(); n != end(); n++ )
81 states *= n->states();
82 return states;
83 }
84
85 /// Construct a VarSet with one element
86 VarSet( const Var &n ) : SmallSet<Var>(n) {}
87
88 /// Construct a VarSet with two elements
89 VarSet( const Var &n1, const Var &n2 ) : SmallSet<Var>(n1,n2) {}
90
91 /// Construct a VarSet from a range.
92 /** \tparam VarIterator Iterates over instances of type Var.
93 * \param begin Points to first Var to be added.
94 * \param end Points just beyond last Var to be added.
95 * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
96 */
97 template <typename VarIterator>
98 VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
99
100 /// Calculates the linear index in the Cartesian product of the variables in *this, which corresponds to a particular joint assignment of the variables specified by \a states.
101 /** \param states Specifies the states of some variables.
102 * \return The linear index in the Cartesian product of the variables in *this
103 * corresponding with the joint assignment specified by \a states, where it is
104 * assumed that \a states[\a m]==0 for all \a m in *this which are not in \a states.
105 *
106 * The linear index is calculated as follows. The variables in *this are
107 * ordered according to their label (in ascending order); say *this corresponds with
108 * 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$,
109 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
110 * ("states") of variable \f$x_l\f$. The argument \a states corresponds
111 * 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$,
112 * where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a states. The linear index \a S corresponding
113 * with \a states is now calculated as:
114 * \f{eqnarray*}
115 * S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
116 * &= & 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)}.
117 * \f}
118 *
119 * \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, and \a states specifies a state
120 * for each variable \f$x_l\f$ for \f$l\in L\f$, calcState(const std::map<Var,size_t> &) induces a mapping
121 * \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
122 * maps a joint state to a linear index; this is the inverse of the mapping
123 * \f$\sigma^{-1}\f$ induced by calcStates(size_t).
124 */
125 size_t calcState( const std::map<Var, size_t> &states ) {
126 size_t prod = 1;
127 size_t state = 0;
128 for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
129 std::map<Var, size_t>::const_iterator m = states.find( *n );
130 if( m != states.end() )
131 state += prod * m->second;
132 prod *= n->states();
133 }
134 return state;
135 }
136
137 /// Calculates the joint assignment of the variables in *this corresponding to the linear index \a linearState.
138 /** \param linearState should be smaller than nrStates().
139 * \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in *this to its state \f$s(x_l)\f$, as specified by \a linearState.
140 *
141 * The variables in *this are ordered according to their label (in ascending order); say *this corresponds with
142 * 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$,
143 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
144 * ("states") of variable \f$x_l\f$ with label \a l.
145 * The mapping \a s returned by this function is defined as:
146 * \f{eqnarray*}
147 * s(x_{l(i)}) = \left[\frac{S \mbox { mod } \prod_{j=0}^{i} S_{l(j)}}{\prod_{j=0}^{i-1} S_{l(j)}}\right] \qquad \mbox{for all $i=0,\dots,n-1$}.
148 * \f}
149 * where \f$S\f$ denotes the value of \a linearState.
150 *
151 * \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, calcStates(size_t) induces a mapping
152 * \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l \to \f$ that
153 * maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
154 * induced by calcState(const std::map<Var,size_t> &).
155 */
156 std::map<Var, size_t> calcStates( size_t linearState ) {
157 std::map<Var, size_t> states;
158 for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
159 states[*n] = linearState % n->states();
160 linearState /= n->states();
161 }
162 assert( linearState == 0 );
163 return states;
164 }
165
166 /// Writes a VarSet to an output stream
167 friend std::ostream& operator<< (std::ostream &os, const VarSet& ns) {
168 os << "{";
169 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
170 os << (n != ns.begin() ? "," : "") << *n;
171 os << "}";
172 return( os );
173 }
174 };
175
176
177 } // end of namespace dai
178
179
180 /** \example example_varset.cpp
181 * This example shows how to use the Var and VarSet classes. It also explains the concept of "states" for VarSets.
182 *
183 * \section Output
184 * \verbinclude examples/example_varset.out
185 *
186 * \section Source
187 */
188
189
190 #endif