Fixed testem failure caused by rounding error
[libdai.git] / include / dai / daialg.h
index fdb0ee7..91d36af 100644 (file)
@@ -1,6 +1,7 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
-    Radboud University Nijmegen, The Netherlands
-    
+/*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
+    Radboud University Nijmegen, The Netherlands /
+    Max Planck Institute for Biological Cybernetics, Germany
+
     This file is part of libDAI.
 
     libDAI is free software; you can redistribute it and/or modify
 */
 
 
+/// \file
+/// \brief Defines abstract base class InfAlg, its descendants DAIAlg<T>, the specializations DAIAlgFG and DAIAlgRG and some generic inference methods.
+/// \todo Improve documentation
+
+
 #ifndef __defined_libdai_daialg_h
 #define __defined_libdai_daialg_h
 
 namespace dai {
 
 
-/// The InfAlg class is the common denominator of the various approximate inference algorithms.
-/// A InfAlg object represents a discrete factorized probability distribution over multiple variables 
-/// together with an inference algorithm.
+/// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
+/** \todo General marginalization functions like calcMarginal now copy a complete InfAlg object. Instead, 
+ *  it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph. 
+ *  Or they can simply be made methods of the general InfAlg class.
+ *  \idea Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().
+ */
 class InfAlg {
     public:
-        /// Clone (virtual copy constructor)
+        /// Virtual desctructor (needed because this class contains virtual functions)
+        virtual ~InfAlg() {}
+
+    public:
+        /// Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor)
         virtual InfAlg* clone() const = 0;
 
-        /// Virtual desctructor
-        // (this is needed because this class contains virtual functions)
-        virtual ~InfAlg() {}
+        /// Returns a pointer to a newly constructed object *this (i.e., virtual default constructor)
+        virtual InfAlg* create() const = 0;
         
         /// Identifies itself for logging purposes
         virtual std::string identify() const = 0;
 
-        /// Get single node belief
+        /// Returns the "belief" (i.e., approximate marginal probability distribution) of a variable
         virtual Factor belief( const Var &n ) const = 0;
 
-        /// Get general belief
+        /// Returns the "belief" (i.e., approximate marginal probability distribution) of a set of variables
         virtual Factor belief( const VarSet &n ) const = 0;
 
-        /// Get all beliefs
+        /// Returns all "beliefs" (i.e., approximate marginal probability distribution) calculated by the algorithm
         virtual std::vector<Factor> beliefs() const = 0;
 
-        /// Get log partition sum
-        virtual Complex logZ() const = 0;
+        /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph)
+        virtual Real logZ() const = 0;
 
-        /// Clear messages and beliefs
+        /// Initializes all data structures of the approximate inference algorithm
+        /** This method should be called at least once before run() is called
+         */
         virtual void init() = 0;
 
-        /// The actual approximate inference algorithm
-        virtual double run() = 0;
-
-        /// Save factor I
-        virtual void saveProb( size_t I ) = 0;
-        /// Save Factors involving ns
-        virtual void saveProbs( const VarSet &ns ) = 0;
+        /// Initializes all data structures corresponding to some set of variables
+        /** This method can be used to do a partial initialization after a part of the factor graph has changed.
+         *  Instead of initializing all data structures, it only initializes those involving the variables in ns.
+         */
+        virtual void init( const VarSet &ns ) = 0;
 
-        /// Restore factor I
-        virtual void undoProb( size_t I ) = 0;
-        /// Restore Factors involving ns
-        virtual void undoProbs( const VarSet &ns ) = 0;
+        /// Runs the approximate inference algorithm
+        /*  Before run() is called the first time, init() should be called.
+         *  If run() returns successfully, the results can be queried using the methods belief(), beliefs() and logZ().
+         */
+        virtual double run() = 0;
 
         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
-        virtual void clamp( const Var & n, size_t i ) = 0;
-
-        /// Return all variables that interact with var(i)
-        virtual VarSet delta( size_t i ) const = 0;
+        virtual void clamp( const Var & n, size_t i, bool backup = false ) = 0;
 
         /// Set all factors interacting with var(i) to 1
-        virtual void makeCavity( size_t i ) = 0;
-
-        /// Get index of variable n
-        virtual size_t findVar( const Var & n ) const = 0;
-
-        /// Get index of first factor involving ns
-        virtual size_t findFactor( const VarSet &ns ) const = 0;
-
-        /// Get number of variables
-        virtual size_t nrVars() const = 0;
+        virtual void makeCavity( size_t i, bool backup = false ) = 0;
 
-        /// Get number of factors
-        virtual size_t nrFactors() const = 0;
+        /// Return maximum difference between single node beliefs in the last pass
+        /// \throw Exception if not implemented/supported
+        virtual double maxDiff() const = 0;
 
-        /// Get const reference to variable i
-        virtual const Var & var(size_t i) const = 0;
+        /// Return number of passes over the factorgraph
+        /// \throw Exception if not implemented/supported
+        virtual size_t Iterations() const = 0;
 
-        /// Get reference to variable i
-        virtual Var & var(size_t i) = 0;
 
-        /// Get const reference to factor I
-        virtual const Factor & factor( size_t I ) const = 0;
+        /// Get reference to underlying FactorGraph
+        virtual FactorGraph &fg() = 0;
 
-        /// Get reference to factor I
-        virtual Factor & factor( size_t I ) = 0;
+        /// Get const reference to underlying FactorGraph
+        virtual const FactorGraph &fg() const = 0;
 
-        /// Factor I has been updated
-        virtual void updatedFactor( size_t I ) = 0;
+        /// Save factor I
+        virtual void backupFactor( size_t I ) = 0;
+        /// Save Factors involving ns
+        virtual void backupFactors( const VarSet &ns ) = 0;
 
-        /// Return maximum difference between beliefs in the last pass
-        virtual double maxDiff() const = 0;
+        /// Restore factor I
+        virtual void restoreFactor( size_t I ) = 0;
+        /// Restore Factors involving ns
+        virtual void restoreFactors( const VarSet &ns ) = 0;
 };
 
 
