// blabla
}
A disadvantage of this approach may be worse cachability.
+A problem is if there are nog properties for nodes (type 1), nodes (type 2)
+or edges. Maybe this can be solved using specializations, or using variadac
+template arguments or something similar?
- BipartiteGraph::isConnected should be optimized.
- http://www.boost.org/development/requirements.html#Design_and_Programming
- Would it be a good idea to cache second-order neighborhoods (delta's) in BipGraph?
No, a better idea is to avoid calls to findVar() as much as possible.
- Can the FactorGraph constructors be optimized further?
- Remove x2x?
+- Add iterations (like maxdiff, but counts iterations) to some algorithms
+- A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should store a
+reference to it
TODO FOR RELEASE:
- Test Visual C++ compatibility
prob.h
factorgraph.h
factorgraph.cpp
+regiongraph.h
+regiongraph.cpp
+daialg.h
+daialg.cpp
FILES IN SVN HEAD THAT ARE STILL RELEVANT:
ChangeLog
README
TODO
-regiongraph.h
-regiongraph.cpp
-daialg.h
-daialg.cpp
bp.h
bp.cpp
BP() : DAIAlgFG(), edges(), props(), maxdiff(0.0) {};
/// Copy constructor
BP( const BP & x ) : DAIAlgFG(x), edges(x.edges), props(x.props), maxdiff(x.maxdiff) {};
- /// Clone *this
+ /// Clone *this (virtual copy constructor)
BP* clone() const { return new BP(*this); }
+ /// Create (virtual constructor)
+ virtual BP* create() const { return new BP; }
/// Construct from FactorGraph fg and PropertySet opts
BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), edges(), props(), maxdiff(0.0) {
setProperties( opts );
std::string identify() const;
void create();
void init();
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &ns );
double run();
void findMaxResidual( size_t &i, size_t &_I );
std::vector<Factor> beliefs() const;
Real logZ() const;
- void init( const VarSet &ns );
void restoreFactors( const VarSet &ns ) { FactorGraph::restoreFactors(ns); init(ns); }
/// Set Props according to the PropertySet opts, where the values can be stored as std::strings or as the type of the corresponding Props member
/// Clone (virtual copy constructor)
virtual InfAlg* clone() const = 0;
+ /// Create (virtual constructor)
+ virtual InfAlg* create() const = 0;
+
/// Virtual desctructor
// (this is needed because this class contains virtual functions)
virtual ~InfAlg() {}
/// Clear messages and beliefs
virtual void init() = 0;
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &ns ) = 0;
+
/// The actual approximate inference algorithm
virtual double run() = 0;
virtual void restoreFactors( const VarSet &ns ) = 0;
/// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
- virtual void clamp( const Var & n, size_t i ) = 0;
+ virtual void clamp( const Var & n, size_t i, bool backup = false ) = 0;
/// Set all factors interacting with var(i) to 1
- virtual void makeCavity( size_t i ) = 0;
+ virtual void makeCavity( size_t i, bool backup = false ) = 0;
/// Get reference to underlying FactorGraph
virtual FactorGraph &fg() = 0;
/// Copy constructor
DAIAlg( const DAIAlg & x ) : InfAlg(x), T(x) {}
+ /// Assignment operator
+ DAIAlg & operator=( const DAIAlg &x ) {
+ if( this != &x ) {
+ InfAlg::operator=(x);
+ T::operator=(x);
+ }
+ return *this;
+ }
+
/// Save factor I (using T::backupFactor)
void backupFactor( size_t I ) { T::backupFactor( I ); }
/// Save Factors involving ns (using T::backupFactors)
void restoreFactors( const VarSet &ns ) { T::restoreFactors( ns ); }
/// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
- void clamp( const Var & n, size_t i ) { T::clamp( n, i ); }
+ void clamp( const Var & n, size_t i, bool backup = false ) { T::clamp( n, i, backup ); }
/// Set all factors interacting with var(i) to 1 (using T::makeCavity)
- void makeCavity( size_t i ) { T::makeCavity( i ); }
+ void makeCavity( size_t i, bool backup = false ) { T::makeCavity( i, backup ); }
/// Get reference to underlying FactorGraph
FactorGraph &fg() { return (FactorGraph &)(*this); }
return *this;
}
-/* /// Create (virtual constructor)
+ /// Create (virtual constructor)
virtual ExactInf* create() const {
return new ExactInf();
}
-*/
+
/// Return maximum difference between single node
/// beliefs for two consecutive iterations
virtual double maxDiff() const {
virtual void init();
/// Clear messages and beliefs corresponding to the nodes in ns
- virtual void init( const VarSet &/*ns*/ ) {}
+ virtual void init( const VarSet &/*ns*/ ) {
+ DAI_THROW(NOT_IMPLEMENTED);
+ }
/// The actual approximate inference algorithm
virtual double run();
public:
BipartiteGraph G;
std::vector<Var> vars;
- std::vector<Factor> factors;
typedef BipartiteGraph::Neighbor Neighbor;
typedef BipartiteGraph::Neighbors Neighbors;
typedef BipartiteGraph::Edge Edge;
private:
+ std::vector<Factor> _factors;
std::map<size_t,Factor> _backup;
public:
/// Default constructor
- FactorGraph() : G(), vars(), factors(), _backup() {}
+ FactorGraph() : G(), vars(), _factors(), _backup() {}
/// Copy constructor
- FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), factors(x.factors), _backup(x._backup) {}
+ FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), _factors(x._factors), _backup(x._backup) {}
/// Construct FactorGraph from vector of Factors
FactorGraph(const std::vector<Factor> &P);
// Construct a FactorGraph from given factor and variable iterators
if( this != &x ) {
G = x.G;
vars = x.vars;
- factors = x.factors;
- _backup = x._backup;
+ _factors = x._factors;
+ _backup = x._backup;
}
return *this;
}
Var & var(size_t i) { return vars[i]; }
/// Get const reference to i'th variable
const Var & var(size_t i) const { return vars[i]; }
- Factor & factor(size_t I) { return factors[I]; }
/// Get const reference to I'th factor
- const Factor & factor(size_t I) const { return factors[I]; }
+ Factor & factor(size_t I) { return _factors[I]; }
+ /// Get const reference to I'th factor
+ const Factor & factor(size_t I) const { return _factors[I]; }
+ /// Get const reference to all factors
+ const std::vector<Factor> & factors() const { return _factors; }
/// Get number of variables
size_t nrVars() const { return vars.size(); }
/// Get number of factors
- size_t nrFactors() const { return factors.size(); }
+ size_t nrFactors() const { return _factors.size(); }
size_t nrEdges() const { return G.nrEdges(); }
/// Provides read access to neighbors of variable
/// 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() == factors[I].vars() );
+ assert( newFactor.vars() == factor(I).vars() );
if( backup )
backupFactor( I );
- factors[I] = newFactor;
+ _factors[I] = newFactor;
}
/// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
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() {
// add factors
size_t nrEdges = 0;
- factors.reserve( nr_fact_hint );
+ _factors.reserve( nr_fact_hint );
for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
- factors.push_back( *p2 );
+ _factors.push_back( *p2 );
nrEdges += p2->vars().size();
}
/// Clone function
HAK* clone() const { return new HAK(*this); }
+ /// Create (virtual constructor)
+ virtual HAK* create() const { return new HAK(); }
+
/// Construct from RegionGraph
HAK(const RegionGraph & rg, const PropertySet &opts);
double doDoubleLoop();
double run();
void init();
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &ns );
std::string identify() const;
Factor belief( const Var &n ) const;
Factor belief( const VarSet &ns ) const;
std::vector<Factor> beliefs() const;
Real logZ () const;
- void init( const VarSet &ns );
void restoreFactors( const VarSet &ns ) { RegionGraph::restoreFactors( ns ); init( ns ); }
void setProperties( const PropertySet &opts );
PropertySet getProperties() const;
JTree() : DAIAlgRG(), _RTree(), _Qa(), _Qb(), _mes(), _logZ(), props() {}
JTree( const JTree& x ) : DAIAlgRG(x), _RTree(x._RTree), _Qa(x._Qa), _Qb(x._Qb), _mes(x._mes), _logZ(x._logZ), props(x.props) {}
JTree* clone() const { return new JTree(*this); }
+ /// Create (virtual constructor)
+ virtual JTree* create() const { return new JTree(); }
JTree & operator=( const JTree& x ) {
if( this != &x ) {
DAIAlgRG::operator=(x);
static const char *Name;
std::string identify() const;
void init() {}
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &/*ns*/ ) {}
void runHUGIN();
void runShaferShenoy();
double run();
std::vector<Factor> beliefs() const;
Real logZ() const;
- void init( const VarSet &/*ns*/ ) {}
void restoreFactors( const VarSet &ns ) { RegionGraph::restoreFactors( ns ); init( ns ); }
size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
LC(const LC & x) : DAIAlgFG(x), _pancakes(x._pancakes), _cavitydists(x._cavitydists), _phis(x._phis), _beliefs(x._beliefs), props(x.props), maxdiff(x.maxdiff) {}
/// Clone function
LC* clone() const { return new LC(*this); }
+ /// Create (virtual constructor)
+ virtual LC* create() const { return new LC(); }
/// Construct LC object from a FactorGraph and parameters
LC( const FactorGraph & fg, const PropertySet &opts );
/// Assignment operator
long SetCavityDists( std::vector<Factor> &Q );
void init();
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &/*ns*/ ) {
+ DAI_THROW(NOT_IMPLEMENTED);
+ }
Factor NewPancake (size_t i, size_t _I, bool & hasNaNs);
double run();
// copy constructor
MF( const MF& x ) : DAIAlgFG(x), _beliefs(x._beliefs), props(x.props), maxdiff(x.maxdiff) {}
MF* clone() const { return new MF(*this); }
+ /// Create (virtual constructor)
+ virtual MF* create() const { return new MF(); }
// construct MF object from FactorGraph
MF( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), props(), maxdiff(0.0) {
setProperties( opts );
std::string identify() const;
void create();
void init();
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &ns );
double run();
Factor beliefV (size_t i) const;
Factor belief (const Var &n) const;
std::vector<Factor> beliefs() const;
Real logZ() const;
- void init( const VarSet &ns );
void restoreFactors( const VarSet &ns ) { FactorGraph::restoreFactors(ns); init(ns); }
void setProperties( const PropertySet &opts );
PropertySet getProperties() const;
double maxdiff;
public:
+ MR() {}
MR( const FactorGraph & fg, const PropertySet &opts );
void init(size_t Nin, double *_w, double *_th);
void makekindex();
return 0.0;
}
void init() {}
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &/*ns*/ ) {
+ DAI_THROW(NOT_IMPLEMENTED);
+ }
static const char *Name;
std::string identify() const;
double _tJ(size_t i, sub_nb A);
double sign(double a) { return (a >= 0) ? 1.0 : -1.0; }
MR* clone() const { return new MR(*this); }
+ /// Create (virtual constructor)
+ virtual MR* create() const { return new MR(); }
void setProperties( const PropertySet &opts );
PropertySet getProperties() const;
return *this;
}
+ /// Create (virtual default constructor)
+ virtual RegionGraph* create() const {
+ return new RegionGraph();
+ }
+
+ /// Clone (virtual copy constructor)
+ virtual RegionGraph* clone() const {
+ return new RegionGraph(*this);
+ }
+
+ /// 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 ) {
+ FactorGraph::setFactor( I, newFactor, backup );
+ RecomputeOR( I );
+ }
+
+ /// 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 ) {
+ FactorGraph::setFactors( facs, backup );
+ VarSet ns;
+ for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
+ ns |= fac->second.vars();
+ RecomputeORs( ns );
+ }
+
+
/// Provides read access to outer region
const FRegion & OR(size_t alpha) const { return ORs[alpha]; }
/// Provides access to outer region
/// Recompute all outer regions involving factor I
void RecomputeOR( size_t I );
- /// We have to overload FactorGraph::clamp because the corresponding outer regions have to be recomputed
- void clamp( const Var &n, size_t i ) { FactorGraph::clamp( n, i ); RecomputeORs( n ); }
-
- /// We have to overload FactorGraph::makeCavity because the corresponding outer regions have to be recomputed
- void makeCavity( size_t i ) { FactorGraph::makeCavity( i ); RecomputeORs( var(i) ); }
-
- /// We have to overload FactorGraph::restoreFactors because the corresponding outer regions have to be recomputed
- void restoreFactors( const VarSet &ns ) { FactorGraph::restoreFactors( ns ); RecomputeORs( ns ); }
-
- /// We have to overload FactorGraph::restoreFactor because the corresponding outer regions have to be recomputed
- void restoreFactor( size_t I ) { FactorGraph::restoreFactor( I ); RecomputeOR( I ); }
-
/// Send RegionGraph to output stream
friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
};
_Q[I].I() = &factor(I);
}
TreeEP* clone() const { return new TreeEP(*this); }
+ /// Create (virtual constructor)
+ virtual TreeEP* create() const { return new TreeEP(); }
TreeEP & operator=( const TreeEP& x ) {
if( this != &x ) {
JTree::operator=(x);
static const char *Name;
std::string identify() const;
void init();
+ /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual void init( const VarSet &/*ns*/ ) { init(); }
double run();
Real logZ() const;
bool offtree( size_t I ) const { return (fac2OR[I] == -1U); }
- void init( const VarSet &/*ns*/ ) { init(); }
void restoreFactors( const VarSet &ns ) { RegionGraph::restoreFactors( ns ); init( ns ); }
void setProperties( const PropertySet &opts );
using namespace std;
-/// Calculate the marginal of obj on ns by clamping
-/// all variables in ns and calculating logZ for each joined state
Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit ) {
Factor Pns (ns);
// run DAIAlg, calc logZ, store in Pns
if( reInit )
clamped->init();
+ else
+ clamped->init(ns);
clamped->run();
Real Z;
delete clamped;
- return( Pns.normalized(Prob::NORMPROB) );
+ return( Pns.normalized() );
}
for( size_t j = 0; j < N; j++ )
for( size_t k = 0; k < N; k++ )
if( j == k )
- pairbeliefs.push_back(Factor());
+ pairbeliefs.push_back( Factor() );
else
- pairbeliefs.push_back(Factor(vns[j] | vns[k]));
+ pairbeliefs.push_back( Factor( vns[j] | vns[k] ) );
InfAlg *clamped = obj.clone();
if( !reInit )
for( size_t j = 0; j < N; j++ ) {
// clamp Var j to its possible values
for( size_t j_val = 0; j_val < vns[j].states(); j_val++ ) {
- // save unclamped factors connected to ns
- clamped->backupFactors( ns );
-
- clamped->clamp( vns[j], j_val );
+ clamped->clamp( vns[j], j_val, true );
if( reInit )
clamped->init();
+ else
+ clamped->init(ns);
clamped->run();
//if( j == 0 )
for( size_t ij = 0; ij < pairbeliefs.size(); ij++ )
Pns *= pairbeliefs[ij];
- return( Pns.normalized(Prob::NORMPROB) );
+ return( Pns.normalized() );
}
clamped->clamp( *nk, k_val );
if( reInit )
clamped->init();
+ else
+ clamped->init(ns);
clamped->run();
double Z_xj = 1.0;
FactorGraph::FactorGraph( const std::vector<Factor> &P ) : G(), _backup() {
// add factors, obtain variables
set<Var> _vars;
- factors.reserve( P.size() );
+ _factors.reserve( P.size() );
size_t nrEdges = 0;
for( vector<Factor>::const_iterator p2 = P.begin(); p2 != P.end(); p2++ ) {
- factors.push_back( *p2 );
+ _factors.push_back( *p2 );
copy( p2->vars().begin(), p2->vars().end(), inserter( _vars, _vars.begin() ) );
nrEdges += p2->vars().size();
}
long verbose = 0;
try {
- vector<Factor> factors;
+ vector<Factor> facs;
size_t nr_Factors;
string line;
vardims[labels[mi]] = dims[mi];
I_vars |= Var(labels[mi], dims[mi]);
}
- factors.push_back( Factor( I_vars, 0.0 ) );
+ facs.push_back( Factor( I_vars, 0.0 ) );
// calculate permutation sigma (internally, members are sorted)
vector<size_t> sigma(nr_members,0);
// store value, but permute indices first according
// to internal representation
- factors.back()[permindex.convert_linear_index( li )] = val;
+ facs.back()[permindex.convert_linear_index( li )] = val;
}
}
if( verbose >= 3 )
- cout << "factors:" << factors << endl;
+ cout << "factors:" << facs << endl;
- fg = FactorGraph(factors);
+ fg = FactorGraph(facs);
} catch (char *e) {
cout << e << endl;
}
#include <algorithm>
#include <cmath>
+#include <boost/dynamic_bitset.hpp>
#include <dai/regiongraph.h>
#include <dai/factorgraph.h>
#include <dai/clustergraph.h>
for( alpha = 0; alpha < nrORs(); alpha++ )
if( OR(alpha).vars() >> factor(I).vars() ) {
fac2OR.push_back( alpha );
-// OR(alpha) *= factor(I);
break;
}
assert( alpha != nrORs() );
for( alpha = 0; alpha < nrORs(); alpha++ )
if( OR(alpha).vars() >> factor(I).vars() ) {
fac2OR.push_back( alpha );
-// OR(alpha) *= factor(I);
break;
}
assert( alpha != nrORs() );
set<VarSet> betas;
for( size_t alpha = 0; alpha < cg.clusters.size(); alpha++ )
for( size_t alpha2 = alpha; (++alpha2) != cg.clusters.size(); ) {
- VarSet intersect = cg.clusters[alpha] & cg.clusters[alpha2];
- if( intersect.size() > 0 )
- betas.insert( intersect );
+ VarSet intersection = cg.clusters[alpha] & cg.clusters[alpha2];
+ if( intersection.size() > 0 )
+ betas.insert( intersection );
}
// Create inner regions - subsequent passes
new_betas.clear();
for( set<VarSet>::const_iterator gamma = betas.begin(); gamma != betas.end(); gamma++ )
for( set<VarSet>::const_iterator gamma2 = gamma; (++gamma2) != betas.end(); ) {
- VarSet intersect = (*gamma) & (*gamma2);
- if( (intersect.size() > 0) && (betas.count(intersect) == 0) )
- new_betas.insert( intersect );
+ VarSet intersection = (*gamma) & (*gamma2);
+ if( (intersection.size() > 0) && (betas.count(intersection) == 0) )
+ new_betas.insert( intersection );
}
betas.insert(new_betas.begin(), new_betas.end());
} while( new_betas.size() );
// Calculates counting numbers of inner regions based upon counting numbers of outer regions
vector<vector<size_t> > ancestors(nrIRs());
- vector<bool> assigned(nrIRs(), false);
+ boost::dynamic_bitset<> assigned(nrIRs());
for( size_t beta = 0; beta < nrIRs(); beta++ ) {
IR(beta).c() = 0.0;
for( size_t beta2 = 0; beta2 < nrIRs(); beta2++ )
for( vector<size_t>::const_iterator beta2 = ancestors[beta].begin(); beta2 != ancestors[beta].end(); beta2++ )
c -= IR(*beta2).c();
IR(beta).c() = c;
- assigned[beta] = true;
+ assigned.set(beta, true);
new_counting = true;
}
}
ostream & operator << (ostream & os, const RegionGraph & rg) {
os << "Outer regions" << endl;
for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
- os << rg.OR(alpha).vars() << ": c = " << rg.OR(alpha).c() << endl;
+ os << alpha << ": " << rg.OR(alpha).vars() << ": c = " << rg.OR(alpha).c() << endl;
os << "Inner regions" << endl;
for( size_t beta = 0; beta < rg.nrIRs(); beta++ )
- os << (VarSet)rg.IR(beta) << ": c = " << rg.IR(beta).c() << endl;
+ os << beta << ": " << (VarSet)rg.IR(beta) << ": c = " << rg.IR(beta).c() << endl;
+
+ os << "Edges" << endl;
+ for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
+ foreach( const RegionGraph::Neighbor &beta, rg.nbOR(alpha) )
+ os << alpha << "->" << beta << endl;
return(os);
}
projects / libdai.git / commitdiff