A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph. More...

#include <dai/regiongraph.h>

Inheritance diagram for dai::RegionGraph:

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

	RegionGraph (const FactorGraph &fg, const std::vector< VarSet > &ors, const std::vector< Region > &irs, const std::vector< std::pair< size_t, size_t > > &edges)
	Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges. More...

	RegionGraph (const FactorGraph &fg, const std::vector< VarSet > &cl)
	Constructs a region graph from a factor graph and a vector of outer clusters (CVM style) More...

virtual RegionGraph *	clone () const
	Clone `*this` (virtual copy constructor) More...

Accessors and mutators
size_t	nrORs () const
	Returns number of outer regions. More...

size_t	nrIRs () const
	Returns number of inner regions. More...

const FRegion &	OR (size_t alpha) const
	Returns constant reference to outer region alpha. More...

FRegion &	OR (size_t alpha)
	Returns reference to outer region alpha. More...

const Region &	IR (size_t beta) const
	Returns constant reference to inner region beta. More...

Region &	IR (size_t beta)
	Returns reference to inner region beta. More...

size_t	fac2OR (size_t I) const
	Returns the index of the outer region to which the I 'th factor corresponds. More...

const Neighbors &	nbOR (size_t alpha) const
	Returns constant reference to the neighbors of outer region alpha. More...

const Neighbors &	nbIR (size_t beta) const
	Returns constant reference to the neighbors of inner region beta. More...

const BipartiteGraph &	DAG () const
	Returns DAG structure of the region graph. More...

Queries
bool	checkCountingNumbers () const
	Check whether the counting numbers are valid. More...

Operations
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...

Public Member Functions inherited from dai::FactorGraph
	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...

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

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

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

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

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

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

Protected Member Functions
void	construct (const FactorGraph &fg, const std::vector< VarSet > &ors, const std::vector< Region > &irs, const std::vector< std::pair< size_t, size_t > > &edges)
	Helper function for constructors. More...

void	constructCVM (const FactorGraph &fg, const std::vector< VarSet > &cl, size_t verbose=0)
	Helper function for constructors (CVM style) More...

void	recomputeORs ()
	Recompute all outer regions. More...

void	recomputeORs (const VarSet &vs)
	Recompute all outer regions involving the variables in vs. More...

void	recomputeOR (size_t I)
	Recompute all outer regions involving factor I. More...

void	calcCVMCountingNumbers ()
	Calculates counting numbers of inner regions based upon counting numbers of outer regions. More...

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

std::vector< FRegion >	_ORs
	The outer regions (corresponding to nodes of type 1) More...

std::vector< Region >	_IRs
	The inner regions (corresponding to nodes of type 2) More...

std::vector< size_t >	_fac2OR
	Stores for each factor index the index of the outer region it belongs to. More...

Input/output
virtual void	ReadFromFile (const char *)
	Reads a region graph from a file. More...

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

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

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

std::ostream &	operator<< (std::ostream &os, const RegionGraph &rg)
	Writes a region graph to an output stream. More...

Detailed Description

A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph.

A RegionGraph inherits from a FactorGraph and adds additional structure in the form of a "region graph". Our definition of region graph is inspired by [HAK03], which is less general than the definition given in [YFW05].

The extra structure described by a RegionGraph compared with that described by a FactorGraph is:

a set of outer regions (indexed by ), where each outer region consists of
- a factor defined on a subset of variables
- a counting number
a set of inner regions (indexed by ), where each inner region consists of
- a subset of variables
- a counting number
edges between inner and outer regions

Each factor in the factor graph belongs to an outer region; normally, the factor contents of an outer region would be the product of all the factors that belong to that region.

Idea:

Generalize the definition of region graphs to the one given in [YFW05], i.e., replace the current implementation which uses a BipartiteGraph with one that uses a DAG.

The outer regions are products of factors; right now, this product is constantly cached: changing one factor results in an update of all relevant outer regions. This may not be the most efficient approach; an alternative would be to only precompute the factor products at the start of an inference algorithm - e.g., in init(). This has the additional advantage that FactorGraph e can offer write access to its factors.

Constructor & Destructor Documentation

dai::RegionGraph::RegionGraph ( )

inline

Default constructor.

dai::RegionGraph::RegionGraph	(	const FactorGraph &	fg,
		const std::vector< VarSet > &	ors,
		const std::vector< Region > &	irs,
		const std::vector< std::pair< size_t, size_t > > &	edges
	)

inline

Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges.

The counting numbers for the outer regions are set to 1.

dai::RegionGraph::RegionGraph	(	const FactorGraph &	fg,
		const std::vector< VarSet > &	cl
	)

inline

Constructs a region graph from a factor graph and a vector of outer clusters (CVM style)

The region graph is constructed as in the Cluster Variation Method.

The outer regions have as variable subsets the clusters specified in cl. Each factor in the factor graph fg is assigned to one of the outer regions. Each outer region gets counting number 1.

