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 /** \note A VarSet is implemented using a SmallSet<Var> instead
  48  *  of the more natural std::set<Var> because of efficiency reasons.
  49  *  That is, internally, the variables in the set are sorted according
  50  *  to their labels: the set of variables \f$\{x_l\}_{l\in L}\f$ is
  51  *  represented as a vector \f$(x_{l(0)},x_{l(1)},\dots,x_{l(|L|-1)})\f$
  52  *  where \f$l(0) < l(1) < \dots < l(|L|-1)\f$
  53  *  and \f$L = \{l(0),l(1),\dots,l(|L|-1)\}\f$.
  54  */
  55 class VarSet : public SmallSet<Var> {
  56     public:
  57         /// Default constructor
  58         VarSet() : SmallSet<Var>() {}
  59
  60         /// Construct from SmallSet<Var>
  61         VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
  62
  63         /// Calculates the number of states of this VarSet.
  64         /** The number of states of the Cartesian product of the variables in this VarSet
  65          *  is simply the product of the number of states of each variable in this VarSet.
  66          *  If *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
  67          *  where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
  68          *  number of possible values ("states") of variable \f$x_l\f$, the number of
  69          *  joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
  70          */
  71         size_t nrStates() {
  72             size_t states = 1;
  73             for( VarSet::const_iterator n = begin(); n != end(); n++ )
  74                 states *= n->states();
  75             return states;
  76         }
  77
  78         /// Construct a VarSet with one element
  79         VarSet( const Var &n ) : SmallSet<Var>(n) {}
  80
  81         /// Construct a VarSet with two elements
  82         VarSet( const Var &n1, const Var &n2 ) : SmallSet<Var>(n1,n2) {}
  83
  84         /// Construct a VarSet from a range.
  85         /** \tparam VarIterator Iterates over instances of type Var.
  86          *  \param begin Points to first Var to be added.
  87          *  \param end Points just beyond last Var to be added.
  88          *  \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
  89          */
  90         template <typename VarIterator>
  91         VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
  92
  93         /// 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.
  94         /** \param states Specifies the states of some variables.
  95          *  \return The linear index in the Cartesian product of the variables in *this
  96          *  corresponding with the joint assignment specified by \a states, where it is
  97          *  assumed that \a states[\a m]==0 for all \a m in *this which are not in \a states.
  98          *
  99          *  The linear index is calculated as follows. The variables in *this are
 100          *  ordered according to their label (in ascending order); say *this corresponds with
 101          *  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$,
 102          *  where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
 103          *  ("states") of variable \f$x_l\f$. The argument \a states corresponds
 104          *  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$,
 105          *  where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a states. The linear index \a S corresponding
 106          *  with \a states is now calculated as:
 107          *  \f{eqnarray*}
 108          *    S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
 109          *      &= & 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)}.
 110          *  \f}
 111          *
 112          *  \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, and \a states specifies a state
 113          *  for each variable \f$x_l\f$ for \f$l\in L\f$, calcState(const std::map<Var,size_t> &) induces a mapping
 114          *  \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
 115          *  maps a joint state to a linear index; this is the inverse of the mapping
 116          *  \f$\sigma^{-1}\f$ induced by calcStates(size_t).
 117          */
 118         size_t calcState( const std::map<Var, size_t> &states ) {
 119             size_t prod = 1;
 120             size_t state = 0;
 121             for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
 122                 std::map<Var, size_t>::const_iterator m = states.find( *n );
 123                 if( m != states.end() )
 124                     state += prod * m->second;
 125                 prod *= n->states();
 126             }
 127             return state;
 128         }
 129
 130         /// Calculates the joint assignment of the variables in *this corresponding to the linear index \a linearState.
 131         /** \param linearState should be smaller than nrStates().
 132          *  \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.
 133          *
 134          *  The variables in *this are ordered according to their label (in ascending order); say *this corresponds with
 135          *  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$,
 136          *  where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
 137          *  ("states") of variable \f$x_l\f$ with label \a l.
 138          *  The mapping \a s returned by this function is defined as:
 139          *  \f{eqnarray*}
 140          *    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$}.
 141          *  \f}
 142          *  where \f$S\f$ denotes the value of \a linearState.
 143          *
 144          *  \note If *this corresponds with \f$\{x_l\}_{l\in L}\f$, calcStates(size_t) induces a mapping
 145          *  \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l\f$ that
 146          *  maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
 147          *  induced by calcState(const std::map<Var,size_t> &).
 148          */
 149         std::map<Var, size_t> calcStates( size_t linearState ) {
 150             std::map<Var, size_t> states;
 151             for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
 152                 states[*n] = linearState % n->states();
 153                 linearState /= n->states();
 154             }
 155             assert( linearState == 0 );
 156             return states;
 157         }
 158
 159         /// Writes a VarSet to an output stream
 160         friend std::ostream& operator<< (std::ostream &os, const VarSet& ns)  {
 161             os << "{";
 162             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
 163                 os << (n != ns.begin() ? "," : "") << *n;
 164             os << "}";
 165             return( os );
 166         }
 167 };
 168
 169
 170 } // end of namespace dai
 171
 172
 173 /** \example example_varset.cpp
 174  *  This example shows how to use the Var and VarSet classes. It also explains the concept of "states" for VarSets.
 175  *
 176  *  \section Output
 177  *  \verbinclude examples/example_varset.out
 178  *
 179  *  \section Source
 180  */
 181
 182
 183 #endif