include/dai/factorgraph.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
   2     Radboud University Nijmegen, The Netherlands
   3
   4     This file is part of libDAI.
   5
   6     libDAI is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     libDAI is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with libDAI; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19 */
  20
  21
  22 #ifndef __defined_libdai_factorgraph_h
  23 #define __defined_libdai_factorgraph_h
  24
  25
  26 #include <iostream>
  27 #include <map>
  28 #include <tr1/unordered_map>
  29 #include <dai/bipgraph.h>
  30 #include <dai/factor.h>
  31
  32
  33 namespace dai {
  34
  35
  36 bool hasShortLoops( const std::vector<Factor> &P );
  37 void RemoveShortLoops( std::vector<Factor> &P );
  38
  39
  40 class FactorGraph {
  41     public:
  42         BipartiteGraph         G;
  43         std::vector<Var>       vars;
  44         std::vector<Factor>    factors;
  45         typedef BipartiteGraph::Neighbor  Neighbor;
  46         typedef BipartiteGraph::Neighbors Neighbors;
  47
  48     protected:
  49         std::map<size_t,Prob>  _undoProbs;
  50         Prob::NormType         _normtype;
  51
  52     public:
  53         /// Default constructor
  54         FactorGraph() : G(), vars(), factors(), _undoProbs(), _normtype(Prob::NORMPROB) {};
  55         /// Copy constructor
  56         FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), factors(x.factors), _undoProbs(x._undoProbs), _normtype(x._normtype) {};
  57         /// Construct FactorGraph from vector of Factors
  58         FactorGraph(const std::vector<Factor> &P);
  59         // Construct a FactorGraph from given factor and variable iterators
  60         template<typename FactorInputIterator, typename VarInputIterator>
  61         FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint = 0, size_t nr_var_hint = 0 );
  62
  63         /// Assignment operator
  64         FactorGraph & operator=(const FactorGraph & x) {
  65             if( this != &x ) {
  66                 G          = x.G;
  67                 vars       = x.vars;
  68                 factors    = x.factors;
  69                 _undoProbs = x._undoProbs;
  70                 _normtype  = x._normtype;
  71             }
  72             return *this;
  73         }
  74         virtual ~FactorGraph() {}
  75
  76         // aliases
  77         Var & var(size_t i) { return vars[i]; }
  78         const Var & var(size_t i) const { return vars[i]; }
  79         Factor & factor(size_t I) { return factors[I]; }
  80         const Factor & factor(size_t I) const { return factors[I]; }
  81
  82         size_t nrVars() const { return vars.size(); }
  83         size_t nrFactors() const { return factors.size(); }
  84         size_t nrEdges() const { return G.nrEdges(); }
  85
  86         /// Provides read access to neighbors of variable
  87         const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
  88         /// Provides full access to neighbors of variable
  89         Neighbors & nbV( size_t i ) { return G.nb1(i); }
  90         /// Provides read access to neighbors of factor
  91         const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
  92         /// Provides full access to neighbors of factor
  93         Neighbors & nbF( size_t I ) { return G.nb2(I); }
  94         /// Provides read access to neighbor of variable
  95         const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
  96         /// Provides full access to neighbor of variable
  97         Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
  98         /// Provides read access to neighbor of factor
  99         const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
 100         /// Provides full access to neighbor of factor
 101         Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
 102
 103         size_t findVar(const Var & n) const {
 104             size_t i = find( vars.begin(), vars.end(), n ) - vars.begin();
 105             assert( i != nrVars() );
 106             return i;
 107         }
 108         size_t findFactor(const VarSet &ns) const {
 109             size_t I;
 110             for( I = 0; I < nrFactors(); I++ )
 111                 if( factor(I).vars() == ns )
 112                     break;
 113             assert( I != nrFactors() );
 114             return I;
 115         }
 116
 117         friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
 118         friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
 119
 120         VarSet delta( unsigned i ) const;
 121         VarSet Delta( unsigned i ) const;
 122         virtual void makeCavity( unsigned i );
 123
 124         long ReadFromFile(const char *filename);
 125         long WriteToFile(const char *filename) const;
 126         long WriteToDotFile(const char *filename) const;
 127
 128         virtual void clamp( const Var & n, size_t i );
 129
 130         bool hasNegatives() const;
 131         Prob::NormType NormType() const { return _normtype; }
 132
 133         std::vector<VarSet> Cliques() const;
 134
 135         virtual void undoProbs( const VarSet &ns );
 136         void saveProbs( const VarSet &ns );
 137         virtual void undoProb( size_t I );
 138         void saveProb( size_t I );
 139
 140         virtual void updatedFactor( size_t /*I*/ ) {};
 141
 142     private:
 143         /// Part of constructors (creates edges, neighbors and adjacency matrix)
 144         void createGraph( size_t nrEdges );
 145 };
 146
 147
 148 // assumes that the set of variables in [var_begin,var_end) is the union of the variables in the factors in [fact_begin, fact_end)
 149 template<typename FactorInputIterator, typename VarInputIterator>
 150 FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint, size_t nr_var_hint ) : G(), _undoProbs(), _normtype(Prob::NORMPROB) {
 151     // add factors
 152     size_t nrEdges = 0;
 153     factors.reserve( nr_fact_hint );
 154     for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
 155         factors.push_back( *p2 );
 156         nrEdges += p2->vars().size();
 157     }
 158
 159     // add variables
 160     vars.reserve( nr_var_hint );
 161     for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
 162         vars.push_back( *p1 );
 163
 164     // create graph structure
 165     createGraph( nrEdges );
 166 }
 167
 168
 169 } // end of namespace dai
 170
 171
 172 #endif