src/clustergraph.cpp

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 #include <set>
  13 #include <vector>
  14 #include <iostream>
  15 #include <dai/varset.h>
  16 #include <dai/clustergraph.h>
  17
  18
  19 namespace dai {
  20
  21
  22 using namespace std;
  23
  24
  25 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
  26     // construct vars, clusters and edge list
  27     vector<Edge> edges;
  28     foreach( const VarSet &cl, cls ) {
  29         if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
  30             // add cluster
  31             size_t n2 = clusters.size();
  32             clusters.push_back( cl );
  33             for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
  34                 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
  35                 if( n1 == vars.size() )
  36                     // add variable
  37                     vars.push_back( *n );
  38                 edges.push_back( Edge( n1, n2 ) );
  39             }
  40         } // disregard duplicate clusters
  41     }
  42
  43     // Create bipartite graph
  44     G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
  45 }
  46
  47
  48 ClusterGraph ClusterGraph::VarElim_MinFill() const {
  49     // Make a copy
  50     ClusterGraph cl(*this);
  51     cl.eraseNonMaximal();
  52
  53     ClusterGraph result;
  54
  55     // Construct set of variable indices
  56     set<size_t> varindices;
  57     for( size_t i = 0; i < vars.size(); ++i )
  58         varindices.insert( i );
  59
  60     // Do variable elimination
  61     while( !varindices.empty() ) {
  62         set<size_t>::const_iterator lowest = varindices.end();
  63         size_t lowest_cost = -1UL;
  64         for( set<size_t>::const_iterator i = varindices.begin(); i != varindices.end(); i++ ) {
  65             size_t cost = cl.eliminationCost( *i );
  66             if( lowest == varindices.end() || lowest_cost > cost ) {
  67                 lowest = i;
  68                 lowest_cost = cost;
  69             }
  70         }
  71         size_t i = *lowest;
  72
  73         result.insert( cl.Delta( i ) );
  74
  75         cl.insert( cl.delta( i ) );
  76         cl.eraseSubsuming( i );
  77         cl.eraseNonMaximal();
  78         varindices.erase( i );
  79     }
  80
  81     return result;
  82 }
  83
  84
  85
  86 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
  87     // Make a copy
  88     ClusterGraph cl(*this);
  89     cl.eraseNonMaximal();
  90
  91     ClusterGraph result;
  92
  93     // Do variable elimination
  94     for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
  95         size_t i = cl.findVar( *n );
  96         DAI_ASSERT( i != cl.vars.size() );
  97
  98         result.insert( cl.Delta(i) );
  99
 100         cl.insert( cl.delta(i) );
 101         cl.eraseSubsuming( i );
 102         cl.eraseNonMaximal();
 103     }
 104
 105     return result;
 106 }
 107
 108
 109 } // end of namespace dai