Represents a factor graph. More...

#include <dai/factorgraph.h>

Inheritance diagram for dai::FactorGraph:

Public Member Functions
Constructors and destructors
	FactorGraph ()
	Default constructor. More...

	FactorGraph (const std::vector< Factor > &P)
	Constructs a factor graph from a vector of factors. More...

template<typename FactorInputIterator , typename VarInputIterator >
	FactorGraph (FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint=0, size_t nrVarHint=0)
	Constructs a factor graph from given factor and variable iterators. More...

virtual	~FactorGraph ()
	Destructor. More...

virtual FactorGraph *	clone () const
	Virtual copy constructor. More...

Accessors and mutators
const Var &	var (size_t i) const
	Returns constant reference the i 'th variable. More...

const std::vector< Var > &	vars () const
	Returns constant reference to all variables. More...

const Factor &	factor (size_t I) const
	Returns constant reference to I 'th factor. More...

const std::vector< Factor > &	factors () const
	Returns constant reference to all factors. More...

const Neighbors &	nbV (size_t i) const
	Returns constant reference to neighbors of the i 'th variable. More...

const Neighbors &	nbF (size_t I) const
	Returns constant reference to neighbors of the I 'th factor. More...

const Neighbor &	nbV (size_t i, size_t _I) const
	Returns constant reference to the _I 'th neighbor of the i 'th variable. More...

const Neighbor &	nbF (size_t I, size_t _i) const
	Returns constant reference to the _i 'th neighbor of the I 'th factor. More...

Queries
const BipartiteGraph &	bipGraph () const
	Returns neighborhood structure. More...

size_t	nrVars () const
	Returns number of variables. More...

size_t	nrFactors () const
	Returns number of factors. More...

size_t	nrEdges () const
	Calculates number of edges. More...

size_t	findVar (const Var &n) const
	Returns the index of a particular variable. More...

SmallSet< size_t >	findVars (const VarSet &ns) const
	Returns a set of indexes corresponding to a set of variables. More...

size_t	findFactor (const VarSet &ns) const
	Returns index of the first factor that depends on the variables. More...

VarSet	inds2vars (const std::vector< size_t > &inds) const
	Returns the VarSet corresponding to a vector of variable indices. More...

VarSet	Delta (size_t i) const
	Return all variables that occur in a factor involving the i 'th variable, itself included. More...

VarSet	Delta (const VarSet &vs) const
	Return all variables that occur in a factor involving some variable in vs, vs itself included. More...

VarSet	delta (size_t i) const
	Return all variables that occur in a factor involving the i 'th variable, itself excluded. More...

VarSet	delta (const VarSet &vs) const
	Return all variables that occur in a factor involving some variable in vs, vs itself excluded. More...

SmallSet< size_t >	Deltai (size_t i) const
	Return all the indices of variables that occur in a factor involving the i 'th variable, itself included. More...

SmallSet< size_t >	deltai (size_t i) const
	Return all the indices of variables that occur in a factor involving the i 'th variable, itself excluded. More...

bool	isConnected () const
	Returns `true` if the factor graph is connected. More...

bool	isTree () const
	Returns `true` if the factor graph is a tree (i.e., has no cycles and is connected) More...

bool	isPairwise () const
	Returns `true` if each factor depends on at most two variables. More...

bool	isBinary () const
	Returns `true` if each variable has only two possible values. More...

GraphAL	MarkovGraph () const
	Constructs the corresponding Markov graph. More...

bool	isMaximal (size_t I) const
	Returns whether the I 'th factor is maximal. More...

size_t	maximalFactor (size_t I) const
	Returns the index of a maximal factor that contains the I 'th factor. More...

std::vector< VarSet >	maximalFactorDomains () const
	Returns the maximal factor domains in this factorgraph. More...

Real	logScore (const std::vector< size_t > &statevec) const
	Evaluates the log score (i.e., minus the energy) of the joint configuration statevec. More...

Backup/restore mechanism for factors
virtual void	setFactor (size_t I, const Factor &newFactor, bool backup=false)
	Set the content of the I 'th factor and make a backup of its old content if backup == `true`. More...

