d32b1e4f1a6ccc2de9870e0e718d1f4d2732ccd2
[libdai.git] / include / dai / varset.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 /// \file
10 /// \brief Defines the VarSet class, which represents a set of random variables.
11
12
13 #ifndef __defined_libdai_varset_h
14 #define __defined_libdai_varset_h
15
16
17 #include <vector>
18 #include <map>
19 #include <ostream>
20 #include <dai/var.h>
21 #include <dai/util.h>
22 #include <dai/smallset.h>
23
24
25 namespace dai {
26
27
28 // Predefine for definitions of calcLinearState() and calcState()
29 class VarSet;
30
31
32 /// Calculates the linear index in the Cartesian product of the variables in \a vs that corresponds to a particular joint assignment of the variables, specified by \a state.
33 /** \param vs Set of variables for which the linear state should be calculated;
34 * \param state Specifies the states of some variables.
35 * \return The linear index in the Cartesian product of the variables in \a vs
36 * corresponding with the joint assignment specified by \a state, where variables
37 * for which no state is specified are assumed to be in state 0.
38 *
39 * The linear index is calculated as follows. The variables in \a vs are
40 * ordered according to their label (in ascending order); say \a vs corresponds with
41 * 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$,
42 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
43 * ("states") of variable \f$x_l\f$. The argument \a state corresponds
44 * 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$,
45 * where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a state. The linear index \f$S\f$ corresponding
46 * with \a state is now calculated by:
47 * \f{eqnarray*}
48 * S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
49 * &= & 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)}.
50 * \f}
51 *
52 * \note If \a vs corresponds with \f$\{x_l\}_{l\in L}\f$, and \a state specifies a state
53 * for each variable \f$x_l\f$ for \f$l\in L\f$, calcLinearState() induces a mapping
54 * \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
55 * maps a joint state to a linear index; this is the inverse of the mapping
56 * \f$\sigma^{-1}\f$ induced by calcState().
57 *
58 * \see calcState()
59 */
60 size_t calcLinearState( const VarSet &vs, const std::map<Var, size_t> &state );
61
62
63 /// Calculates the joint assignment of the variables in \a vs corresponding to the linear index \a linearState.
64 /** \param vs Set of variables to which \a linearState refers
65 * \param linearState should be smaller than vs.nrStates().
66 * \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in \a vs to its state \f$s(x_l)\f$, as specified by \a linearState.
67 *
68 * The variables in \a vs are ordered according to their label (in ascending order); say \a vs corresponds with
69 * 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$,
70 * where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
71 * ("states") of variable \f$x_l\f$ with label \a l.
72 * The mapping \f$s\f$ returned by this function is defined as:
73 * \f{eqnarray*}
74 * 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$}.
75 * \f}
76 * where \f$S\f$ denotes the value of \a linearState.
77 *
78 * \note If \a vs corresponds with \f$\{x_l\}_{l\in L}\f$, calcState() induces a mapping
79 * \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l\f$ that
80 * maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
81 * induced by calcLinearState().
82 *
83 * \see calcLinearState()
84 */
85 std::map<Var, size_t> calcState( const VarSet &vs, size_t linearState );
86
87
88 /// Represents a set of variables.
89 /** \note A VarSet is implemented using a SmallSet<Var> instead
90 * of the more natural std::set<Var> because of efficiency reasons.
91 * That is, internally, the variables in the set are sorted ascendingly
92 * according to their labels.
93 */
94 class VarSet : public SmallSet<Var> {
95 public:
96 /// \name Constructors and destructors
97 //@{
98 /// Default constructor (constructs an empty set)
99 VarSet() : SmallSet<Var>() {}
100
101 /// Construct from \link SmallSet \endlink<\link Var \endlink> \a x
102 VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
103
104 /// Construct a VarSet with one element, \a v
105 VarSet( const Var &v ) : SmallSet<Var>(v) {}
106
107 /// Construct a VarSet with two elements, \a v1 and \a v2
108 VarSet( const Var &v1, const Var &v2 ) : SmallSet<Var>(v1,v2) {}
109
110 /// Construct a VarSet from the range between \a begin and \a end.
111 /** \tparam VarIterator Iterates over instances of type Var.
112 * \param begin Points to first Var to be added.
113 * \param end Points just beyond last Var to be added.
114 * \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
115 */
116 template <typename VarIterator>
117 VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
118 //@}
119
120 /// \name Queries
121 //@{
122 /// Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in \c *this.
123 /** The number of states of the Cartesian product of the variables in this VarSet
124 * is simply the product of the number of states of each variable in this VarSet.
125 * If \c *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
126 * where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
127 * number of possible values ("states") of variable \f$x_l\f$, the number of
128 * joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
129 */
130 BigInt nrStates() const {
131 BigInt states = 1;
132 for( VarSet::const_iterator n = begin(); n != end(); n++ )
133 states *= (BigInt)n->states();
134 return states;
135 }
136 //@}
137
138 /// \name Input and output
139 //@{
140 /// Writes a VarSet to an output stream
141 friend std::ostream& operator<<( std::ostream &os, const VarSet &vs ) {
142 os << "{";
143 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
144 os << (v != vs.begin() ? ", " : "") << *v;
145 os << "}";
146 return( os );
147 }
148 //@}
149 };
150
151
152 } // end of namespace dai
153
154
155 /** \example example_varset.cpp
156 * This example shows how to use the Var, VarSet and State classes. It also explains the concept of "states" for VarSets.
157 *
158 * \section Output
159 * \verbinclude examples/example_varset.out
160 *
161 * \section Source
162 */
163
164
165 #endif