A CobwebGraph is a special type of region graph used by the GLC algorithm. More...

#include <dai/cobwebgraph.h>

Inheritance diagram for dai::CobwebGraph:

Classes
struct	Connection
	The information in connection between two regions. More...

Public Member Functions
	DAI_ENUM (NeighborType, ALL, TOP, CLOSEST)

Constructors and destructors
	CobwebGraph ()
	Default constructor. More...

	CobwebGraph (const FactorGraph &fg)
	Constructs a cobweb graph from a factor graph. More...

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

Accessors and mutators
size_t	nrCWs () const
	Returns the number of regions. More...

const std::map< VarSet, std::pair< int, std::vector< size_t > > > &	cn (size_t R) const
	Returns constant reference to the _cn for region R. More...

std::map< VarSet, std::pair< int, std::vector< size_t > > > &	cn (size_t R)
	Returns a reference to the _cn for region R. More...

const std::vector< VarSet > &	outM (size_t R) const
	Returns constant reference the vector of domain of all outgoing messages from region R. More...

std::vector< VarSet > &	outM (size_t R)
	Returns reference the vector of domain of all outgoing messages from region R. More...

const VarSet &	outM (size_t R, size_t j) const
	Returns constant reference to the variables in the outgoing message from region R to its j'th neighbor. More...

VarSet &	outM (size_t R, size_t j)
	Returns a reference to the variables in the outgoing message from region R to its j'th neighbor. More...

const SmallSet< size_t > &	Rfs (size_t R) const
	Returns constant reference to the index of factors of region R. More...

SmallSet< size_t > &	Rfs (size_t R)
	Returns reference to the index of factors of region R. More...

const SmallSet< size_t > &	EXRs (size_t R) const
	Returns constant reference to the index of variables on the boundary of region R ( r) More...

SmallSet< size_t > &	EXRs (size_t R)
	Returns reference to the index of variables on the boundary of region R ( r) More...

const SmallSet< size_t > &	INRs (size_t R) const
	Returns constant reference to the index of variables inside region R (r) More...

SmallSet< size_t > &	INRs (size_t R)
	Returns reference to the index of variables inside region R (r) More...

const Connection &	M (size_t R, size_t i) const
	Returns constant reference to the connection structure from region R to its i'th neighbour. More...

Connection &	M (size_t R, size_t i)
	Returns reference to the connection structure from region R to its i'th neighbour. More...

const std::vector< Connection > &	M (size_t R) const
	Returns constant reference to the vector of connection structure from region R to all its neighbours. More...

std::vector< Connection > &	M (size_t R)
	Returns vector of all connections to region R. More...

const std::vector< size_t > &	var2CW (size_t i) const
	Returns the vector of region indices that contain i as internal variable. More...

Operations
void	setRgn (std::vector< SmallSet< size_t > > regions, NeighborType neighbors, bool debugging=false)
	Sets up all the regions and messages. 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...

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

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
bool	checkPartition (const std::vector< SmallSet< size_t > > &regions) const
	The function to check for partitioning. More...

void	setVar2CW ()
	Helper function that sets the regions containing each variable using the values in _INRs. More...

void	setExtnFact ()
	Setup the _INRs, _EXRs and all the factor indices (e.g. Rifs) More...

void	setMSGs (NeighborType neighbors)
	Helper function that setups the msgs (_M, _outM) using the values in _INRs and _EXRs. More...

void	setCountingNumbers (bool debugging=false)
	Sets _cn. More...

void	eraseNonMaximal (std::vector< SmallSet< size_t > > &regions)
	For the given set of variables for each region, removes the regions that are non-maximal. More...

Protected Attributes
std::vector< SmallSet< size_t > >	_INRs
	Vector of variable indices internal to each region (r) More...

std::vector< SmallSet< size_t > >	_EXRs
	Vector of variable indices on the boundary of each region ( r) More...

std::vector< SmallSet< size_t > >	_Rfs
	Index of factors in each region. More...