virtual void	setFactors (const std::map< size_t, Factor > &facs, bool backup=false)
	Set the contents of all factors as specified by facs and make a backup of the old contents if backup == `true`. More...

void	backupFactor (size_t I)
	Makes a backup of the I 'th factor. More...

void	restoreFactor (size_t I)
	Restores the I 'th factor from the backup (it should be backed up first) More...

virtual void	backupFactors (const std::set< size_t > &facs)
	Backup the factors specified by indices in facs. More...

virtual void	restoreFactors ()
	Restore all factors to the backup copies. More...

void	backupFactors (const VarSet &ns)
	Makes a backup of all factors connected to a set of variables. More...

void	restoreFactors (const VarSet &ns)
	Restores all factors connected to a set of variables from their backups. More...

Transformations
FactorGraph	maximalFactors () const
	Returns a copy of `*this`, where all factors that are subsumed by some larger factor are merged with the larger factors. More...

FactorGraph	clamped (size_t i, size_t x) const
	Returns a copy of `*this`, where the i 'th variable has been clamped to value x. More...

Operations
virtual void	clamp (size_t i, size_t x, bool backup=false)
	Clamp the i 'th variable to value x (i.e. multiply with a Kronecker delta $\delta_{x_i, x}$ ) More...

void	clampVar (size_t i, const std::vector< size_t > &xis, bool backup=false)
	Clamp a variable in a factor graph to have one out of a list of values. More...

void	clampFactor (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. More...

virtual void	makeCavity (size_t i, bool backup=false)
	Set all factors interacting with the i 'th variable to 1. More...

virtual void	makeRegionCavity (std::vector< size_t > facInds, bool backup)
	Set all factors indexed by facInds to 1. More...

Private Member Functions
void	constructGraph (size_t nrEdges)
	Part of constructors (creates edges, neighbors and adjacency matrix) More...

Private Attributes
BipartiteGraph	_G
	Stores the neighborhood structure. More...

std::vector< Var >	_vars
	Stores the variables. More...

std::vector< Factor >	_factors
	Stores the factors. More...

std::map< size_t, Factor >	_backup
	Stores backups of some factors. More...

Input/Output
virtual void	ReadFromFile (const char *filename)
	Reads a factor graph from a file. More...

virtual void	WriteToFile (const char *filename, size_t precision=15) const
	Writes a factor graph to a file. More...

virtual void	printDot (std::ostream &os) const
	Writes a factor graph to a GraphViz .dot file. More...

std::string	toString () const
	Formats a factor graph as a string. More...

void	fromString (const std::string &s)
	Reads a factor graph from a string. More...

std::ostream &	operator<< (std::ostream &os, const FactorGraph &fg)
	Writes a factor graph to an output stream. More...

std::istream &	operator>> (std::istream &is, FactorGraph &fg)
	Reads a factor graph from an input stream. More...

Detailed Description

Represents a factor graph.

Both Bayesian Networks and Markov random fields can be represented in a unifying representation, called factor graph [KFL01], implemented in libDAI by the FactorGraph class.

Consider a probability distribution over $N$ discrete random variables $x_0,x_1,\dots,x_{N-1}$ that factorizes as a product of $M$ factors, each of which depends on some subset of the variables:

$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).$

Each factor $f_I$ is a function from an associated subset of variables $X_I \subset \{x_0,x_1,\dots,x_{N-1}\}$ 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. 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.

Idea:: 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. Update: it seems that the proposed functionality would not be enough for CBP, for which it would make more sense to add more levels of backup/restore.

Todo:: Write a method that applies evidence (should we represent evidence as a map<Var,size_t> or as a map<size_t,size_t>?)

Examples:: example.cpp, example_imagesegmentation.cpp, example_sprinkler.cpp, example_sprinkler_em.cpp, and uai2010-aie-solver.cpp.

Constructor & Destructor Documentation

dai::FactorGraph::FactorGraph ( )

inline

Default constructor.

dai::FactorGraph::FactorGraph ( const std::vector< Factor > & P )

Constructs a factor graph from a vector of factors.

