libDAI
clustergraph.h
Go to the documentation of this file.
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 
13 
14 
15 #ifndef __defined_libdai_clustergraph_h
16 #define __defined_libdai_clustergraph_h
17 
18 
19 #include <set>
20 #include <vector>
21 #include <dai/varset.h>
22 #include <dai/bipgraph.h>
23 #include <dai/factorgraph.h>
24 
25 
26 namespace dai {
27 
28 
30 
34  class ClusterGraph {
35  private:
38 
40  std::vector<Var> _vars;
41 
43  std::vector<VarSet> _clusters;
44 
45  public:
47 
48 
49  ClusterGraph() : _G(), _vars(), _clusters() {}
50 
52  ClusterGraph( const std::vector<VarSet>& cls );
53 
55 
58  ClusterGraph( const FactorGraph& fg, bool onlyMaximal );
60 
62 
63 
64  const BipartiteGraph& bipGraph() const { return _G; }
65 
67  size_t nrVars() const { return _vars.size(); }
68 
70  const std::vector<Var>& vars() const { return _vars; }
71 
73  const Var& var( size_t i ) const {
74  DAI_DEBASSERT( i < nrVars() );
75  return _vars[i];
76  }
77 
79  size_t nrClusters() const { return _clusters.size(); }
80 
82  const std::vector<VarSet>& clusters() const { return _clusters; }
83 
85  const VarSet& cluster( size_t I ) const {
86  DAI_DEBASSERT( I < nrClusters() );
87  return _clusters[I];
88  }
89 
91  size_t findVar( const Var& n ) const {
92  return find( _vars.begin(), _vars.end(), n ) - _vars.begin();
93  }
94 
96  size_t findCluster( const VarSet& cl ) const {
97  return find( _clusters.begin(), _clusters.end(), cl ) - _clusters.begin();
98  }
99 
101  VarSet Delta( size_t i ) const {
102  VarSet result;
103  bforeach( const Neighbor& I, _G.nb1(i) )
104  result |= _clusters[I];
105  return result;
106  }
107 
109  VarSet delta( size_t i ) const {
110  return Delta( i ) / _vars[i];
111  }
112 
114  bool adj( size_t i1, size_t i2 ) const {
115  if( i1 == i2 )
116  return false;
117  bool result = false;
118  bforeach( const Neighbor& I, _G.nb1(i1) )
119  if( find( _G.nb2(I).begin(), _G.nb2(I).end(), i2 ) != _G.nb2(I).end() ) {
120  result = true;
121  break;
122  }
123  return result;
124  }
125 
127  bool isMaximal( size_t I ) const {
128  DAI_DEBASSERT( I < _G.nrNodes2() );
129  const VarSet & clI = _clusters[I];
130  bool maximal = true;
131  // The following may not be optimal, since it may repeatedly test the same cluster *J
132  bforeach( const Neighbor& i, _G.nb2(I) ) {
133  bforeach( const Neighbor& J, _G.nb1(i) )
134  if( (J != I) && (clI << _clusters[J]) ) {
135  maximal = false;
136  break;
137  }
138  if( !maximal )
139  break;
140  }
141  return maximal;
142  }
144 
146 
147 
148 
151  size_t insert( const VarSet& cl ) {
152  size_t index = findCluster( cl ); // OPTIMIZE ME
153  if( index == _clusters.size() ) {
154  _clusters.push_back( cl );
155  // add variables (if necessary) and calculate neighborhood of new cluster
156  std::vector<size_t> nbs;
157  for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
158  size_t iter = findVar( *n ); // OPTIMIZE ME
159  nbs.push_back( iter );
160  if( iter == _vars.size() ) {
161  _G.addNode1();
162  _vars.push_back( *n );
163  }
164  }
165  _G.addNode2( nbs.begin(), nbs.end(), nbs.size() );
166  }
167  return index;
168  }
169 
172  for( size_t I = 0; I < _G.nrNodes2(); ) {
173  if( !isMaximal(I) ) {
174  _clusters.erase( _clusters.begin() + I );
175  _G.eraseNode2(I);
176  } else
177  I++;
178  }
179  return *this;
180  }
181 
184  DAI_ASSERT( i < nrVars() );
185  while( _G.nb1(i).size() ) {
186  _clusters.erase( _clusters.begin() + _G.nb1(i)[0] );
187  _G.eraseNode2( _G.nb1(i)[0] );
188  }
189  return *this;
190  }
191 
193 
195  VarSet elimVar( size_t i ) {
196  DAI_ASSERT( i < nrVars() );
197  VarSet Di = Delta( i );
198  insert( Di / var(i) );
199  eraseSubsuming( i );
200  eraseNonMaximal();
201  return Di;
202  }
204 
206 
207 
208  friend std::ostream& operator << ( std::ostream& os, const ClusterGraph& cl ) {
209  os << cl.clusters();
210  return os;
211  }
213 
215 
216 
217 
223  template<class EliminationChoice>
224  ClusterGraph VarElim( EliminationChoice f, size_t maxStates=0 ) const {
225  // Make a copy
226  ClusterGraph cl(*this);
227  cl.eraseNonMaximal();
228 
229  ClusterGraph result;
230 
231  // Construct set of variable indices
232  std::set<size_t> varindices;
233  for( size_t i = 0; i < _vars.size(); ++i )
234  varindices.insert( i );
235 
236  // Do variable elimination
237  BigInt totalStates = 0;
238  while( !varindices.empty() ) {
239  size_t i = f( cl, varindices );
240  VarSet Di = cl.elimVar( i );
241  result.insert( Di );
242  if( maxStates ) {
243  totalStates += Di.nrStates();
244  if( totalStates > (BigInt)maxStates )
245  DAI_THROW(OUT_OF_MEMORY);
246  }
247  varindices.erase( i );
248  }
249 
250  return result;
251  }
253  };
254 
255 
257 
260  private:
262  std::vector<Var> seq;
264  size_t i;
265 
266  public:
268  sequentialVariableElimination( const std::vector<Var> s ) : seq(s), i(0) {}
269 
271  size_t operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ );
272  };
273 
274 
276 
280  public:
282  typedef size_t (*eliminationCostFunction)(const ClusterGraph &, size_t);
283 
284  private:
287 
288  public:
290 
293 
295 
297  size_t operator()( const ClusterGraph &cl, const std::set<size_t>& remainingVars );
298  };
299 
300 
302 
306  size_t eliminationCost_MinNeighbors( const ClusterGraph& cl, size_t i );
307 
308 
310 
315  size_t eliminationCost_MinWeight( const ClusterGraph& cl, size_t i );
316 
317 
319 
323  size_t eliminationCost_MinFill( const ClusterGraph& cl, size_t i );
324 
325 
327 
332  size_t eliminationCost_WeightedMinFill( const ClusterGraph& cl, size_t i );
333 
334 
335 } // end of namespace dai
336 
337 
338 #endif