src/clustergraph.cpp

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
   2     Radboud University Nijmegen, The Netherlands
   3
   4     This file is part of libDAI.
   5
   6     libDAI is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     libDAI is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with libDAI; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19 */
  20
  21
  22 #include <set>
  23 #include <vector>
  24 #include <iostream>
  25 #include <dai/varset.h>
  26 #include <dai/clustergraph.h>
  27
  28
  29 namespace dai {
  30
  31
  32 using namespace std;
  33
  34
  35 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
  36     const long verbose = 0;
  37
  38     // Make a copy
  39     ClusterGraph _Cl(*this);
  40
  41     ClusterGraph result;
  42     _Cl.eraseNonMaximal();
  43
  44     // Do variable elimination
  45     for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
  46         assert( _Cl.vars() && *n );
  47
  48         if( verbose >= 1 )
  49             cout << "Cost of eliminating " << *n << ": " << _Cl.eliminationCost( *n ) << " new edges" << endl;
  50
  51         result.insert( _Cl.Delta(*n) );
  52
  53         if( verbose >= 1 )
  54             cout << "_Cl = " << _Cl << endl;
  55
  56         if( verbose >= 1 )
  57             cout << "After inserting " << _Cl.delta(*n) << ", _Cl = ";
  58         _Cl.insert( _Cl.delta(*n) );
  59         if( verbose >= 1 )
  60             cout << _Cl << endl;
  61
  62         if( verbose >= 1 )
  63             cout << "After erasing clusters that contain " << *n <<  ", _Cl = ";
  64         _Cl.eraseSubsuming( *n );
  65         if( verbose >= 1 )
  66             cout << _Cl << endl;
  67
  68         if( verbose >= 1 )
  69             cout << "After erasing nonmaximal clusters, _Cl = ";
  70         _Cl.eraseNonMaximal();
  71         if( verbose >= 1 )
  72             cout << _Cl << endl;
  73     }
  74
  75     return result;
  76 }
  77
  78
  79 ClusterGraph ClusterGraph::VarElim_MinFill() const {
  80     const long verbose = 0;
  81
  82     // Make a copy
  83     ClusterGraph _Cl(*this);
  84     VarSet _vars( vars() );
  85
  86     ClusterGraph result;
  87     _Cl.eraseNonMaximal();
  88
  89     // Do variable elimination
  90     while( !_vars.empty() ) {
  91         if( verbose >= 1 )
  92             cout << "Var  Eliminiation cost" << endl;
  93         VarSet::const_iterator lowest = _vars.end();
  94         size_t lowest_cost = -1UL;
  95         for( VarSet::const_iterator n = _vars.begin(); n != _vars.end(); n++ ) {
  96             size_t cost = _Cl.eliminationCost( *n );
  97             if( verbose >= 1 )
  98                 cout << *n << "  " << cost << endl;
  99             if( lowest == _vars.end() || lowest_cost > cost ) {
 100                 lowest = n;
 101                 lowest_cost = cost;
 102             }
 103         }
 104         Var n = *lowest;
 105
 106         if( verbose >= 1 )
 107             cout << "Lowest: " << n << " (" << lowest_cost << ")" << endl;
 108
 109         result.insert( _Cl.Delta(n) );
 110
 111         _Cl.insert( _Cl.delta(n) );
 112         _Cl.eraseSubsuming( n );
 113         _Cl.eraseNonMaximal();
 114         _vars /= n;
 115
 116     }
 117
 118     return result;
 119 }
 120
 121
 122 } // end of namespace dai