The inner regions are (repeated) intersections of outer regions. An inner and an outer region are connected if the variables in the inner region form a subset of the variables in the outer region. The counting numbers for the inner regions are calculated by calcCountingNumbers() and satisfy the Moebius formula.

Member Function Documentation

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

inlinevirtual

Clone *this (virtual copy constructor)

Reimplemented from dai::FactorGraph.

size_t dai::RegionGraph::nrORs ( ) const

inline

Returns number of outer regions.

size_t dai::RegionGraph::nrIRs ( ) const

inline

Returns number of inner regions.

const FRegion& dai::RegionGraph::OR ( size_t alpha ) const

inline

Returns constant reference to outer region alpha.

FRegion& dai::RegionGraph::OR ( size_t alpha )

inline

Returns reference to outer region alpha.

const Region& dai::RegionGraph::IR ( size_t beta ) const

inline

Returns constant reference to inner region beta.

Region& dai::RegionGraph::IR ( size_t beta )

inline

Returns reference to inner region beta.

size_t dai::RegionGraph::fac2OR ( size_t I ) const

inline

Returns the index of the outer region to which the I 'th factor corresponds.

const Neighbors& dai::RegionGraph::nbOR ( size_t alpha ) const

inline

Returns constant reference to the neighbors of outer region alpha.

const Neighbors& dai::RegionGraph::nbIR ( size_t beta ) const

inline

Returns constant reference to the neighbors of inner region beta.

const BipartiteGraph& dai::RegionGraph::DAG ( ) const

inline

Returns DAG structure of the region graph.

Note: Currently, the DAG is implemented as a BipartiteGraph; the nodes of type 1 are the outer regions, the nodes of type 2 the inner regions, and edges correspond with arrows from nodes of type 1 to type 2.

bool dai::RegionGraph::checkCountingNumbers ( ) const

Check whether the counting numbers are valid.

Counting numbers are said to be (variable) valid if for each variable $x$ ,

$\sum_{\alpha \ni x} c_\alpha + \sum_{\beta \ni x} c_\beta = 1$

or in words, if the sum of the counting numbers of the regions that contain the variable equals one.

virtual void dai::RegionGraph::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 from dai::FactorGraph.

virtual void dai::RegionGraph::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 from dai::FactorGraph.

virtual void dai::RegionGraph::ReadFromFile ( const char * )

inlinevirtual

Reads a region graph from a file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

virtual void dai::RegionGraph::WriteToFile	(	const char *	,
		size_t	= `15`
	)		const

inlinevirtual

Writes a region graph to a file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

std::string dai::RegionGraph::toString ( ) const

inline

Formats a region graph as a string.

virtual void dai::RegionGraph::printDot ( std::ostream & ) const

inlinevirtual

Writes a region graph to a GraphViz .dot file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

void dai::RegionGraph::construct	(	const FactorGraph &	fg,
		const std::vector< VarSet > &	ors,
		const std::vector< Region > &	irs,
		const std::vector< std::pair< size_t, size_t > > &	edges
	)

protected

Helper function for constructors.

void dai::RegionGraph::constructCVM	(	const FactorGraph &	fg,
		const std::vector< VarSet > &	cl,
		size_t	verbose = `0`
	)

protected

Helper function for constructors (CVM style)

void dai::RegionGraph::recomputeORs ( )

protected

Recompute all outer regions.

The factor contents of each outer region is set to the product of the factors belonging to that region.

void dai::RegionGraph::recomputeORs ( const VarSet & vs )

protected

Recompute all outer regions involving the variables in vs.

The factor contents of each outer region involving at least one of the variables in vs is set to the product of the factors belonging to that region.

void dai::RegionGraph::recomputeOR ( size_t I )

protected

Recompute all outer regions involving factor I.

The factor contents of each outer region involving the I 'th factor is set to the product of the factors belonging to that region.

void dai::RegionGraph::calcCVMCountingNumbers ( )

protected

Calculates counting numbers of inner regions based upon counting numbers of outer regions.

The counting numbers of the inner regions are set using the Moebius inversion formula:

$c_\beta := 1 - \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma$

where $\mathrm{an}(\beta)$ are the ancestors of inner region $\beta$ according to the partial ordering induced by the subset relation (i.e., a region is a child of another region if its variables are a subset of the variables of its parent region).

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const RegionGraph &	rg
	)

friend

Writes a region graph to an output stream.

Member Data Documentation

BipartiteGraph dai::RegionGraph::_G

protected

Stores the neighborhood structure.

std::vector<FRegion> dai::RegionGraph::_ORs

protected

The outer regions (corresponding to nodes of type 1)

std::vector<Region> dai::RegionGraph::_IRs

protected

The inner regions (corresponding to nodes of type 2)

std::vector<size_t> dai::RegionGraph::_fac2OR

protected

Stores for each factor index the index of the outer region it belongs to.

The documentation for this class was generated from the following files:

include/dai/regiongraph.h
src/regiongraph.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Input/output

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation