include/dai/clustergraph.h

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