00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00016
00017
00018 #ifndef __defined_libdai_clustergraph_h
00019 #define __defined_libdai_clustergraph_h
00020
00021
00022 #include <set>
00023 #include <vector>
00024 #include <dai/varset.h>
00025 #include <dai/bipgraph.h>
00026
00027
00028 namespace dai {
00029
00030
00032
00035 class ClusterGraph {
00036 public:
00038 typedef BipartiteGraph::Neighbor Neighbor;
00039
00041 typedef BipartiteGraph::Edge Edge;
00042
00043 private:
00045 BipartiteGraph _G;
00046
00048 std::vector<Var> _vars;
00049
00051 std::vector<VarSet> _clusters;
00052
00053 public:
00055
00056
00057 ClusterGraph() : _G(), _vars(), _clusters() {}
00058
00060 ClusterGraph( const std::vector<VarSet>& cls );
00062
00064
00065
00066 const BipartiteGraph& bipGraph() const { return _G; }
00067
00069 size_t nrVars() const { return _vars.size(); }
00070
00072 const std::vector<Var>& vars() const { return _vars; }
00073
00075 const Var& var( size_t i ) const {
00076 DAI_DEBASSERT( i < nrVars() );
00077 return _vars[i];
00078 }
00079
00081 size_t nrClusters() const { return _clusters.size(); }
00082
00084 const std::vector<VarSet>& clusters() const { return _clusters; }
00085
00087 const VarSet& cluster( size_t I ) const {
00088 DAI_DEBASSERT( I < nrClusters() );
00089 return _clusters[I];
00090 }
00091
00093
00095 const std::vector<VarSet>& toVector() const { return _clusters; }
00096
00098
00100 size_t size() const { return _G.nrNodes2(); }
00101
00103
00105 size_t findVar( const Var& n ) const {
00106 size_t r = find( _vars.begin(), _vars.end(), n ) - _vars.begin();
00107 if( r == _vars.size() )
00108 DAI_THROW(OBJECT_NOT_FOUND);
00109 return r;
00110 }
00111
00113 VarSet Delta( size_t i ) const {
00114 VarSet result;
00115 foreach( const Neighbor &I, _G.nb1(i) )
00116 result |= _clusters[I];
00117 return result;
00118 }
00119
00121 VarSet delta( size_t i ) const {
00122 return Delta( i ) / _vars[i];
00123 }
00124
00126 bool adj( size_t i1, size_t i2 ) const {
00127 if( i1 == i2 )
00128 return false;
00129 bool result = false;
00130 foreach( const Neighbor &I, _G.nb1(i1) )
00131 if( find( _G.nb2(I).begin(), _G.nb2(I).end(), i2 ) != _G.nb2(I).end() ) {
00132 result = true;
00133 break;
00134 }
00135 return result;
00136 }
00137
00139 bool isMaximal( size_t I ) const {
00140 DAI_DEBASSERT( I < _G.nrNodes2() );
00141 const VarSet & clI = _clusters[I];
00142 bool maximal = true;
00143
00144 foreach( const Neighbor &i, _G.nb2(I) ) {
00145 foreach( const Neighbor &J, _G.nb1(i) )
00146 if( (J != I) && (clI << _clusters[J]) ) {
00147 maximal = false;
00148 break;
00149 }
00150 if( !maximal )
00151 break;
00152 }
00153 return maximal;
00154 }
00156
00158
00159
00160 void insert( const VarSet& cl ) {
00161 if( find( _clusters.begin(), _clusters.end(), cl ) == _clusters.end() ) {
00162 _clusters.push_back( cl );
00163
00164 std::vector<size_t> nbs;
00165 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
00166 size_t iter = find( _vars.begin(), _vars.end(), *n ) - _vars.begin();
00167 nbs.push_back( iter );
00168 if( iter == _vars.size() ) {
00169 _G.addNode1();
00170 _vars.push_back( *n );
00171 }
00172 }
00173 _G.addNode2( nbs.begin(), nbs.end(), nbs.size() );
00174 }
00175 }
00176
00178 ClusterGraph& eraseNonMaximal() {
00179 for( size_t I = 0; I < _G.nrNodes2(); ) {
00180 if( !isMaximal(I) ) {
00181 _clusters.erase( _clusters.begin() + I );
00182 _G.eraseNode2(I);
00183 } else
00184 I++;
00185 }
00186 return *this;
00187 }
00188
00190 ClusterGraph& eraseSubsuming( size_t i ) {
00191 while( _G.nb1(i).size() ) {
00192 _clusters.erase( _clusters.begin() + _G.nb1(i)[0] );
00193 _G.eraseNode2( _G.nb1(i)[0] );
00194 }
00195 return *this;
00196 }
00198
00200
00201
00202 friend std::ostream& operator << ( std::ostream& os, const ClusterGraph& cl ) {
00203 os << cl.clusters();
00204 return os;
00205 }
00207
00209
00210
00211
00215 template<class EliminationChoice>
00216 ClusterGraph VarElim( EliminationChoice f ) const {
00217
00218 ClusterGraph cl(*this);
00219 cl.eraseNonMaximal();
00220
00221 ClusterGraph result;
00222
00223
00224 std::set<size_t> varindices;
00225 for( size_t i = 0; i < _vars.size(); ++i )
00226 varindices.insert( i );
00227
00228
00229 while( !varindices.empty() ) {
00230 size_t i = f( cl, varindices );
00231 DAI_ASSERT( i < _vars.size() );
00232 result.insert( cl.Delta( i ) );
00233 cl.insert( cl.delta( i ) );
00234 cl.eraseSubsuming( i );
00235 cl.eraseNonMaximal();
00236 varindices.erase( i );
00237 }
00238
00239 return result;
00240 }
00242 };
00243
00244
00246
00248 class sequentialVariableElimination {
00249 private:
00251 std::vector<Var> seq;
00253 size_t i;
00254
00255 public:
00257 sequentialVariableElimination( const std::vector<Var> s ) : seq(s), i(0) {}
00258
00260 size_t operator()( const ClusterGraph &cl, const std::set<size_t> & );
00261 };
00262
00263
00265
00268 class greedyVariableElimination {
00269 public:
00271 typedef size_t (*eliminationCostFunction)(const ClusterGraph &, size_t);
00272
00273 private:
00275 eliminationCostFunction heuristic;
00276
00277 public:
00279
00281 greedyVariableElimination( eliminationCostFunction h ) : heuristic(h) {}
00282
00284
00286 size_t operator()( const ClusterGraph &cl, const std::set<size_t>& remainingVars );
00287 };
00288
00289
00291
00295 size_t eliminationCost_MinNeighbors( const ClusterGraph& cl, size_t i );
00296
00297
00299
00304 size_t eliminationCost_MinWeight( const ClusterGraph& cl, size_t i );
00305
00306
00308
00312 size_t eliminationCost_MinFill( const ClusterGraph& cl, size_t i );
00313
00314
00316
00321 size_t eliminationCost_WeightedMinFill( const ClusterGraph& cl, size_t i );
00322
00323
00324 }
00325
00326
00327 #endif