-template <class T>
-class DAIAlg : public InfAlg, public T {
+/// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
+/** \tparam GRM Should be castable to FactorGraph
+ *  \todo A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should
+ *  store a reference to the graphical model object. This prevents needless copying 
+ *  of (possibly large) data structures. Disadvantage: the caller must not change 
+ *  the graphical model between calls to the inference algorithm (maybe a smart_ptr 
+ *  or some locking mechanism would help here?). 
+ */
+template <class GRM>
+class DAIAlg : public InfAlg, public GRM {
     public:
         /// Default constructor
-        DAIAlg() : InfAlg(), T() {}
+        DAIAlg() : InfAlg(), GRM() {}
         
-        /// Construct from T
-        DAIAlg( const T &t ) : InfAlg(), T(t) {}
-
-        /// Copy constructor
-        DAIAlg( const DAIAlg & x ) : InfAlg(x), T(x) {}
-
-        /// Save factor I (using T::saveProb)
-        void saveProb( size_t I ) { T::saveProb( I ); }
-        /// Save Factors involving ns (using T::saveProbs)
-        void saveProbs( const VarSet &ns ) { T::saveProbs( ns ); }
-
-        /// Restore factor I (using T::undoProb)
-        void undoProb( size_t I ) { T::undoProb( I ); }
-        /// Restore Factors involving ns (using T::undoProbs)
-        void undoProbs( const VarSet &ns ) { T::undoProbs( ns ); }
-
-        /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
-        void clamp( const Var & n, size_t i ) { T::clamp( n, i ); }
-
-        /// Return all variables that interact with var(i) (using T::delta)
-        VarSet delta( size_t i ) const { return T::delta( i ); }
+        /// Construct from GRM 
+        DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
 
-        /// Set all factors interacting with var(i) to 1 (using T::makeCavity)
-        void makeCavity( size_t i ) { T::makeCavity( i ); }
-
-        /// Get index of variable n (using T::findVar)
-        size_t findVar( const Var & n ) const { return T::findVar(n); }
-
-        /// Get index of first factor involving ns (using T::findFactor)
-        size_t findFactor( const VarSet &ns ) const { return T::findFactor(ns); }
-
-        /// Get number of variables (using T::nrFactors)
-        size_t nrVars() const { return T::nrVars(); }
-
-        /// Get number of factors (using T::nrFactors)
-        size_t nrFactors() const { return T::nrFactors(); }
+        /// Save factor I
+        void backupFactor( size_t I ) { GRM::backupFactor( I ); }
+        /// Save Factors involving ns
+        void backupFactors( const VarSet &ns ) { GRM::backupFactors( ns ); }
 
-        /// Get const reference to variable i (using T::var)
-        const Var & var( size_t i ) const { return T::var(i); }
+        /// Restore factor I
+        void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
+        /// Restore Factors involving ns
+        void restoreFactors( const VarSet &ns ) { GRM::restoreFactors( ns ); }
 
-        /// Get reference to variable i (using T::var)
-        Var & var(size_t i) { return T::var(i); }
+        /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
+        void clamp( const Var & n, size_t i, bool backup = false ) { GRM::clamp( n, i, backup ); }
 
-        /// Get const reference to factor I (using T::factor)
-        const Factor & factor( size_t I ) const { return T::factor(I); }
+        /// Set all factors interacting with var(i) to 1
+        void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
 
-        /// Get reference to factor I (using T::factor)
-        Factor & factor( size_t I ) { return T::factor(I); }
+        /// Get reference to underlying FactorGraph
+        FactorGraph &fg() { return (FactorGraph &)(*this); }
 
-        /// Factor I has been updated (using T::updatedFactor)
-        void updatedFactor( size_t I ) { T::updatedFactor(I); }
+        /// Get const reference to underlying FactorGraph
+        const FactorGraph &fg() const { return (const FactorGraph &)(*this); }
 };
 
 
+/// Base class for inference algorithms that operate on a FactorGraph
 typedef DAIAlg<FactorGraph> DAIAlgFG;
+
+/// Base class for inference algorithms that operate on a RegionGraph
 typedef DAIAlg<RegionGraph> DAIAlgRG;
 
 
-/// Calculate the marginal of obj on ns by clamping 
-/// all variables in ns and calculating logZ for each joined state
 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// nodes in ns and calculating logZ and the beliefs for each state)
 std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// pairs in ns and calculating logZ for each joined state)
 std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate 2nd order interactions of the marginal of obj on ns
 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );