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( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
  36     // construct vars, clusters and edge list
  37     vector<Edge> edges;
  38     foreach( const VarSet &cl, cls ) {
  39         if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
  40             // add cluster
  41             size_t n2 = clusters.size();
  42             clusters.push_back( cl );
  43             for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
  44                 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
  45                 if( n1 == vars.size() )
  46                     // add variable
  47                     vars.push_back( *n );
  48                 edges.push_back( Edge( n1, n2 ) );
  49             }
  50         } // disregard duplicate clusters
  51     }
  52
  53     // Create bipartite graph
  54     G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
  55 }
  56
  57
  58 ClusterGraph ClusterGraph::VarElim_MinFill() const {
  59     // Make a copy
  60     ClusterGraph cl(*this);
  61     cl.eraseNonMaximal();
  62
  63     ClusterGraph result;
  64
  65     // Construct set of variable indices
  66     set<size_t> varindices;
  67     for( size_t i = 0; i < vars.size(); ++i )
  68         varindices.insert( i );
  69
  70     // Do variable elimination
  71     while( !varindices.empty() ) {
  72         set<size_t>::const_iterator lowest = varindices.end();
  73         size_t lowest_cost = -1UL;
  74         for( set<size_t>::const_iterator i = varindices.begin(); i != varindices.end(); i++ ) {
  75             size_t cost = cl.eliminationCost( *i );
  76             if( lowest == varindices.end() || lowest_cost > cost ) {
  77                 lowest = i;
  78                 lowest_cost = cost;
  79             }
  80         }
  81         size_t i = *lowest;
  82
  83         result.insert( cl.Delta( i ) );
  84
  85         cl.insert( cl.delta( i ) );
  86         cl.eraseSubsuming( i );
  87         cl.eraseNonMaximal();
  88         varindices.erase( i );
  89     }
  90
  91     return result;
  92 }
  93
  94
  95
  96 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
  97     // Make a copy
  98     ClusterGraph cl(*this);
  99     cl.eraseNonMaximal();
 100
 101     ClusterGraph result;
 102
 103     // Do variable elimination
 104     for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
 105         size_t i = cl.findVar( *n );
 106         assert( i != cl.vars.size() );
 107
 108         result.insert( cl.Delta(i) );
 109
 110         cl.insert( cl.delta(i) );
 111         cl.eraseSubsuming( i );
 112         cl.eraseNonMaximal();
 113     }
 114
 115     return result;
 116 }
 117
 118
 119 } // end of namespace dai