include/dai/clustergraph.h

   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 /// \file
  13 /// \brief Defines class ClusterGraph
  14 /// \todo Improve documentation
  15
  16
  17 #ifndef __defined_libdai_clustergraph_h
  18 #define __defined_libdai_clustergraph_h
  19
  20
  21 #include <set>
  22 #include <vector>
  23 #include <dai/varset.h>
  24 #include <dai/bipgraph.h>
  25
  26
  27 namespace dai {
  28
  29
  30     /// A ClusterGraph is a hypergraph with VarSets as nodes.
  31     /** It is implemented as bipartite graph with variable (Var) nodes
  32      *  and cluster (VarSet) nodes.
  33      */
  34     class ClusterGraph {
  35         public:
  36             /// Stores the neighborhood structure
  37             BipartiteGraph       G;
  38
  39             /// Stores the variables corresponding to the nodes
  40             std::vector<Var>     vars;
  41
  42             /// Stores the clusters corresponding to the hyperedges
  43             std::vector<VarSet>  clusters;
  44
  45             /// Shorthand for BipartiteGraph::Neighbor
  46             typedef BipartiteGraph::Neighbor Neighbor;
  47
  48             /// Shorthand for BipartiteGraph::Edge
  49             typedef BipartiteGraph::Edge     Edge;
  50
  51         public:
  52             /// Default constructor
  53             ClusterGraph() : G(), vars(), clusters() {}
  54
  55             /// Construct from vector<VarSet>
  56             ClusterGraph( const std::vector<VarSet> & cls );
  57
  58             /// Returns true if cluster I is not contained in a larger cluster
  59             bool isMaximal( size_t I ) const {
  60                 DAI_DEBASSERT( I < G.nr2() );
  61                 const VarSet & clI = clusters[I];
  62                 bool maximal = true;
  63                 // The following may not be optimal, since it may repeatedly test the same cluster *J
  64                 foreach( const Neighbor &i, G.nb2(I) ) {
  65                     foreach( const Neighbor &J, G.nb1(i) )
  66                         if( (J != I) && (clI << clusters[J]) ) {
  67                             maximal = false;
  68                             break;
  69                         }
  70                     if( !maximal )
  71                         break;
  72                 }
  73                 return maximal;
  74             }
  75
  76             /// Erases all VarSets that are not maximal
  77             ClusterGraph& eraseNonMaximal() {
  78                 for( size_t I = 0; I < G.nr2(); ) {
  79                     if( !isMaximal(I) ) {
  80                         clusters.erase( clusters.begin() + I );
  81                         G.erase2(I);
  82                     } else
  83                         I++;
  84                 }
  85                 return *this;
  86             }
  87
  88             /// Returns number of clusters
  89             size_t size() const {
  90                 return G.nr2();
  91             }
  92
  93             /// Returns index of variable n
  94             size_t findVar( const Var &n ) const {
  95                 return find( vars.begin(), vars.end(), n ) - vars.begin();
  96             }
  97
  98             /// Returns true if vars with indices i1 and i2 are adjacent, i.e., both contained in the same cluster
  99             bool adj( size_t i1, size_t i2 ) {
 100                 bool result = false;
 101                 foreach( const Neighbor &I, G.nb1(i1) )
 102                     if( find( G.nb2(I).begin(), G.nb2(I).end(), i2 ) != G.nb2(I).end() ) {
 103                         result = true;
 104                         break;
 105                     }
 106                 return result;
 107             }
 108
 109             /// Returns union of clusters that contain the variable with index i
 110             VarSet Delta( size_t i ) const {
 111                 VarSet result;
 112                 foreach( const Neighbor &I, G.nb1(i) )
 113                     result |= clusters[I];
 114                 return result;
 115             }
 116
 117             /// Inserts a cluster (if it does not already exist)
 118             void insert( const VarSet &cl ) {
 119                 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
 120                     clusters.push_back( cl );
 121                     // add variables (if necessary) and calculate neighborhood of new cluster
 122                     std::vector<size_t> nbs;
 123                     for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
 124                         size_t iter = find( vars.begin(), vars.end(), *n ) - vars.begin();
 125                         nbs.push_back( iter );
 126                         if( iter == vars.size() ) {
 127                             G.add1();
 128                             vars.push_back( *n );
 129                         }
 130                     }
 131                     G.add2( nbs.begin(), nbs.end(), nbs.size() );
 132                 }
 133             }
 134
 135             /// Returns union of clusters that contain variable with index i, minus this variable
 136             VarSet delta( size_t i ) const {
 137                 return Delta( i ) / vars[i];
 138             }
 139
 140             /// Erases all clusters that contain n where n is the variable with index i
 141             ClusterGraph& eraseSubsuming( size_t i ) {
 142                 while( G.nb1(i).size() ) {
 143                     clusters.erase( clusters.begin() + G.nb1(i)[0] );
 144                     G.erase2( G.nb1(i)[0] );
 145                 }
 146                 return *this;
 147             }
 148
 149             /// Returns a const reference to the clusters
 150             const std::vector<VarSet> & toVector() const { return clusters; }
 151
 152             /// Calculates cost of eliminating the variable with index i.
 153             /** The cost is measured as "number of added edges in the adjacency graph",
 154              *  where the adjacency graph has the variables as its nodes and
 155              *  connects nodes i1 and i2 iff i1 and i2 occur in some common cluster.
 156              */
 157             size_t eliminationCost( size_t i ) {
 158                 std::vector<size_t> id_n = G.delta1( i );
 159
 160                 size_t cost = 0;
 161
 162                 // for each unordered pair {i1,i2} adjacent to n
 163                 for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
 164                     for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
 165                         // if i1 and i2 are not adjacent, eliminating n would make them adjacent
 166                         if( !adj(id_n[_i1], id_n[_i2]) )
 167                             cost++;
 168                     }
 169
 170                 return cost;
 171             }
 172
 173             /// Performs Variable Elimination without Probs, i.e. only keeping track of
 174             /*  the interactions that are created along the way.
 175              *  \param ElimSeq A set of outer clusters and an elimination sequence
 176              *  \return A set of elimination "cliques"
 177              *  \todo Variable elimination should be implemented generically using a function
 178              *  object that tells you which variable to delete.
 179              */
 180             ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
 181
 182             /// Performs Variable Eliminiation using the MinFill heuristic
 183             ClusterGraph VarElim_MinFill() const;
 184
 185             /// Writes a ClusterGraph to an output stream
 186             friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
 187                 os << cl.toVector();
 188                 return os;
 189             }
 190     };
 191
 192
 193 } // end of namespace dai
 194
 195
 196 #endif