46b2244c6950c894eca5df804bf917c75c939756
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
5 Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
6 Radboud University Nijmegen, The Netherlands
8 This file is part of libDAI.
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.
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.
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
27 /// \brief Defines the IndexFor, MultiFor, Permute and State classes
28 /// \todo Improve documentation
31 #ifndef __defined_libdai_index_h
32 #define __defined_libdai_index_h
39 #include <dai/varset.h>
45 /// Tool for looping over the states of several variables.
46 /** The class IndexFor is an important tool for indexing Factor entries.
47 * Its usage can best be explained by an example.
48 * Assume indexVars, forVars are both VarSets.
49 * Then the following code:
51 * IndexFor i( indexVars, forVars );
52 * for( ; i >= 0; ++i ) {
56 * loops over all joint states of the variables in forVars,
57 * and (long)i is equal to the linear index of the corresponding
58 * state of indexVars, where the variables in indexVars that are
59 * not in forVars assume their zero'th value.
60 * \idea Optimize all indices as follows: keep a cache of all (or only
61 * relatively small) indices that have been computed (use a hash). Then,
62 * instead of computing on the fly, use the precomputed ones.
66 /// The current linear index corresponding to the state of indexVars
69 /// For each variable in forVars, the amount of change in _index
70 std::vector
<long> _sum
;
72 /// For each variable in forVars, the current state
73 std::vector
<size_t> _count
;
75 /// For each variable in forVars, its number of possible values
76 std::vector
<size_t> _dims
;
79 /// Default constructor
85 IndexFor( const VarSet
& indexVars
, const VarSet
& forVars
) : _count( forVars
.size(), 0 ) {
88 _dims
.reserve( forVars
.size() );
89 _sum
.reserve( forVars
.size() );
91 VarSet::const_iterator j
= forVars
.begin();
92 for( VarSet::const_iterator i
= indexVars
.begin(); i
!= indexVars
.end(); ++i
) {
93 for( ; j
!= forVars
.end() && *j
<= *i
; ++j
) {
94 _dims
.push_back( j
->states() );
95 _sum
.push_back( (*i
== *j
) ? sum
: 0 );
99 for( ; j
!= forVars
.end(); ++j
) {
100 _dims
.push_back( j
->states() );
106 /// Sets the index back to zero
108 fill( _count
.begin(), _count
.end(), 0 );
113 /// Conversion to long
114 operator long () const {
118 /// Pre-increment operator
119 IndexFor
& operator++ () {
123 while( i
< _count
.size() ) {
125 if( ++_count
[i
] < _dims
[i
] )
127 _index
-= _sum
[i
] * _dims
[i
];
132 if( i
== _count
.size() )
140 /// MultiFor makes it easy to perform a dynamic number of nested for loops.
141 /** An example of the usage is as follows:
143 * std::vector<size_t> dims;
144 * dims.push_back( 3 );
145 * dims.push_back( 4 );
146 * dims.push_back( 5 );
147 * for( MultiFor s(dims); s.valid(); ++s )
148 * cout << "linear index: " << (size_t)s << " corresponds to indices " << s[0] << ", " << s[1] << ", " << s[2] << endl;
150 * which would be equivalent to:
153 * for( size_t s0 = 0; s0 < 3; s0++ )
154 * for( size_t s1 = 0; s1 < 4; s1++ )
155 * for( size_t s2 = 0; s2 < 5; s++, s2++ )
156 * cout << "linear index: " << (size_t)s << " corresponds to indices " << s0 << ", " << s1 << ", " << s2 << endl;
161 std::vector
<size_t> _dims
;
162 std::vector
<size_t> _states
;
166 /// Default constructor
167 MultiFor() : _dims(), _states(), _state(0) {}
169 /// Initialize from vector of index dimensions
170 MultiFor( const std::vector
<size_t> &d
) : _dims(d
), _states(d
.size(),0), _state(0) {}
172 /// Return linear state
173 operator size_t() const {
178 /// Return k'th index
179 size_t operator[]( size_t k
) const {
181 assert( k
< _states
.size() );
185 /// Prefix increment operator
186 MultiFor
& operator++() {
190 for( i
= 0; i
!= _states
.size(); i
++ ) {
191 if( ++(_states
[i
]) < _dims
[i
] )
195 if( i
== _states
.size() )
201 /// Postfix increment operator
202 void operator++( int ) {
206 /// Returns true if the current state is valid
208 return( _state
>= 0 );
213 /// Tool for calculating permutations of multiple indices.
216 std::vector
<size_t> _dims
;
217 std::vector
<size_t> _sigma
;
220 /// Default constructor
221 Permute() : _dims(), _sigma() {}
223 /// Initialize from vector of index dimensions and permutation sigma
224 Permute( const std::vector
<size_t> &d
, const std::vector
<size_t> &sigma
) : _dims(d
), _sigma(sigma
) {
225 assert( _dims
.size() == _sigma
.size() );
228 /// Calculates a permuted linear index.
229 /** Converts the linear index li to a vector index
230 * corresponding with the dimensions in _dims, permutes it according to sigma,
231 * and converts it back to a linear index according to the permuted dimensions.
233 size_t convert_linear_index( size_t li
) {
234 size_t N
= _dims
.size();
236 // calculate vector index corresponding to linear index
237 std::vector
<size_t> vi
;
240 for( size_t k
= 0; k
< N
; k
++ ) {
241 vi
.push_back( li
% _dims
[k
] );
246 // convert permuted vector index to corresponding linear index
249 for( size_t k
= 0; k
< N
; k
++ ) {
250 sigma_li
+= vi
[_sigma
[k
]] * prod
;
251 prod
*= _dims
[_sigma
[k
]];
259 /// Contains the joint state of variables within a VarSet and useful things to do with this information.
260 /** This is very similar to a MultiFor, but tailored for Vars and Varsets.
264 typedef std::map
<Var
, size_t> states_type
;
270 /// Default constructor
271 State() : state(0), states() {}
273 /// Initialize from VarSet
274 State( const VarSet
&vs
) : state(0) {
275 for( VarSet::const_iterator v
= vs
.begin(); v
!= vs
.end(); v
++ )
279 /// Return linear state
280 operator size_t() const {
285 /// Return state of variable n, or zero if n is not in this State
286 size_t operator() ( const Var
&n
) const {
288 states_type::const_iterator entry
= states
.find( n
);
289 if( entry
== states
.end() )
292 return entry
->second
;
295 /// Return linear state of variables in varset, setting them to zero if they are not in this State
296 size_t operator() ( const VarSet
&vs
) const {
300 for( VarSet::const_iterator v
= vs
.begin(); v
!= vs
.end(); v
++ ) {
301 states_type::const_iterator entry
= states
.find( *v
);
302 if( entry
!= states
.end() )
303 vs_state
+= entry
->second
* prod
;
309 /// Prefix increment operator
313 states_type::iterator entry
= states
.begin();
314 while( entry
!= states
.end() ) {
315 if( ++(entry
->second
) < entry
->first
.states() )
320 if( entry
== states
.end() )
325 /// Postfix increment operator
326 void operator++( int ) {
330 /// Returns true if the current state is valid
332 return( state
>= 0 );
337 } // end of namespace dai