+libDAI-0.2.2 (2008-??-??)
+-------------------------
+
+* Contributions by Christian, resulting in vast speed and memory improvements
+ for large factor graphs:
+ - Sparse implementation of nodes->edge conversion table _E12ind in bipgraph.h
+ - New FactorGraph constructor that constructs from given ranges of factors
+ and variables
+ - Optimization of FactorGraph constructors
+* FactorGraph constructors no longer check for short loops and for
+ negative entries. Also, the normtype is now Prob::NORMPROB by default.
+* Moved everything into namespace "dai"
+
+
libDAI-0.2.1 (2008-05-26)
-------------------------
#include "alldai.h"
+namespace dai {
+
+
InfAlg *newInfAlg( const string &name, const FactorGraph &fg, const Properties &opts ) {
if( name == BP::Name )
return new BP (fg, opts);
else
throw "Unknown inference algorithm";
}
+
+
+}
#include "mr.h"
+namespace dai {
+
+
/// newInfAlg constructs a new approximate inference algorithm named name for the
/// FactorGraph fg with optionts opts and returns a pointer to the new object.
/// The caller needs to delete it (maybe some sort of smart_ptr might be useful here).
/// AINames contains the names of all approximate inference algorithms
static const char* DAINames[] = {BP::Name, MF::Name, HAK::Name, LC::Name, TreeEP::Name, MR::Name, JTree::Name};
+}
+
#endif
#include <vector>
#include <algorithm>
+#include <boost/numeric/ublas/vector_sparse.hpp>
+
+
+namespace dai {
/// A BipartiteGraph represents a graph with two types of nodes
std::vector<_edge_t> _E12;
/// Conversion matrix that computes which index of _E12 corresponds to a vertex index pair (v1,v2)
- std::vector<std::vector<size_t> > _E12ind;
+ std::vector<boost::numeric::ublas::mapped_vector<size_t> > _E12ind;
/// Neighbour indices of vertices of first type
std::vector<_nb_t> _nb1;
_nb_t & nb2( size_t i2 ) { return _nb2[i2]; }
/// Converts the pair of indices (i1,i2) to the corresponding edge index
- size_t VV2E( const size_t i1, const size_t i2 ) const { return _E12ind[i1][i2]; }
+ size_t VV2E( const size_t i1, const size_t i2 ) const { return _E12ind[i1](i2); }
/// Regenerates internal structures (_E12ind, _nb1 and _nb2) based upon _V1, _V2 and _E12
}
// Calculate _E12ind
-
- // Allocate data structures
- _E12ind.clear();
- std::vector<size_t> col(_V2.size(),-1);
- _E12ind.assign(_V1.size(), col);
- // Assign elements
+ _E12ind = std::vector<boost::numeric::ublas::mapped_vector<size_t> >(_V1.size(), boost::numeric::ublas::mapped_vector<size_t>(_V2.size()) );
for( size_t k = 0; k < _E12.size(); k++ )
- _E12ind[_E12[k].first][_E12[k].second] = k;
+ _E12ind[_E12[k].first](_E12[k].second) = k;
+
}
};
+}
+
+
#endif
#include "properties.h"
+namespace dai {
+
+
using namespace std;
message(ni,*I).fill( 1.0 );
}
}
+
+
+}
#include "enum.h"
+namespace dai {
+
+
using namespace std;
typedef vector<size_t> _ind_t;
vector<_ind_t> _indices;
- vector<Prob> _messages, _newmessages;
+ vector<Prob> _messages, _newmessages;
public:
ENUM4(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
bool checkProperties();
};
+
+}
+
+
#endif
#include "clustergraph.h"
+namespace dai {
+
+
using namespace std;
return result;
}
+
+
+}
#include "varset.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#include "daialg.h"
+namespace dai {
+
+
/// 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 ) {
return result;
}
+
+
+}
#include "properties.h"
+namespace dai {
+
+
/// The InfAlg class is the common denominator of the various approximate inference algorithms.
/// A InfAlg object represents a discrete factorized probability distribution over multiple variables
/// together with an inference algorithm.
Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
+}
+
#endif
#include <vector>
+
+namespace dai {
+
+
using namespace std;
}
};
+
+}
+
+
#endif
#include <iostream>
+namespace dai {
+
+
// C++ enums are too limited for my purposes. This defines wrapper classes
// that provide much more functionality than a simple enum. The only
// disadvantage is that one wrapper class needs to be written for each
};
+}
+
+
#endif
-/* Copyright 2006-2008 Joris Mooij
- jorism@jorismooij.nl
+/* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
+ Radboud University Nijmegen, The Netherlands
- This file is part of AI.
+ This file is part of libDAI.
- AI is free software; you can redistribute it and/or modify
+ libDAI is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
- AI is distributed in the hope that it will be useful,
+ libDAI is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with AI; if not, write to the Free Software
+ along with libDAI; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#include "alldai.h"
+using namespace dai;
using namespace std;
#include "index.h"
+namespace dai {
+
+
template<typename T> class TFactor;
typedef TFactor<Real> Factor;
typedef TFactor<Complex> CFactor;
}
+}
+
+
#endif
#include <string>
#include <algorithm>
#include <functional>
+#include <tr1/unordered_map>
#include "factorgraph.h"
+namespace dai {
+
+
using namespace std;
-FactorGraph::FactorGraph( const vector<Factor> &P ) : BipartiteGraph<Var,Factor>(), _undoProbs(), _hasNegatives(false), _normtype(Prob::NORMPROB) {
- // add Factors
+FactorGraph::FactorGraph( const vector<Factor> &P ) : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {
+ // add factors, obtain variables
set<Var> _vars;
- for(vector<Factor>::const_iterator p2 = P.begin(); p2 != P.end(); p2++ ) {
- V2s().push_back(*p2);
- if( !_hasNegatives && p2->hasNegatives() )
- _hasNegatives = true;
- for( set<Var>::const_iterator i = p2->vars().begin(); i != p2->vars().end(); i++ )
- _vars.insert(*i);
+ V2s().reserve( P.size() );
+ size_t nrEdges = 0;
+ for( vector<Factor>::const_iterator p2 = P.begin(); p2 != P.end(); p2++ ) {
+ V2s().push_back( *p2 );
+ copy( p2->vars().begin(), p2->vars().end(), inserter( _vars, _vars.begin() ) );
+ nrEdges += p2->vars().size();
}
- // if negative factors are present, use LINF norm
- if( _hasNegatives )
- _normtype = Prob::NORMLINF;
-
// add _vars
- for(VarSet::const_iterator p1 = _vars.begin(); p1 != _vars.end(); p1++ )
- vars().push_back(*p1);
+ V1s().reserve( _vars.size() );
+ for( set<Var>::const_iterator p1 = _vars.begin(); p1 != _vars.end(); p1++ )
+ V1s().push_back( *p1 );
+
+ // create graph structure
+ createGraph( nrEdges );
+}
+
+/// Part of constructors (creates edges, neighbours and adjacency matrix)
+void FactorGraph::createGraph( size_t nrEdges ) {
+ // create a mapping for indices
+ std::tr1::unordered_map<size_t, size_t> hashmap;
+
+ for( size_t i = 0; i < vars().size(); i++ )
+ hashmap[vars()[i].label()] = i;
+
// create edges
- for(size_t i2 = 0; i2 < nrFactors(); i2++ ) {
- VarSet ns = factor(i2).vars();
- for(VarSet::const_iterator q = ns.begin(); q != ns.end(); q++ ) {
- for(size_t i1=0; i1 < nrVars(); i1++ ) {
- if (var(i1) == *q) {
- edges().push_back(_edge_t(i1,i2));
- break;
- }
- }
- }
+ edges().reserve( nrEdges );
+ for( size_t i2 = 0; i2 < nrFactors(); i2++ ) {
+ const VarSet& ns = factor(i2).vars();
+ for( VarSet::const_iterator q = ns.begin(); q != ns.end(); q++ )
+ edges().push_back(_edge_t(hashmap[q->label()], i2));
}
// calc neighbours and adjacency matrix
Regenerate();
-
- // Check for short loops
- if( hasShortLoops(P) )
- cerr << "FactorGraph::FactorGraph(): WARNING: short loops are present" << endl;
}
/*FactorGraph& FactorGraph::addFactor( const Factor &I ) {
// add Factor
_V2.push_back( I );
- if( !_hasNegatives && I.hasNegatives() )
- _hasNegatives = true;
-
- // if negative factors are present, use LINF norm
- if( _hasNegatives )
- _normtype = Prob::NORMLINF;
// add new vars in Factor
for( VarSet::const_iterator i = I.vars().begin(); i != I.vars().end(); i++ ) {
}
+bool FactorGraph::hasNegatives() const {
+ bool result = false;
+ for( size_t I = 0; I < nrFactors() && !result; I++ )
+ if( factor(I).hasNegatives() )
+ result = true;
+ return result;
+}
+
+
/*FactorGraph & FactorGraph::DeleteFactor(size_t I) {
// Go through all edges
for( vector<_edge_t>::iterator edge = _E12.begin(); edge != _E12.end(); edge++ )
return remaining.empty();
}
}
+
+
+}
#include "bipgraph.h"
#include "factor.h"
+#include <tr1/unordered_map>
+
+
+namespace dai {
+
using namespace std;
+bool hasShortLoops(const vector<Factor> &P);
+void RemoveShortLoops(vector<Factor> &P);
+
class FactorGraph : public BipartiteGraph<Var,Factor> {
protected:
map<size_t,Prob> _undoProbs;
- bool _hasNegatives;
Prob::NormType _normtype;
public:
/// Default constructor
- FactorGraph() : BipartiteGraph<Var,Factor>(), _undoProbs(), _hasNegatives(false), _normtype(Prob::NORMPROB) {};
+ FactorGraph() : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {};
/// Copy constructor
- FactorGraph(const FactorGraph & x) : BipartiteGraph<Var,Factor>(x), _undoProbs(), _hasNegatives(x._hasNegatives), _normtype(x._normtype) {};
+ FactorGraph(const FactorGraph & x) : BipartiteGraph<Var,Factor>(x), _undoProbs(), _normtype(x._normtype) {};
/// Construct FactorGraph from vector of Factors
FactorGraph(const vector<Factor> &P);
+ // Construct a FactorGraph from given factor and variable iterators
+ template<typename FactorInputIterator, typename VarInputIterator>
+ 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 );
+
/// Assignment operator
FactorGraph & operator=(const FactorGraph & x) {
if(this!=&x) {
BipartiteGraph<Var,Factor>::operator=(x);
_undoProbs = x._undoProbs;
- _hasNegatives = x._hasNegatives;
_normtype = x._normtype;
}
return *this;
virtual void clamp( const Var & n, size_t i );
- bool hasNegatives() const { return _hasNegatives; }
+ bool hasNegatives() const;
Prob::NormType NormType() const { return _normtype; }
vector<VarSet> Cliques() const;
bool isConnected() const;
virtual void updatedFactor( size_t I ) {};
+
+ private:
+ /// Part of constructors (creates edges, neighbours and adjacency matrix)
+ void createGraph( size_t nrEdges );
};
-bool hasShortLoops(const vector<Factor> &P);
-void RemoveShortLoops(vector<Factor> &P);
+// 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)
+template<typename FactorInputIterator, typename VarInputIterator>
+FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint, size_t nr_var_hint ) : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {
+ // add factors
+ size_t nrEdges = 0;
+ V2s().reserve( nr_fact_hint );
+ for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
+ V2s().push_back( *p2 );
+ nrEdges += p2->vars().size();
+ }
+
+ // add variables
+ V1s().reserve( nr_var_hint );
+ for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
+ V1s().push_back( *p1 );
+
+ // create graph structure
+ createGraph( nrEdges );
+}
+
+
+}
#endif
#include "diffs.h"
+namespace dai {
+
+
const char *HAK::Name = "HAK";
}
return sum;
}
+
+
+}
#include "enum.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#ifndef __INDEX_H__
#define __INDEX_H__
+
#include <vector>
#include "varset.h"
+
+namespace dai {
+
+
/* Example:
*
* Index i ({s_j_1,s_j_2,...,s_j_m}, {s_1,...,s_N}); // j_k in {1,...,N}
* }
*/
+
class Index
{
private:
};
};
+
class multind {
private:
std::vector<size_t> _dims; // dimensions
}
std::vector<size_t> vi(size_t li) const { // linear index to vector index
std::vector<size_t> v(_dims.size(),0);
- assert(li >= 0 && li < _pdims.back());
+ assert(li < _pdims.back());
for( long j = v.size()-1; j >= 0; j-- ) {
size_t q = li / _pdims[j];
v[j] = q;
// FIXME add an iterator, which increases a vector index just using addition
};
+
+}
+
+
#endif
#include "jtree.h"
+namespace dai {
+
+
using namespace std;
}
}
}
+
+
+}
#include "enum.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#include "x2x.h"
+namespace dai {
+
+
using namespace std;
// Set interactions of order > 2 to zero
size_t N = delta(var(i)).size();
- double *p = &(*Bi.p().p().begin());
+ Real *p = &(*Bi.p().p().begin());
x2x::p2logp (N, p);
x2x::logp2w (N, p);
x2x::fill (N, p, 2, 0.0);
// Set cumulants of order > 2 to zero
size_t N = delta(var(i)).size();
- double *p = &(*Bi.p().p().begin());
+ Real *p = &(*Bi.p().p().begin());
x2x::p2m (N, p);
x2x::m2c (N, p, N);
x2x::fill (N, p, 2, 0.0);
return diffs.max();
}
+
+
+}
#include "factorgraph.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#include "util.h"
+namespace dai {
+
+
using namespace std;
_beliefs[i].fill( 1.0 );
}
}
+
+
+}
#include "daialg.h"
#include "factorgraph.h"
+
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#include "diffs.h"
+namespace dai {
+
+
using namespace std;
if( supported ) {
size_t i = findVar( n );
- double x[2];
+ Real x[2];
x[0] = 0.5 - Mag[i] / 2.0;
x[1] = 0.5 + Mag[i] / 2.0;
delete th;
delete w;
}
+
+
+}
#include "enum.h"
+namespace dai {
+
+
using namespace std;
size_t operator[](size_t i) {
size_t bit;
for(bit = 0; bit < bits; bit++ )
- if( s & (1U << bit) )
+ if( s & (1U << bit) ) {
if( i == 0 )
break;
else
i--;
+ }
#ifdef DEBUG
assert( bit < bits );
#endif
};
+}
+
+
#endif
#include "util.h"
+namespace dai {
+
+
typedef double Real;
typedef std::complex<double> Complex;
};
+}
+
+
#endif
#include "alldai.h"
+namespace dai {
+
+
/// Sends a single Property object to an output stream
std::ostream& operator<< (std::ostream & os, const Property & p) {
os << p.first << "=";
return is;
}
+
+
+}
#include <typeinfo>
+namespace dai {
+
+
typedef std::string PropertyKey;
typedef boost::any PropertyValue;
typedef std::pair<PropertyKey, PropertyValue> Property;
};
+}
+
+
#endif
#include "clustergraph.h"
+namespace dai {
+
+
RegionGraph::RegionGraph(const FactorGraph & fg, const vector<Region> & ors, const vector<Region> & irs, const vector<R_edge_t> & edges) : FactorGraph(fg), BipRegGraph(), _fac2OR() {
// Copy outer regions (giving them counting number 1.0)
ORs().reserve( ors.size() );
return(os);
}
+
+
+}
#include "weightedgraph.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
using namespace std;
+using namespace dai;
namespace po = boost::program_options;
#include "diffs.h"
+namespace dai {
+
+
using namespace std;
return sum;
}
+
+
+}
#include "enum.h"
+namespace dai {
+
+
using namespace std;
};
+}
+
+
#endif
#include <boost/random/variate_generator.hpp>
+namespace dai {
+
+
clock_t toc() {
tms tbuf;
times(&tbuf);
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand _rnd_gen_type;
-_rnd_gen_type _rnd_gen(42u);
+_rnd_gen_type _rnd_gen(42);
// Define a uniform random number distribution which produces "double"
// values between 0 and 1 (0 inclusive, 1 exclusive).
boost::variate_generator<_rnd_gen_type&, boost::normal_distribution<> > _normal_rnd(_rnd_gen, _normal_dist);
-void rnd_seed( size_t seed ) {
+void rnd_seed( int seed ) {
_rnd_gen.seed(seed);
}
double rnd_stdnormal() {
return _normal_rnd();
}
+
+
+}
#include <cstdio>
+namespace dai {
+
+
clock_t toc();
-void rnd_seed( size_t seed );
+void rnd_seed( int seed );
double rnd_uniform();
double rnd_stdnormal();
+}
+
+
#endif
using namespace std;
+using namespace dai;
namespace po = boost::program_options;
#include "../factorgraph.h"
#include <iostream>
-#include <stdlib.h>
+#include <cstdlib>
+#include <string>
+using namespace dai;
using namespace std;
cerr << "Error reading file " << infile << endl;
return 2;
} else {
- if( strcmp( argv[2], "-" ) )
+ if( string( argv[2] ) == "-" )
fg.WriteToDotFile( argv[2] );
else {
cout << "graph G {" << endl;
#include "../factorgraph.h"
#include <iostream>
-#include <stdlib.h>
+#include <cstdlib>
+using namespace dai;
using namespace std;
#include "factorgraph.h"
#include <iostream>
-#include <stdlib.h>
+#include <cstdlib>
+using namespace dai;
using namespace std;
#include <iostream>
+namespace dai {
+
+
/// Represents a discrete variable
class Var {
private:
};
+}
+
+
#endif
#include "var.h"
+namespace dai {
+
+
/// VarSet represents a set of variables and is a descendant of set<Var>.
/// In addition, it provides an easy interface for set-theoretic operations
/// by operator overloading.
}
+}
+
+
#endif
#include "util.h"
+namespace dai {
+
+
std::ostream & operator << (std::ostream & os, const DEdgeVec & rt) {
os << "[";
for( size_t n = 0; n < rt.size(); n++ )
return G;
}
+
+
+}
#include <set>
+namespace dai {
+
+
using namespace std;
UEdgeVec RandomDRegularGraph( size_t N, size_t d );
+}
+
+
#endif
*/
-#include <math.h>
-#include <string.h>
+#include <cmath>
+#include <cstring>
+
namespace x2x {
*/
-#include <math.h>
-#include <string.h>
+#include <cmath>
+#include <cstring>
namespace x2x {
projects / libdai.git / commitdiff