std::vector< SmallSet< size_t > >	_Rifs
	Index of factors internal to each region, i.e., all its variables are internal to the region. More...

std::vector< SmallSet< size_t > >	_Rxfs
	Index of factors that bridge each region, i.e., not all its variables are internal to the region. More...

std::vector< std::vector< VarSet > >	_outM
	The vector of domain of messages leaving each region ( r_{p,q}) More...

std::vector< std::vector< Connection > >	_M
	Vector of all connections to each region. More...

std::vector< std::vector< size_t > >	_var2CW
	For each i the index of (cobweb) regions that contain variable i. More...

std::vector< std::map< VarSet, std::pair< int, std::vector< size_t > > > >	_cn

bool	isPartition
	Whether a given set of region vars makes a partitioning or not. More...

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

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

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

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

std::ostream &	operator<< (std::ostream &, const CobwebGraph &)
	Writes a cobweb graph to an output stream. More...

Detailed Description

A CobwebGraph is a special type of region graph used by the GLC algorithm.

Author: Siamak Ravanbakhsh

Todo:: Implement unit test for Cobwebgraph

Constructor & Destructor Documentation

dai::CobwebGraph::CobwebGraph ( )

inline

Default constructor.

dai::CobwebGraph::CobwebGraph ( const FactorGraph & fg )

inline

Constructs a cobweb graph from a factor graph.

Member Function Documentation

dai::CobwebGraph::DAI_ENUM	(	NeighborType	,
		ALL	,
		TOP	,
		CLOSEST
	)

Indicates what happens if a subset of variables in the boundary of a region ( r_p) is shared by some neighbors such that one ( r_{p,q1}) is a subset of another ( r_{p,q2}).

ALL all such neighbors are included in the the updates.
TOP only ( r_{p,q2}) is included unless ( r_{p,q2} = r_{p,q1}) in which case both are included
CLOSEST (default): similar to TOP but in case of a tie the the region r_q with largest r_q r_p is considered
Note
Not important in perfomance!

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

inlinevirtual

Clone *this (virtual copy constructor)

Reimplemented from dai::FactorGraph.

size_t dai::CobwebGraph::nrCWs ( ) const

inline

Returns the number of regions.

const std::map<VarSet, std::pair<int,std::vector<size_t> > >& dai::CobwebGraph::cn ( size_t R ) const

inline

Returns constant reference to the _cn for region R.

std::map<VarSet, std::pair<int,std::vector<size_t> > >& dai::CobwebGraph::cn ( size_t R )

inline

Returns a reference to the _cn for region R.

const std::vector<VarSet>& dai::CobwebGraph::outM ( size_t R ) const

inline

Returns constant reference the vector of domain of all outgoing messages from region R.

std::vector<VarSet>& dai::CobwebGraph::outM ( size_t R )

inline

Returns reference the vector of domain of all outgoing messages from region R.

const VarSet& dai::CobwebGraph::outM	(	size_t	R,
		size_t	j
	)		const

inline

Returns constant reference to the variables in the outgoing message from region R to its j'th neighbor.

j corresponds to dual in the connection construct

VarSet& dai::CobwebGraph::outM	(	size_t	R,
		size_t	j
	)

inline

Returns a reference to the variables in the outgoing message from region R to its j'th neighbor.

j corresponds to dual in the connection construct

const SmallSet<size_t>& dai::CobwebGraph::Rfs ( size_t R ) const

inline

Returns constant reference to the index of factors of region R.

SmallSet<size_t>& dai::CobwebGraph::Rfs ( size_t R )

inline

Returns reference to the index of factors of region R.

const SmallSet<size_t>& dai::CobwebGraph::EXRs ( size_t R ) const

inline

Returns constant reference to the index of variables on the boundary of region R ( r)

SmallSet<size_t>& dai::CobwebGraph::EXRs ( size_t R )

inline

Returns reference to the index of variables on the boundary of region R ( r)

const SmallSet<size_t>& dai::CobwebGraph::INRs ( size_t R ) const

inline

Returns constant reference to the index of variables inside region R (r)

