include/dai/varset.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   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]
   9  *  Copyright (C) 2002-2007  Radboud University Nijmegen, The Netherlands
  10  */
  11
  12
  13 /// \file
  14 /// \brief Defines the VarSet class, which represents a set of random variables.
  15
  16
  17 #ifndef __defined_libdai_varset_h
  18 #define __defined_libdai_varset_h
  19
  20
  21 #include <vector>
  22 #include <map>
  23 #include <ostream>
  24 #include <dai/var.h>
  25 #include <dai/util.h>
  26 #include <dai/smallset.h>
  27
  28
  29 namespace dai {
  30
  31
  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>() {}
  47
  48         /// Construct from \link SmallSet \endlink<\link Var \endlink> \a x
  49         VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
  50
  51         /// Construct a VarSet with one element, \a v
  52         VarSet( const Var &v ) : SmallSet<Var>(v) {}
  53
  54         /// Construct a VarSet with two elements, \a v1 and \a v2
  55         VarSet( const Var &v1, const Var &v2 ) : SmallSet<Var>(v1,v2) {}
  56
  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     //@}
  66
  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         }
  83
  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         }
 120
 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     //@}
 150
 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 };
 163
 164
 165 } // end of namespace dai
 166
 167
 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  */
 176
 177
 178 #endif