template<typename FactorInputIterator , typename VarInputIterator >

dai::FactorGraph::FactorGraph	(	FactorInputIterator	facBegin,
		FactorInputIterator	facEnd,
		VarInputIterator	varBegin,
		VarInputIterator	varEnd,
		size_t	nrFacHint = `0`,
		size_t	nrVarHint = `0`
	)

Constructs a factor graph from given factor and variable iterators.

Template Parameters

FactorInputIterator	Iterates over instances of type dai::Factor
VarInputIterator	Iterates over instances of type Var

Precondition: Assumes that the set of variables in [varBegin, varEnd) is the union of the variables in the factors in [facBegin, facEnd)

virtual dai::FactorGraph::~FactorGraph ( )

inlinevirtual

Destructor.

Member Function Documentation

virtual FactorGraph* dai::FactorGraph::clone ( ) const

inlinevirtual

Virtual copy constructor.

Reimplemented in dai::RegionGraph, and dai::CobwebGraph.

const Var& dai::FactorGraph::var ( size_t i ) const

inline

Returns constant reference the i 'th variable.

Examples:: example.cpp.

const std::vector<Var>& dai::FactorGraph::vars ( ) const

inline

Returns constant reference to all variables.

const Factor& dai::FactorGraph::factor ( size_t I ) const

inline

Returns constant reference to I 'th factor.

Examples:: example.cpp, and example_sprinkler.cpp.

const std::vector<Factor>& dai::FactorGraph::factors ( ) const

inline

Returns constant reference to all factors.

const Neighbors& dai::FactorGraph::nbV ( size_t i ) const

inline

Returns constant reference to neighbors of the i 'th variable.

const Neighbors& dai::FactorGraph::nbF ( size_t I ) const

inline

Returns constant reference to neighbors of the I 'th factor.

const Neighbor& dai::FactorGraph::nbV	(	size_t	i,
		size_t	_I
	)		const

inline

Returns constant reference to the _I 'th neighbor of the i 'th variable.

const Neighbor& dai::FactorGraph::nbF	(	size_t	I,
		size_t	_i
	)		const

inline

Returns constant reference to the _i 'th neighbor of the I 'th factor.

const BipartiteGraph& dai::FactorGraph::bipGraph ( ) const

inline

Returns neighborhood structure.

size_t dai::FactorGraph::nrVars ( ) const

inline

Returns number of variables.

Examples:: example.cpp, example_imagesegmentation.cpp, and example_sprinkler.cpp.

size_t dai::FactorGraph::nrFactors ( ) const

inline

Returns number of factors.

Examples:: example.cpp, and example_sprinkler.cpp.

size_t dai::FactorGraph::nrEdges ( ) const

inline

Calculates number of edges.

Note: Time complexity: O(nrVars())

size_t dai::FactorGraph::findVar ( const Var & n ) const

inline

Returns the index of a particular variable.

Note: Time complexity: O(nrVars())

Exceptions

OBJECT_NOT_FOUND if the variable is not part of this factor graph

SmallSet<size_t> dai::FactorGraph::findVars ( const VarSet & ns ) const

inline

Returns a set of indexes corresponding to a set of variables.

Note: Time complexity: O( nrVars() * ns.size() )

Exceptions

OBJECT_NOT_FOUND if one of the variables is not part of this factor graph

size_t dai::FactorGraph::findFactor ( const VarSet & ns ) const

inline

Returns index of the first factor that depends on the variables.

Note: Time complexity: O(nrFactors())

Exceptions

OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables

VarSet dai::FactorGraph::inds2vars ( const std::vector< size_t > & inds ) const

inline

Returns the VarSet corresponding to a vector of variable indices.

VarSet dai::FactorGraph::Delta ( size_t i ) const

Return all variables that occur in a factor involving the i 'th variable, itself included.

VarSet dai::FactorGraph::Delta ( const VarSet & vs ) const

Return all variables that occur in a factor involving some variable in vs, vs itself included.

VarSet dai::FactorGraph::delta ( size_t i ) const

inline

