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
  49 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> &ElimSeq ) const {
  50     // Make a copy
  51     ClusterGraph cl(*this);
  52     cl.eraseNonMaximal();
  53
  54     ClusterGraph result;
  55
  56     // Do variable elimination
  57     for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
  58         size_t i = cl.findVar( *n );
  59         DAI_ASSERT( i != cl.vars.size() );
  60
  61         result.insert( cl.Delta(i) );
  62
  63         cl.insert( cl.delta(i) );
  64         cl.eraseSubsuming( i );
  65         cl.eraseNonMaximal();
  66     }
  67
  68     return result;
  69 }
  70
  71
  72 size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i ) {
  73     std::vector<size_t> id_n = cl.G.delta1( i );
  74
  75     size_t cost = 0;
  76
  77     // for each unordered pair {i1,i2} adjacent to n
  78     for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
  79         for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
  80             // if i1 and i2 are not adjacent, eliminating n would make them adjacent
  81             if( !cl.adj(id_n[_i1], id_n[_i2]) )
  82                 cost++;
  83         }
  84
  85     return cost;
  86 }
  87
  88
  89 size_t eliminationChoice_MinFill( const ClusterGraph &cl, const std::set<size_t> &remainingVars ) {
  90     set<size_t>::const_iterator lowest = remainingVars.end();
  91     size_t lowest_cost = -1UL;
  92     for( set<size_t>::const_iterator i = remainingVars.begin(); i != remainingVars.end(); i++ ) {
  93         size_t cost = eliminationCost_MinFill( cl, *i );
  94         if( lowest == remainingVars.end() || lowest_cost > cost ) {
  95             lowest = i;
  96             lowest_cost = cost;
  97         }
  98     }
  99     return *lowest;
 100 }
 101
 102
 103 } // end of namespace dai