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