X-Git-Url: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=include%2Fdai%2Ffactorgraph.h;h=7330e1e95c975b6200d70aa7780393bb0ac74b9f;hp=5ad7c399bcda409c969ed76decd4f29d1daf6a98;hb=76cf77837c617f54202590125c7a566ae443d0ab;hpb=02488112876cc5ccb7f48048ffe1c49937a1a1cf diff --git a/include/dai/factorgraph.h b/include/dai/factorgraph.h index 5ad7c39..7330e1e 100644 --- a/include/dai/factorgraph.h +++ b/include/dai/factorgraph.h @@ -10,8 +10,7 @@ /// \file -/// \brief Defines the FactorGraph class -/// \todo Improve documentation +/// \brief Defines the FactorGraph class, which represents factor graphs (e.g., Bayesian networks or Markov random fields) #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::iterator iterator; - /// Const iterator over factors + /// Constant iterator over factors typedef std::vector::const_iterator const_iterator; private: + /// Stores the variables std::vector _vars; + /// Stores the factors std::vector _factors; + /// Stores backups of some factors std::map _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 &P); + /// Constructs a factor graph from a vector of factors + FactorGraph( const std::vector &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 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 & 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 & 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 findVars( VarSet &ns ) const { std::set 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 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 & facs, bool backup = false ) { for( std::map::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) { if( backup ) @@ -203,95 +245,138 @@ 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 + /** \throw MULTIPLE_UNDO if a backup already exists + */ + 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 + /** \throw MULTIPLE_UNDO if a backup already exists + */ + virtual void backupFactors( const std::set & facs ); + + /// Restore all factors to the backup copies + virtual void restoreFactors(); + + /// Makes a backup of all factors connected to a set of variables + /** \throw MULTIPLE_UNDO if a backup already exists + */ + 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_i,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 + /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v,x}\f$); + /** \deprecated Please use dai::FactorGraph::clamped(size_t,size_t) instead + */ + 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 ); // OBSOLETE - /// Only for backwards compatibility (to be removed soon) + /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$) + /** \deprecated Please use dai::FactorGraph::clamp(size_t,size_t,bool) instead + */ virtual void clamp( const Var &v, size_t x, bool backup = false ) { std::cerr << "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl; clamp( findVar(v), x, backup ); } /// 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 &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 &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 & 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 + /// 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 ); + //@} + + /// \name Input/Output + //@{ + /// Reads a factor graph from a file + /** \see \ref fileformats-factorgraph + * \throw CANNOT_READ_FILE if the file cannot be opened + * \throw INVALID_FACTORGRAPH_FILE if the file is not valid + */ void ReadFromFile( const char *filename ); - /// Writes a FactorGraph to a file + /// Writes a factor graph to a file + /** \see \ref fileformats-factorgraph + * \throw CANNOT_WRITE_FILE if the file cannot be written + */ 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 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 fileformats-factorgraph */ - 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 fileformats-factorgraph + * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid + */ 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) - //@{ - 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); } + /// \name Backwards compatibility layer (to be removed soon) + //@{ + /// Prepare backwards compatibility layer for indexed edges + /** \deprecated Please use FactorGraph::Neighbor interface instead + */ void indexEdges() { G.indexEdges(); } - size_t nr_edges() const { return G.nr_edges(); } + /// Returns edge with index \a e + /** \deprecated Please use FactorGraph::Neighbor interface instead + */ + const Edge& edge(size_t e) const { return G.edge(e); } + /// Returns all edges + /** \deprecated Please use FactorGraph::Neighbor interface instead + */ const std::vector& edges() const { return G.edges(); } - //}@ + /// Converts a pair of node indices to an edge index + /** \deprecated Please use FactorGraph::Neighbor interface instead + */ + size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); } + /// Returns number of edges + /** \deprecated Please use FactorGraph::Neighbor interface instead + */ + size_t nr_edges() const { return G.nr_edges(); } + //@} private: /// Part of constructors (creates edges, neighbors and adjacency matrix)