Return all variables that occur in a factor involving the i 'th variable, itself excluded.

VarSet dai::FactorGraph::delta ( const VarSet & vs ) const

inline

Return all variables that occur in a factor involving some variable in vs, vs itself excluded.

SmallSet< size_t > dai::FactorGraph::Deltai ( size_t i ) const

Return all the indices of variables that occur in a factor involving the i 'th variable, itself included.

SmallSet<size_t> dai::FactorGraph::deltai ( size_t i ) const

inline

Return all the indices of variables that occur in a factor involving the i 'th variable, itself excluded.

bool dai::FactorGraph::isConnected ( ) const

inline

Returns true if the factor graph is connected.

bool dai::FactorGraph::isTree ( ) const

inline

Returns true if the factor graph is a tree (i.e., has no cycles and is connected)

bool dai::FactorGraph::isPairwise ( ) const

Returns true if each factor depends on at most two variables.

bool dai::FactorGraph::isBinary ( ) const

Returns true if each variable has only two possible values.

GraphAL dai::FactorGraph::MarkovGraph ( ) const

Constructs the corresponding Markov graph.

Note: The Markov graph has the variables as nodes and an edge between two variables if and only if the variables share a factor.

bool dai::FactorGraph::isMaximal ( size_t I ) const

Returns whether the I 'th factor is maximal.

Note: A factor (domain) is maximal if and only if it is not a strict subset of another factor domain.

size_t dai::FactorGraph::maximalFactor ( size_t I ) const

Returns the index of a maximal factor that contains the I 'th factor.

Note: A factor (domain) is maximal if and only if it is not a strict subset of another factor domain.

vector< VarSet > dai::FactorGraph::maximalFactorDomains ( ) const

Returns the maximal factor domains in this factorgraph.

Note: A factor domain is maximal if and only if it is not a strict subset of another factor domain.

Real dai::FactorGraph::logScore ( const std::vector< size_t > & statevec ) const

Evaluates the log score (i.e., minus the energy) of the joint configuration statevec.

Examples:: example.cpp.

virtual void dai::FactorGraph::setFactor	(	size_t	I,
		const Factor &	newFactor,
		bool	backup = `false`
	)

inlinevirtual

Set the content of the I 'th factor and make a backup of its old content if backup == true.

Reimplemented in dai::RegionGraph.

virtual void dai::FactorGraph::setFactors	(	const std::map< size_t, Factor > &	facs,
		bool	backup = `false`
	)

inlinevirtual

Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true.

Reimplemented in dai::RegionGraph.

void dai::FactorGraph::backupFactor ( size_t I )

Makes a backup of the I 'th factor.

Exceptions

MULTIPLE_UNDO if a backup already exists

void dai::FactorGraph::restoreFactor ( size_t I )

Restores the I 'th factor from the backup (it should be backed up first)

Exceptions

OBJECT_NOT_FOUND if a backup does not exist

void dai::FactorGraph::backupFactors ( const std::set< size_t > & facs )

virtual

Backup the factors specified by indices in facs.

Exceptions

MULTIPLE_UNDO if a backup already exists

void dai::FactorGraph::restoreFactors ( )

virtual

Restore all factors to the backup copies.

void dai::FactorGraph::backupFactors ( const VarSet & ns )

Makes a backup of all factors connected to a set of variables.

Exceptions

MULTIPLE_UNDO if a backup already exists

void dai::FactorGraph::restoreFactors ( const VarSet & ns )

Restores all factors connected to a set of variables from their backups.

FactorGraph dai::FactorGraph::maximalFactors ( ) const

Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.

FactorGraph dai::FactorGraph::clamped	(	size_t	i,
		size_t	x
	)		const

Returns a copy of *this, where the i 'th variable has been clamped to value x.

Note: This version changes the factor graph structure and thus returns a newly constructed FactorGraph and keeps the current one constant, contrary to clamp()

void dai::FactorGraph::clamp	(	size_t	i,
		size_t	x,
		bool	backup = `false`
	)

virtual

Clamp the i 'th variable to value x (i.e. multiply with a Kronecker delta $\delta_{x_i, x}$ )