SmallSet<size_t>& dai::CobwebGraph::INRs ( size_t R )

inline

Returns reference to the index of variables inside region R (r)

const Connection& dai::CobwebGraph::M	(	size_t	R,
		size_t	i
	)		const

inline

Returns constant reference to the connection structure from region R to its i'th neighbour.

Connection& dai::CobwebGraph::M	(	size_t	R,
		size_t	i
	)

inline

Returns reference to the connection structure from region R to its i'th neighbour.

const std::vector<Connection>& dai::CobwebGraph::M ( size_t R ) const

inline

Returns constant reference to the vector of connection structure from region R to all its neighbours.

std::vector<Connection>& dai::CobwebGraph::M ( size_t R )

inline

Returns vector of all connections to region R.

const std::vector<size_t>& dai::CobwebGraph::var2CW ( size_t i ) const

inline

Returns the vector of region indices that contain i as internal variable.

void dai::CobwebGraph::setRgn	(	std::vector< SmallSet< size_t > >	regions,
		NeighborType	neighbors,
		bool	debugging = `false`
	)

Sets up all the regions and messages.

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

inlinevirtual

Reads a cobweb graph from a file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

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

inlinevirtual

Writes a cobweb graph to a file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

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

inline

Formats a cobweb graph as a string.

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

inlinevirtual

Writes a cobweb graph to a GraphViz .dot file.

Note: Not implemented yet

Reimplemented from dai::FactorGraph.

bool dai::CobwebGraph::checkPartition ( const std::vector< SmallSet< size_t > > & regions ) const

protected

The function to check for partitioning.

void dai::CobwebGraph::setVar2CW ( )

protected

Helper function that sets the regions containing each variable using the values in _INRs.

void dai::CobwebGraph::setExtnFact ( )

protected

Setup the _INRs, _EXRs and all the factor indices (e.g. Rifs)

void dai::CobwebGraph::setMSGs ( NeighborType neighbors )

protected

Helper function that setups the msgs (_M, _outM) using the values in _INRs and _EXRs.

void dai::CobwebGraph::setCountingNumbers ( bool debugging = false )

protected

Sets _cn.

void dai::CobwebGraph::eraseNonMaximal ( std::vector< SmallSet< size_t > > & regions )

protected

For the given set of variables for each region, removes the regions that are non-maximal.

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	,
		const CobwebGraph &
	)

friend

Writes a cobweb graph to an output stream.

Member Data Documentation

std::vector<SmallSet<size_t> > dai::CobwebGraph::_INRs

protected

Vector of variable indices internal to each region (r)

std::vector<SmallSet<size_t> > dai::CobwebGraph::_EXRs

protected

Vector of variable indices on the boundary of each region ( r)

std::vector<SmallSet<size_t> > dai::CobwebGraph::_Rfs

protected

Index of factors in each region.

std::vector<SmallSet<size_t> > dai::CobwebGraph::_Rifs

protected

Index of factors internal to each region, i.e., all its variables are internal to the region.

std::vector<SmallSet<size_t> > dai::CobwebGraph::_Rxfs

protected

Index of factors that bridge each region, i.e., not all its variables are internal to the region.

std::vector<std::vector<VarSet> > dai::CobwebGraph::_outM

protected

The vector of domain of messages leaving each region ( r_{p,q})

std::vector<std::vector<Connection> > dai::CobwebGraph::_M

protected

Vector of all connections to each region.

std::vector<std::vector<size_t> > dai::CobwebGraph::_var2CW

protected

For each i the index of (cobweb) regions that contain variable i.

std::vector<std::map<VarSet, std::pair<int,std::vector<size_t> > > > dai::CobwebGraph::_cn

protected

For each region r_p a mapping from all variables rho in its msg-region graph to a pair: first: counting number second: the index of top-regions that contain rho

bool dai::CobwebGraph::isPartition

protected

Whether a given set of region vars makes a partitioning or not.

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

include/dai/cobwebgraph.h
src/cobwebgraph.cpp

Classes

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