index f68ea46..863b694 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 the FactorGraph class
+/// \todo Improve documentation
+
+
#ifndef __defined_libdai_factorgraph_h
#define __defined_libdai_factorgraph_h

#include <iostream>
#include <map>
-#include <tr1/unordered_map>
#include <dai/bipgraph.h>
#include <dai/factor.h>

namespace dai {

-bool hasShortLoops( const std::vector<Factor> &P );
-void RemoveShortLoops( std::vector<Factor> &P );
+/// Represents a factor graph.
+/** Both Bayesian Networks and Markov random fields can be represented in a
+ *  unifying representation, called <em>factor graph</em> [\ref KFL01],
+ *  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
+ *  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).
+ *  \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
+ *  real numbers.
+ *
+ *  For a Bayesian network, each factor corresponds to a (conditional)
+ *  probability table, whereas for a Markov random field, each factor
+ *  corresponds to a maximal clique of the undirected graph.
+ *
+ *  Factor graphs explicitly express the factorization structure of the
+ *  corresponding probability distribution.
+ *
+ *  \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
+ *  could also be implemented in the TFactor itself, which could maintain its state
+ *  (ones/delta/full) and act accordingly.
+ */
+class FactorGraph {
+    public:
+        /// Stores the neighborhood structure
+        BipartiteGraph                    G;
+
+        /// Shorthand for BipartiteGraph::Neighbor
+        typedef BipartiteGraph::Neighbor  Neighbor;
+
+        /// Shorthand for BipartiteGraph::Neighbors
+        typedef BipartiteGraph::Neighbors Neighbors;

+        /// Shorthand for BipartiteGraph::Edge
+        typedef BipartiteGraph::Edge      Edge;
+
+        /// Iterator over factors
+        typedef std::vector<Factor>::iterator iterator;
+
+        /// Const iterator over factors
+        typedef std::vector<Factor>::const_iterator const_iterator;
+

-class FactorGraph : public BipartiteGraph<Var,Factor> {
-    protected:
-        std::map<size_t,Prob>    _undoProbs;
-        Prob::NormType           _normtype;
+    private:
+        std::vector<Var>         _vars;
+        std::vector<Factor>      _factors;
+        std::map<size_t,Factor>  _backup;

public:
/// Default constructor
-        FactorGraph() : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {};
-        /// Copy constructor
-        FactorGraph(const FactorGraph & x) : BipartiteGraph<Var,Factor>(x), _undoProbs(), _normtype(x._normtype) {};
-        /// Construct FactorGraph from vector of Factors
+        FactorGraph() : G(), _vars(), _factors(), _backup() {}
+
+        /// Constructs a FactorGraph from a vector of factors
FactorGraph(const std::vector<Factor> &P);
-        // Construct a FactorGraph from given factor and variable iterators
+
+        /// 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)
+         */
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 );
-
-        /// Assignment operator
-        FactorGraph & operator=(const FactorGraph & x) {
-            if(this!=&x) {
-                BipartiteGraph<Var,Factor>::operator=(x);
-                _undoProbs      = x._undoProbs;
-                _normtype       = x._normtype;
-            }
-            return *this;
-        }
+
+        /// Destructor
virtual ~FactorGraph() {}

-        // aliases
-        Var & var(size_t i) { return V1(i); }
-        const Var & var(size_t i) const { return V1(i); }
-        const std::vector<Var> & vars() const { return V1s(); }
-        std::vector<Var> & vars() { return V1s(); }
-        size_t nrVars() const { return V1s().size(); }
-        Factor & factor(size_t I) { return V2(I); }
-        const Factor & factor(size_t I) const { return V2(I); }
-        const std::vector<Factor> & factors() const { return V2s(); }
-        std::vector<Factor> & factors() { return V2s(); }
-        size_t nrFactors() const { return V2s().size(); }
-
-        /// Provides read access to neighbours of variable
-        const _nb_t & nbV( size_t i1 ) const { return nb1(i1); }
-        /// Provides full access to neighbours of variable
-        _nb_t & nbV( size_t i1 ) { return nb1(i1); }
-        /// Provides read access to neighbours of factor
-        const _nb_t & nbF( size_t i2 ) const { return nb2(i2); }
-        /// Provides full access to neighbours of factor
-        _nb_t & nbF( size_t i2 ) { return nb2(i2); }
-
-        size_t findVar(const Var & n) const {
+        /// Clone *this (virtual copy constructor)
+        virtual FactorGraph* clone() const { return new FactorGraph(); }
+
+        /// Create (virtual default constructor)
+        virtual FactorGraph* create() const { return new FactorGraph(*this); }
+
+        /// Returns const reference to i'th variable
+        const Var & var(size_t i) const { return _vars[i]; }
+        /// Returns const reference to all factors
+        const std::vector<Var> & vars() const { return _vars; }
+        /// Returns reference to I'th factor
+        Factor & factor(size_t I) { return _factors[I]; }
+        /// Returns const reference to I'th factor
+        const Factor & factor(size_t I) const { return _factors[I]; }
+        /// Returns const reference to all factors
+        const std::vector<Factor> & factors() const { return _factors; }
+        /// Returns iterator pointing to first factor
+        iterator begin() { return _factors.begin(); }
+        /// Returns const 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
+        const_iterator end() const { return _factors.end(); }
+
+        /// 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
+        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
+        size_t findVar( const Var & n ) const {
size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
assert( i != nrVars() );
return i;
}
+
+        /// Returns a set of indexes corresponding to a set of variables
+        std::set<size_t> findVars( VarSet &ns ) const {
+            std::set<size_t> indexes;
+            for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
+                indexes.insert( findVar( *n ) );
+            return indexes;
+        }
+
+        /// Returns index of the first factor that depends on the variables
size_t findFactor(const VarSet &ns) const {
size_t I;
for( I = 0; I < nrFactors(); I++ )
@@ -99,61 +184,141 @@ class FactorGraph : public BipartiteGraph<Var,Factor> {
return I;
}

-        friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
-        friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
+        /// Return all variables that occur in a factor involving the i'th variable, itself included
+        VarSet Delta( unsigned i ) const;

-        VarSet delta(const Var & n) const;
-        VarSet Delta(const Var & n) const;
-        virtual void makeFactorCavity(size_t I);
-        virtual void makeCavity(const Var & n);
+        /// Return all variables that occur in a factor involving some variable in ns, ns itself included
+        VarSet Delta( const VarSet &ns ) const;

-        long WriteToFile(const char *filename) const;
-        long WriteToDotFile(const char *filename) const;
+        /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
+        VarSet delta( unsigned i ) const;

-        Factor ExactMarginal(const VarSet & x) const;
-        Real ExactlogZ() 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;
+        }

-        virtual void clamp( const Var & n, size_t i );
-
-        bool hasNegatives() const;
-        Prob::NormType NormType() const { return _normtype; }
+        /// Set the content of the I'th factor and make a backup of its old content if backup == true
+        virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
+            assert( newFactor.vars() == factor(I).vars() );
+            if( backup )
+                backupFactor( I );
+            _factors[I] = newFactor;
+        }
+
+        /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == 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 )
+                    backupFactor( fac->first );
+                setFactor( fac->first, fac->second );
+            }
+        }
+
+        /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
+        /** If backup == true, make a backup of all factors that are changed
+         */
+        virtual void clamp( const Var & n, size_t i, bool backup = false );
+
+        /// 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
+         */
+        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
+         */
+        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;
+
+        /// Reads a FactorGraph from a file
+
+        /// Writes a FactorGraph to a file
+        void WriteToFile(const char *filename) 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;

-        virtual void undoProbs( const VarSet &ns );
-        void saveProbs( const VarSet &ns );
-        virtual void undoProb( size_t I );
-        void saveProb( size_t I );
+        /// Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},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()
+         */
+        FactorGraph clamped( const Var & v_i, 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 );

-        bool isConnected() const;
+        /// Restores the I'th Factor from the backup (it should be backed up first)
+        void backupFactor( size_t I );

-        virtual void updatedFactor( 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 );
+
+        // Friends
+        friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
+        friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
+
+        /// @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, neighbours and adjacency matrix)
-        void createGraph( size_t nrEdges );
+        /// Part of constructors (creates edges, neighbors and adjacency matrix)
+        void constructGraph( size_t nrEdges );
};

-// 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)
template<typename FactorInputIterator, typename VarInputIterator>
-FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint, size_t nr_var_hint ) : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {
+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(), _backup() {
size_t nrEdges = 0;
-    V2s().reserve( nr_fact_hint );
+    _factors.reserve( nr_fact_hint );
for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
-        V2s().push_back( *p2 );
-       nrEdges += p2->vars().size();
+        _factors.push_back( *p2 );
+        nrEdges += p2->vars().size();
}
+