Improved documentation of include/dai/factorgraph.h
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 22 Oct 2009 15:53:35 +0000 (17:53 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Thu, 22 Oct 2009 15:53:35 +0000 (17:53 +0200)
OBSOLETE
TODO
include/dai/factorgraph.h
src/factorgraph.cpp

index 04e8972..eb0a311 100644 (file)
--- a/OBSOLETE
+++ b/OBSOLETE
@@ -7,6 +7,7 @@ TProb<T>& TProb<T>::makeZero( T epsilon );
 virtual void InfAlg::clamp( const Var &v, size_t x, bool backup = false ) = 0;
 void DAIAlg<GRM>::clamp( const Var &v, size_t x, bool backup = false );
 virtual void FactorGraph::clamp( const Var &v, size_t x, bool backup = false );
+FactorGraph clamped( const Var &v, size_t x ) const;
 size_t FactorGraph::VV2E(size_t n1, size_t n2) const;
 const Edge& FactorGraph::edge(size_t e) const;
 void FactorGraph::indexEdges();
diff --git a/TODO b/TODO
index 0440459..5905916 100644 (file)
--- a/TODO
+++ b/TODO
@@ -2,7 +2,6 @@ To do for the next release (0.2.3):
 
 Improve documentation:
 
-       factorgraph.h
        clustergraph.h
        regiongraph.h
        properties.h
index 37da11c..b0551d0 100644 (file)
@@ -11,7 +11,6 @@
 
 /// \file
 /// \brief Defines the FactorGraph class
-/// \todo Improve documentation
 
 
 #ifndef __defined_libdai_factorgraph_h
@@ -33,14 +32,14 @@ namespace dai {
  *  implemented in libDAI by the FactorGraph class.
  *  
  *  Consider a probability distribution over \f$N\f$ discrete random variables
- *  \f$x_0,x_1,\dots,x_N\f$ that factorizes as a product of factors, each of
+ *  \f$x_0,x_1,\dots,x_{N-1}\f$ that factorizes as a product of \f$M\f$ factors, each of
  *  which depends on some subset of the variables:
  *  \f[
- *    P(x_0,x_1,\dots,x_N) = \frac{1}{Z} \prod_{I=0}^M f_I(x_I), \qquad
- *    Z = \sum_{x_0}\dots\sum_{x_N} \prod_{I=0}^M f_I(X_I).
+ *    P(x_0,x_1,\dots,x_{N-1}) = \frac{1}{Z} \prod_{I=0}^{M-1} f_I(x_I), \qquad
+ *    Z = \sum_{x_0}\dots\sum_{x_{N-1}} \prod_{I=0}^{M-1} f_I(X_I).
  *  \f]
  *  Each factor \f$f_I\f$ is a function from an associated subset
- *  of variables \f$X_I \subset \{x_0,x_1,\dots,x_N\}\f$ to the nonnegative
+ *  of variables \f$X_I \subset \{x_0,x_1,\dots,x_{N-1}\}\f$ to the nonnegative
  *  real numbers.
  * 
  *  For a Bayesian network, each factor corresponds to a (conditional)
@@ -48,7 +47,13 @@ namespace dai {
  *  corresponds to a maximal clique of the undirected graph.
  *
  *  Factor graphs explicitly express the factorization structure of the
- *  corresponding probability distribution.
+ *  corresponding probability distribution. A factor graph is a bipartite graph,
+ *  containing variable nodes and factor nodes, and an edge between a variable
+ *  node and a factor node if the corresponding factor depends on that variable.
+ *  In libDAI, this structure is represented by a BipartiteGraph. 
+ *
+ *  So basically, a FactorGraph consists of a BipartiteGraph, a vector of Var 's
+ *  and a vector of TFactor 's.
  *
  *  \todo Alternative implementation of undo factor changes: the only things that have to be
  *  undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
@@ -72,26 +77,31 @@ class FactorGraph {
         /// Iterator over factors
         typedef std::vector<Factor>::iterator iterator;
 
-        /// Const iterator over factors
+        /// Constant iterator over factors
         typedef std::vector<Factor>::const_iterator const_iterator;
 
 
     private:
+        /// Stores the variables
         std::vector<Var>         _vars;
+        /// Stores the factors
         std::vector<Factor>      _factors;
+        /// Stores backups of some factors
         std::map<size_t,Factor>  _backup;
 
     public:
+    /// \name Constructors and destructors
+    //@{
         /// Default constructor
         FactorGraph() : G(), _vars(), _factors(), _backup() {}
 
-        /// Constructs a FactorGraph from a vector of factors
-        FactorGraph(const std::vector<Factor> &P);
+        /// Constructs a factor graph from a vector of factors
+        FactorGraph( const std::vector<Factor> &P );
 
-        /// Constructs a FactorGraph from given factor and variable iterators
-        /** \tparam FactorInputIterator Iterator with value_type Factor
-         *  \tparam VarInputIterator Iterator with value_type Var
-         *  \pre 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)
+        /// Constructs a factor graph from given factor and variable iterators
+        /** \tparam FactorInputIterator Iterates over instances of type dai::Factor
+         *  \tparam VarInputIterator Iterates over instances of type Var
+         *  \pre Assumes that the set of variables in [\a var_begin, \a var_end) is the union of the variables in the factors in [\a fact_begin, \a fact_end)
          */
         template<typename FactorInputIterator, typename VarInputIterator>
         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 );
@@ -99,53 +109,61 @@ class FactorGraph {
         /// Destructor
         virtual ~FactorGraph() {}
 
-        /// Clone *this (virtual copy constructor)
+        /// Virtual copy constructor
         virtual FactorGraph* clone() const { return new FactorGraph(); }
+    //@}
 
-        /// Returns const reference to i'th variable
+    /// \name Accessors and mutators
+    //@{ 
+        /// Returns constant reference the \a i 'th variable
         const Var & var(size_t i) const { return _vars[i]; }
-        /// Returns const reference to all factors
+        /// Returns constant reference to all variables
         const std::vector<Var> & vars() const { return _vars; }
-        /// Returns reference to I'th factor
+
+        /// Returns reference to \a I 'th factor
         Factor & factor(size_t I) { return _factors[I]; }
-        /// Returns const reference to I'th factor
+        /// Returns constant reference to \a I 'th factor
         const Factor & factor(size_t I) const { return _factors[I]; }
-        /// Returns const reference to all factors
+        /// Returns constant reference to all factors
         const std::vector<Factor> & factors() const { return _factors; }
+
+        /// Returns constant reference to neighbors of the \a i 'th variable
+        const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
+        /// Returns constant reference to neighbors of the \a I 'th factor
+        const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
+        /// Returns constant reference to the \a _I 'th neighbor of the \a i 'th variable
+        const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
+        /// Returns constant reference to the \a _i 'th neighbor of the \a I 'th factor
+        const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
+    //@}
+
+    /// \name Iterator interface
+    //@{
         /// Returns iterator pointing to first factor
         iterator begin() { return _factors.begin(); }
-        /// Returns const iterator pointing to first factor
+        /// Returns constant iterator pointing to first factor
         const_iterator begin() const { return _factors.begin(); }
         /// Returns iterator pointing beyond last factor
         iterator end() { return _factors.end(); }
-        /// Returns const iterator pointing beyond last factor
+        /// Returns constant iterator pointing beyond last factor
         const_iterator end() const { return _factors.end(); }
+    //@}
 
+    /// \name Queries
+    //@{
         /// Returns number of variables
         size_t nrVars() const { return vars().size(); }
         /// Returns number of factors
         size_t nrFactors() const { return factors().size(); }
         /// Calculates number of edges
+        /** \note Time complexity: O(nrVars())
+         */
         size_t nrEdges() const { return G.nrEdges(); }
 
-        /// Provides read access to neighbors of variable
-        const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
-        /// Provides full access to neighbors of variable
-        Neighbors & nbV( size_t i ) { return G.nb1(i); }
-        /// Provides read access to neighbors of factor
-        const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
-        /// Provides full access to neighbors of factor
-        Neighbors & nbF( size_t I ) { return G.nb2(I); }
-        /// Provides read access to neighbor of variable
-        const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
-        /// Provides full access to neighbor of variable
-        Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
-        /// Provides read access to neighbor of factor
-        const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
-        /// Provides full access to neighbor of factor
-        Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
-
         /// Returns the index of a particular variable
+        /** \note Time complexity: O(nrVars())
+         *  \throw OBJECT_NOT_FOUND if the variable is not part of this factor graph
+         */
         size_t findVar( const Var &n ) const {
             size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
             if( i == nrVars() )
@@ -154,6 +172,9 @@ class FactorGraph {
         }
 
         /// Returns a set of indexes corresponding to a set of variables
+        /** \note Time complexity: O( nrVars() * ns.size() )
+         *  \throw OBJECT_NOT_FOUND if one of the variables is not part of this factor graph
+         */
         std::set<size_t> findVars( VarSet &ns ) const {
             std::set<size_t> indexes;
             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
@@ -162,6 +183,9 @@ class FactorGraph {
         }
 
         /// Returns index of the first factor that depends on the variables
+        /** \note Time complexity: O(nrFactors())
+         *  \throw OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables
+         */
         size_t findFactor( const VarSet &ns ) const {
             size_t I;
             for( I = 0; I < nrFactors(); I++ )
@@ -172,21 +196,39 @@ class FactorGraph {
             return I;
         }
 
-        /// Return all variables that occur in a factor involving the i'th variable, itself included
-        VarSet Delta( unsigned i ) const;
+        /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
+        VarSet Delta( size_t i ) const;
 
-        /// Return all variables that occur in a factor involving some variable in ns, ns itself included
-        VarSet Delta( const VarSet &ns ) const;
+        /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
+        VarSet Delta( const VarSet &vs ) const;
 
-        /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
-        VarSet delta( unsigned i ) const;
+        /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
+        VarSet delta( size_t i ) const;
 
-        /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
-        VarSet delta( const VarSet & ns ) const {
-            return Delta( ns ) / ns;
+        /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
+        VarSet delta( const VarSet &vs ) const {
+            return Delta( vs ) / vs;
         }
 
-        /// Set the content of the I'th factor and make a backup of its old content if backup == true
+        /// Returns \c true if the factor graph is connected
+        bool isConnected() const { return G.isConnected(); }
+
+        /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
+        bool isTree() const { return G.isTree(); }
+
+        /// Returns \c true if each factor depends on at most two variables
+        bool isPairwise() const;
+
+        /// Returns \c true if each variable has only two possible values
+        bool isBinary() const;
+
+        /// Returns the cliques (fully connected subgraphs of the corresponding Markov graph) in this factor graph
+        std::vector<VarSet> Cliques() const;
+    //@}
+
+    /// \name Backup/restore mechanism for factors
+    //@{
+        /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
         virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
             DAI_ASSERT( newFactor.vars() == factor(I).vars() );
             if( backup )
@@ -194,7 +236,7 @@ class FactorGraph {
             _factors[I] = newFactor;
         }
 
-        /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
+        /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
         virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
                 if( backup )
@@ -203,8 +245,48 @@ class FactorGraph {
             }
         }
 
-        /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
-        /** If backup == true, make a backup of all factors that are changed
+        /// Makes a backup of the \a I 'th factor
+        void backupFactor( size_t I );
+
+        /// Restores the \a I 'th factor from the backup (it should be backed up first)
+        void restoreFactor( size_t I );
+
+        /// Backup the factors specified by indices in \a facs
+        virtual void backupFactors( const std::set<size_t> & facs );
+
+        /// Restore all factors to the backup copies
+        virtual void restoreFactors();
+
+        /// Makes a backup of all factors connected to a set of variables
+        void backupFactors( const VarSet &ns );
+
+        /// Restores all factors connected to a set of variables from their backups
+        void restoreFactors( const VarSet &ns );
+    //@}
+
+    /// \name Transformations
+    //@{
+        /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
+        FactorGraph maximalFactors() const;
+
+        /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_v,x}\f$);
+        /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
+         *  and keeps the current one constant, contrary to clamp()
+         */
+        FactorGraph clamped( size_t i, size_t x ) const;
+
+        // OBSOLETE
+        /// Only for backwards compatibility (to be removed soon)
+        FactorGraph clamped( const Var &v, size_t x ) const {
+            std::cerr << "Warning: this FactorGraph::clamped(const Var&,...) interface is obsolete!" << std::endl;
+            return clamped( findVar(v), x );
+        }
+    //@}
+
+    /// \name Operations
+    //@{
+        /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
+        /** If \a backup == \c true, make a backup of all factors that are changed
          */
         virtual void clamp( size_t i, size_t x, bool backup = false );
 
@@ -216,82 +298,56 @@ class FactorGraph {
         }
 
         /// Clamp a variable in a factor graph to have one out of a list of values
-        /** If backup == true, make a backup of all factors that are changed
+        /** If \a backup == \c true, make a backup of all factors that are changed
          */
         void clampVar( size_t i, const std::vector<size_t> &xis, bool backup = false );
 
         /// Clamp a factor in a factor graph to have one out of a list of values
-        /** If backup == true, make a backup of all factors that are changed
+        /** If \a backup == \c true, make a backup of all factors that are changed
          */
         void clampFactor( size_t I, const std::vector<size_t> &xIs, bool backup = false );
 
-        /// Set all factors interacting with the i'th variable 1
-        virtual void makeCavity( unsigned i, bool backup = false );
-
-        /// Backup the factors specified by indices in facs
-        virtual void backupFactors( const std::set<size_t> & facs );
-
-        /// Restore all factors to the backup copies
-        virtual void restoreFactors();
-
-        /// Returns true if the FactorGraph is connected
-        bool isConnected() const { return G.isConnected(); }
-
-        /// Returns true if the FactorGraph is a tree
-        bool isTree() const { return G.isTree(); }
-
-        /// Returns true if each factor depends on at most two variables
-        bool isPairwise() const;
-
-        /// Returns true if each variable has only two possible values
-        bool isBinary() const;
+        /// Set all factors interacting with the \a i 'th variable to 1
+        /** If \a backup == \c true, make a backup of all factors that are changed
+         */
+        virtual void makeCavity( size_t i, bool backup = false );
+    //@}
 
-        /// Reads a FactorGraph from a file
+    /// \name Input/Output
+    //@{
+        /// Reads a factor graph from a file
+        /** \see \ref fileformat
+         */
         void ReadFromFile( const char *filename );
 
-        /// Writes a FactorGraph to a file
+        /// Writes a factor graph to a file
+        /** \see \ref fileformat
+         */
         void WriteToFile( const char *filename, size_t precision=15 ) const;
 
-        /// Writes a FactorGraph to a GraphViz .dot file
-        void printDot( std::ostream& os ) const;
-
-        /// Returns the cliques in this FactorGraph
-        std::vector<VarSet> Cliques() const;
-
-        /// Clamp variable v to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_v,x}\f$);
-        /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
-         *  and keeps the current one constant, contrary to clamp()
+        /// Writes a factor graph to an output stream
+        /** \see \ref fileformat
          */
-        FactorGraph clamped( const Var &v, size_t x ) const;
-
-        /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
-        FactorGraph maximalFactors() const;
-
-        /// Makes a backup of the I'th Factor
-        void restoreFactor( size_t I );
-
-        /// Restores the I'th Factor from the backup (it should be backed up first)
-        void backupFactor( size_t I );
-
-        /// Makes a backup of all factors connected to a set of variables
-        void backupFactors( const VarSet &ns );
-        /// Restores all factors connected to a set of variables from their backups
-        void restoreFactors( const VarSet &ns );
-
-        /// Writes a FactorGraph to an output stream
         friend std::ostream& operator<< (std::ostream &os, const FactorGraph &fg );
-        /// Reads a FactorGraph from an input stream
+
+        /// Reads a factor graph from an input stream
+        /** \see \ref fileformat
+         */
         friend std::istream& operator>> (std::istream &is, FactorGraph &fg );
 
+        /// Writes a factor graph to a GraphViz .dot file
+        void printDot( std::ostream& os ) const;
+    //@}
+
         // OBSOLETE
-        /// @name Backwards compatibility layer (to be removed soon)
-        //@{
+    /// \name Backwards compatibility layer (to be removed soon)
+    //@{
         size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
         const Edge& edge(size_t e) const { return G.edge(e); }
         void indexEdges() { G.indexEdges(); }
         size_t nr_edges() const { return G.nr_edges(); }
         const std::vector<Edge>& edges() const { return G.edges(); }
-        //@}
+    //@}
 
     private:
         /// Part of constructors (creates edges, neighbors and adjacency matrix)
index b5a0ae6..f94586d 100644 (file)
@@ -212,12 +212,12 @@ std::istream& operator>> ( std::istream& is, FactorGraph &fg ) {
 }
 
 
-VarSet FactorGraph::delta( unsigned i ) const {
+VarSet FactorGraph::delta( size_t i ) const {
     return( Delta(i) / var(i) );
 }
 
 
-VarSet FactorGraph::Delta( unsigned i ) const {
+VarSet FactorGraph::Delta( size_t i ) const {
     // calculate Markov Blanket
     VarSet Del;
     foreach( const Neighbor &I, nbV(i) ) // for all neighboring factors I of i
@@ -236,7 +236,7 @@ VarSet FactorGraph::Delta( const VarSet &ns ) const {
 }
 
 
-void FactorGraph::makeCavity( unsigned i, bool backup ) {
+void FactorGraph::makeCavity( size_t i, bool backup ) {
     // fills all Factors that include var(i) with ones
     map<size_t,Factor> newFacs;
     foreach( const Neighbor &I, nbV(i) ) // for all neighboring factors I of i
@@ -306,7 +306,7 @@ void FactorGraph::clamp( size_t i, size_t x, bool backup ) {
     mask[x] = 1.0;
 
     map<size_t, Factor> newFacs;
-    foreach( const BipartiteGraph::Neighbor &I, nbV(i) )
+    foreach( const Neighbor &I, nbV(i) )
         newFacs[I] = factor(I) * mask;
     setFactors( newFacs, backup );
 
@@ -324,7 +324,7 @@ void FactorGraph::clampVar( size_t i, const vector<size_t> &is, bool backup ) {
     }
 
     map<size_t, Factor> newFacs;
-    foreach( const BipartiteGraph::Neighbor &I, nbV(i) )
+    foreach( const Neighbor &I, nbV(i) )
         newFacs[I] = factor(I) * mask_n;
     setFactors( newFacs, backup );
 }
@@ -410,7 +410,8 @@ bool FactorGraph::isBinary() const {
 }
 
 
-FactorGraph FactorGraph::clamped( const Var &v, size_t state ) const {
+FactorGraph FactorGraph::clamped( size_t i, size_t state ) const {
+    Var v = var( i );
     Real zeroth_order = 1.0;
     vector<Factor> clamped_facs;
     for( size_t I = 0; I < nrFactors(); I++ ) {