src/clustergraph.cpp

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   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.
  11
  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.
  16
  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
  20 */
  21
  22
  23 #include <set>
  24 #include <vector>
  25 #include <iostream>
  26 #include <dai/varset.h>
  27 #include <dai/clustergraph.h>
  28
  29
  30 namespace dai {
  31
  32
  33 using namespace std;
  34
  35
  36 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
  37     // construct vars, clusters and edge list
  38     vector<Edge> edges;
  39     foreach( const VarSet &cl, cls ) {
  40         if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
  41             // add cluster
  42             size_t n2 = clusters.size();
  43             clusters.push_back( cl );
  44             for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
  45                 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
  46                 if( n1 == vars.size() )
  47                     // add variable
  48                     vars.push_back( *n );
  49                 edges.push_back( Edge( n1, n2 ) );
  50             }
  51         } // disregard duplicate clusters
  52     }
  53
  54     // Create bipartite graph
  55     G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
  56 }
  57
  58
  59 ClusterGraph ClusterGraph::VarElim_MinFill() const {
  60     // Make a copy
  61     ClusterGraph cl(*this);
  62     cl.eraseNonMaximal();
  63
  64     ClusterGraph result;
  65
  66     // Construct set of variable indices
  67     set<size_t> varindices;
  68     for( size_t i = 0; i < vars.size(); ++i )
  69         varindices.insert( i );
  70
  71     // Do variable elimination
  72     while( !varindices.empty() ) {
  73         set<size_t>::const_iterator lowest = varindices.end();
  74         size_t lowest_cost = -1UL;
  75         for( set<size_t>::const_iterator i = varindices.begin(); i != varindices.end(); i++ ) {
  76             size_t cost = cl.eliminationCost( *i );
  77             if( lowest == varindices.end() || lowest_cost > cost ) {
  78                 lowest = i;
  79                 lowest_cost = cost;
  80             }
  81         }
  82         size_t i = *lowest;
  83
  84         result.insert( cl.Delta( i ) );
  85
  86         cl.insert( cl.delta( i ) );
  87         cl.eraseSubsuming( i );
  88         cl.eraseNonMaximal();
  89         varindices.erase( i );
  90     }
  91
  92     return result;
  93 }
  94
  95
  96
  97 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
  98     // Make a copy
  99     ClusterGraph cl(*this);
 100     cl.eraseNonMaximal();
 101
 102     ClusterGraph result;
 103
 104     // Do variable elimination
 105     for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
 106         size_t i = cl.findVar( *n );
 107         assert( i != cl.vars.size() );
 108
 109         result.insert( cl.Delta(i) );
 110
 111         cl.insert( cl.delta(i) );
 112         cl.eraseSubsuming( i );
 113         cl.eraseNonMaximal();
 114     }
 115
 116     return result;
 117 }
 118
 119
 120 } // end of namespace dai