1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
3 Radboud University Nijmegen, The Netherlands
5 This file is part of libDAI.
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 #ifndef __defined_libdai_varset_h
24 #define __defined_libdai_varset_h
39 /// A VarSet represents a set of variables.
41 * It is implemented as an ordered std::vector<Var> for efficiency reasons
42 * (indeed, it was found that a std::set<Var> usually has more overhead).
43 * In addition, it provides an interface for common set-theoretic operations.
47 /// The variables in this set
48 std::vector
<Var
> _vars
;
50 /// Product of number of states of all contained variables
54 /// Default constructor
55 VarSet() : _vars(), _states(1) {};
57 /// Construct a VarSet from one variable
58 VarSet( const Var
&n
) : _vars(), _states( n
.states() ) {
62 /// Construct a VarSet from two variables
63 VarSet( const Var
&n1
, const Var
&n2
) {
65 _vars
.push_back( n1
);
66 _vars
.push_back( n2
);
67 } else if( n1
> n2
) {
68 _vars
.push_back( n2
);
69 _vars
.push_back( n1
);
71 _vars
.push_back( n1
);
75 /// Construct from a range of iterators
76 /** The value_type of the VarIterator should be Var.
77 * For efficiency, the number of variables can be
78 * speficied by sizeHint.
80 template <typename VarIterator
>
81 VarSet( VarIterator begin
, VarIterator end
, size_t sizeHint
=0 ) {
82 _vars
.reserve( sizeHint
);
83 _vars
.insert( _vars
.begin(), begin
, end
);
84 std::sort( _vars
.begin(), _vars
.end() );
85 std::vector
<Var
>::iterator new_end
= std::unique( _vars
.begin(), _vars
.end() );
86 _vars
.erase( new_end
, _vars
.end() );
91 VarSet( const VarSet
&x
) : _vars( x
._vars
), _states( x
._states
) {}
93 /// Assignment operator
94 VarSet
& operator=( const VarSet
&x
) {
103 /// Returns the product of the number of states of each variable in this set
104 size_t states() const {
109 /// Setminus operator (result contains all variables in *this, except those in ns)
110 VarSet
operator/ ( const VarSet
& ns
) const {
112 std::set_difference( _vars
.begin(), _vars
.end(), ns
._vars
.begin(), ns
._vars
.end(), inserter( res
._vars
, res
._vars
.begin() ) );
117 /// Set-union operator (result contains all variables in *this, plus those in ns)
118 VarSet
operator| ( const VarSet
& ns
) const {
120 std::set_union( _vars
.begin(), _vars
.end(), ns
._vars
.begin(), ns
._vars
.end(), inserter( res
._vars
, res
._vars
.begin() ) );
125 /// Set-intersection operator (result contains all variables in *this that are also contained in ns)
126 VarSet
operator& ( const VarSet
& ns
) const {
128 std::set_intersection( _vars
.begin(), _vars
.end(), ns
._vars
.begin(), ns
._vars
.end(), inserter( res
._vars
, res
._vars
.begin() ) );
133 /// Erases from *this all variables in ns
134 VarSet
& operator/= ( const VarSet
& ns
) {
135 return (*this = (*this / ns
));
138 /// Erase one variable
139 VarSet
& operator/= ( const Var
& n
) {
140 std::vector
<Var
>::iterator pos
= lower_bound( _vars
.begin(), _vars
.end(), n
);
141 if( pos
!= _vars
.end() )
142 if( *pos
== n
) { // found variable, delete it
144 _states
/= n
.states();
149 /// Adds to *this all variables in ns
150 VarSet
& operator|= ( const VarSet
& ns
) {
151 return( *this = (*this | ns
) );
155 VarSet
& operator|= ( const Var
& n
) {
156 std::vector
<Var
>::iterator pos
= lower_bound( _vars
.begin(), _vars
.end(), n
);
157 if( pos
== _vars
.end() || *pos
!= n
) { // insert it
158 _vars
.insert( pos
, n
);
159 _states
*= n
.states();
165 /// Erases from *this all variables not in ns
166 VarSet
& operator&= ( const VarSet
& ns
) {
167 return (*this = (*this & ns
));
171 /// Returns true if *this is a subset of ns
172 bool operator<< ( const VarSet
& ns
) const {
173 return std::includes( ns
._vars
.begin(), ns
._vars
.end(), _vars
.begin(), _vars
.end() );
176 /// Returns true if ns is a subset of *this
177 bool operator>> ( const VarSet
& ns
) const {
178 return std::includes( _vars
.begin(), _vars
.end(), ns
._vars
.begin(), ns
._vars
.end() );
181 /// Returns true if *this and ns contain common variables
182 bool intersects( const VarSet
& ns
) const {
183 return( (*this & ns
).size() > 0 );
186 /// Returns true if *this contains the variable n
187 bool contains( const Var
& n
) const {
188 return std::binary_search( _vars
.begin(), _vars
.end(), n
);
191 /// Sends a VarSet to an output stream
192 friend std::ostream
& operator<< (std::ostream
& os
, const VarSet
& ns
) {
193 foreach( const Var
&n
, ns
._vars
)
198 /// Constant iterator over Vars
199 typedef std::vector
<Var
>::const_iterator const_iterator
;
200 /// Iterator over Vars
201 typedef std::vector
<Var
>::iterator iterator
;
202 /// Constant reverse iterator over Vars
203 typedef std::vector
<Var
>::const_reverse_iterator const_reverse_iterator
;
204 /// Reverse iterator over Vars
205 typedef std::vector
<Var
>::reverse_iterator reverse_iterator
;
207 /// Returns iterator that points to the first variable
208 iterator
begin() { return _vars
.begin(); }
209 /// Returns constant iterator that points to the first variable
210 const_iterator
begin() const { return _vars
.begin(); }
212 /// Returns iterator that points beyond the last variable
213 iterator
end() { return _vars
.end(); }
214 /// Returns constant iterator that points beyond the last variable
215 const_iterator
end() const { return _vars
.end(); }
217 /// Returns reverse iterator that points to the last variable
218 reverse_iterator
rbegin() { return _vars
.rbegin(); }
219 /// Returns constant reverse iterator that points to the last variable
220 const_reverse_iterator
rbegin() const { return _vars
.rbegin(); }
222 /// Returns reverse iterator that points beyond the first variable
223 reverse_iterator
rend() { return _vars
.rend(); }
224 /// Returns constant reverse iterator that points beyond the first variable
225 const_reverse_iterator
rend() const { return _vars
.rend(); }
228 /// Returns number of variables
229 std::vector
<Var
>::size_type
size() const { return _vars
.size(); }
232 /// Returns whether the VarSet is empty
233 bool empty() const { return _vars
.size() == 0; }
236 /// Test for equality of variable labels
237 friend bool operator==( const VarSet
&a
, const VarSet
&b
) {
238 return (a
._vars
== b
._vars
);
241 /// Test for inequality of variable labels
242 friend bool operator!=( const VarSet
&a
, const VarSet
&b
) {
243 return !(a
._vars
== b
._vars
);
246 /// Lexicographical comparison of variable labels
247 friend bool operator<( const VarSet
&a
, const VarSet
&b
) {
248 return a
._vars
< b
._vars
;
251 /// calcState calculates the linear index of this VarSet that corresponds
252 /// to the states of the variables given in states, implicitly assuming
253 /// states[m] = 0 for all m in this VarSet which are not in states.
254 size_t calcState( const std::map
<Var
, size_t> &states
) const {
257 foreach( const Var
&n
, *this ) {
258 std::map
<Var
, size_t>::const_iterator m
= states
.find( n
);
259 if( m
!= states
.end() )
260 state
+= prod
* m
->second
;
267 /// Calculates the number of states
268 size_t calcStates() {
270 foreach( Var
&i
, _vars
)
271 _states
*= i
.states();
277 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
278 inline VarSet
operator| (const Var
& n1
, const Var
& n2
) {
279 return( VarSet(n1
, n2
) );
283 } // end of namespace dai