Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro.
[libdai.git] / src / factorgraph.cpp
index fcbf626..4df27c8 100644 (file)
@@ -27,8 +27,9 @@
 #include <string>
 #include <algorithm>
 #include <functional>
-#include <tr1/unordered_map>
 #include <dai/factorgraph.h>
+#include <dai/util.h>
+#include <dai/exceptions.h>
 
 
 namespace dai {
@@ -37,21 +38,21 @@ namespace dai {
 using namespace std;
 
 
-FactorGraph::FactorGraph( const vector<Factor> &P ) : BipartiteGraph<Var,Factor>(), _undoProbs(), _normtype(Prob::NORMPROB) {
+FactorGraph::FactorGraph( const std::vector<Factor> &P ) : G(), _undoProbs() {
     // add factors, obtain variables
     set<Var> _vars;
-    V2s().reserve( P.size() );
+    factors.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();
+        factors.push_back( *p2 );
+        copy( p2->vars().begin(), p2->vars().end(), inserter( _vars, _vars.begin() ) );
+        nrEdges += p2->vars().size();
     }
 
     // add _vars
-    V1s().reserve( _vars.size() );
+    vars.reserve( _vars.size() );
     for( set<Var>::const_iterator p1 = _vars.begin(); p1 != _vars.end(); p1++ )
-        V1s().push_back( *p1 );
+        vars.push_back( *p1 );
     
     // create graph structure
     createGraph( nrEdges );
@@ -61,41 +62,25 @@ FactorGraph::FactorGraph( const vector<Factor> &P ) : BipartiteGraph<Var,Factor>
 /// 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;
+    hash_map<size_t, size_t> hashmap;
     
-    for( size_t i = 0; i < vars().size(); i++ )        
-       hashmap[vars()[i].label()] = i;
+    for( size_t i = 0; i < vars.size(); i++ )
+        hashmap[var(i).label()] = i;
     
-    // create edges
-    edges().reserve( nrEdges );
+    // create edge list
+    vector<Edge> edges;
+    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));               
+            edges.push_back( Edge(hashmap[q->label()], i2) );
     }
 
-    // calc neighbours and adjacency matrix
-    Regenerate();
+    // create bipartite graph
+    G.create( nrVars(), nrFactors(), edges.begin(), edges.end() );
 }
 
 
-/*FactorGraph& FactorGraph::addFactor( const Factor &I ) {
-    // add Factor
-    _V2.push_back( I );
-
-    // add new vars in Factor
-    for( VarSet::const_iterator i = I.vars().begin(); i != I.vars().end(); i++ ) {
-        size_t i_ind = find(vars().begin(), vars().end(), *i) - vars().begin();
-        if( i_ind == vars().size() )
-            _V1.push_back( *i );
-        _E12.push_back( _edge_t( i_ind, nrFactors() - 1 ) );
-    }
-
-    Regenerate();
-    return(*this);
-}*/
-
-
 ostream& operator << (ostream& os, const FactorGraph& fg) {
     os << fg.nrFactors() << endl;
 
@@ -109,11 +94,11 @@ ostream& operator << (ostream& os, const FactorGraph& fg) {
             os << i->states() << " ";
         os << endl;
         size_t nr_nonzeros = 0;
-        for( size_t k = 0; k < fg.factor(I).stateSpace(); k++ )
+        for( size_t k = 0; k < fg.factor(I).states(); k++ )
             if( fg.factor(I)[k] != 0.0 )
                 nr_nonzeros++;
         os << nr_nonzeros << endl;
-        for( size_t k = 0; k < fg.factor(I).stateSpace(); k++ )
+        for( size_t k = 0; k < fg.factor(I).states(); k++ )
             if( fg.factor(I)[k] != 0.0 ) {
                 char buf[20];
                 sprintf(buf,"%18.14g", fg.factor(I)[k]);
@@ -137,13 +122,13 @@ istream& operator >> (istream& is, FactorGraph& fg) {
             getline(is,line);
         is >> nr_f;
         if( is.fail() )
-            throw "ReadFromFile: unable to read number of Factors";
+            DAI_THROW(INVALID_FACTORGRAPH_FILE);
         if( verbose >= 2 )
             cout << "Reading " << nr_f << " factors..." << endl;
 
         getline (is,line);
         if( is.fail() )
-            throw "ReadFromFile: empty line expected";
+            DAI_THROW(INVALID_FACTORGRAPH_FILE);
 
         for( size_t I = 0; I < nr_f; I++ ) {
             if( verbose >= 3 )
@@ -186,11 +171,11 @@ istream& operator >> (istream& is, FactorGraph& fg) {
             // add the Factor
             VarSet I_vars;
             for( size_t mi = 0; mi < nr_members; mi++ )
-                I_vars.insert( Var(labels[mi], dims[mi]) );
+                I_vars |= Var(labels[mi], dims[mi]);
             factors.push_back(Factor(I_vars,0.0));
             
             // calculate permutation sigma (internally, members are sorted)
-            vector<long> sigma(nr_members,0);
+            vector<size_t> sigma(nr_members,0);
             VarSet::iterator j = I_vars.begin();
             for( size_t mi = 0; mi < nr_members; mi++,j++ ) {
                 long search_for = j->label();
@@ -204,22 +189,7 @@ istream& operator >> (istream& is, FactorGraph& fg) {
             }
 
             // calculate multindices
-            vector<size_t> sdims(nr_members,0);
-            for( size_t k = 0; k < nr_members; k++ ) {
-                sdims[k] = dims[sigma[k]];
-            }
-            multind mi(dims);
-            multind smi(sdims);
-            if( verbose >= 3 ) {
-                cout << "  mi.max(): " << mi.max() << endl;
-                cout << "       ";
-                for( size_t k=0; k < nr_members; k++ ) 
-                    cout << labels[k] << " ";
-                cout << "   ";
-                for( size_t k=0; k < nr_members; k++ ) 
-                    cout << labels[sigma[k]] << " ";
-                cout << endl;
-            }
+            Permute permindex( dims, sigma );
             
             // read values
             size_t nr_nonzeros;
@@ -238,19 +208,9 @@ istream& operator >> (istream& is, FactorGraph& fg) {
                     getline(is,line);
                 is >> val;
 
-                vector<size_t> vi = mi.vi(li);
-                vector<size_t> svi(vi.size(),0);
-                for( size_t k = 0; k < vi.size(); k++ )
-                    svi[k] = vi[sigma[k]];
-                size_t sli = smi.li(svi);
-                if( verbose >= 3 ) {
-                    cout << "    " << li << ": ";
-                    copy( vi.begin(), vi.end(), ostream_iterator<size_t>(cout," "));
-                    cout << "-> ";
-                    copy( svi.begin(), svi.end(), ostream_iterator<size_t>(cout," "));
-                    cout << ": " << sli << endl;
-                }
-                factors.back()[sli] = val;
+                // store value, but permute indices first according
+                // to internal representation
+                factors.back()[permindex.convert_linear_index( li  )] = val;
             }
         }
 
@@ -268,37 +228,27 @@ istream& operator >> (istream& is, FactorGraph& fg) {
 }
 
 
-VarSet FactorGraph::delta(const Var & n) const {
+VarSet FactorGraph::delta( unsigned i ) const {
     // calculate Markov Blanket
-    size_t i = findVar( n );
-
     VarSet del;
-    for( _nb_cit I = nb1(i).begin(); I != nb1(i).end(); ++I )
-        for( _nb_cit j = nb2(*I).begin(); j != nb2(*I).end(); ++j )
-            if( *j != i )
-                del |= var(*j);
+    foreach( const Neighbor &I, nbV(i) ) // for all neighboring factors I of i
+        foreach( const Neighbor &j, nbF(I) ) // for all neighboring variables j of I
+            if( j != i )
+                del |= var(j);
 
     return del;
 }
 
 
-VarSet FactorGraph::Delta(const Var & n) const {
-    return( delta(n) | n );
+VarSet FactorGraph::Delta( unsigned i ) const {
+    return( delta(i) | var(i) );
 }
 
 
-void FactorGraph::makeFactorCavity(size_t I) {
-    // fill Factor I with ones
-    factor(I).fill(1.0);
-}
-
-
-void FactorGraph::makeCavity(const Var & n) {
-    // fills all Factors that include Var n with ones
-    size_t i = findVar( n );
-
-    for( _nb_cit I = nb1(i).begin(); I != nb1(i).end(); ++I )
-        factor(*I).fill(1.0);
+void FactorGraph::makeCavity( unsigned i ) {
+    // fills all Factors that include var(i) with ones
+    foreach( const Neighbor &I, nbV(i) ) // for all neighboring factors I of i
+        factor(I).fill( 1.0 );
 }
 
 
@@ -306,62 +256,11 @@ bool FactorGraph::hasNegatives() const {
     bool result = false;
     for( size_t I = 0; I < nrFactors() && !result; I++ )
         if( factor(I).hasNegatives() )
-           result = true;
+            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++ )
-        if( edge->second >= I ) {
-            if( edge->second == I )
-                edge->second = -1UL;
-            else 
-                (edge->second)--;
-        }
-    // Remove all edges containing I
-    for( vector<_edge_t>::iterator edge = _E12.begin(); edge != _E12.end(); edge++ )
-        if( edge->second == -1UL )
-            edge = _E12.erase( edge );
-//  vector<_edge_t>::iterator new_end = _E12.remove_if( _E12.begin(), _E12.end(), compose1( bind2nd(equal_to<size_t>(), -1), select2nd<_edge_t>() ) );
-//  _E12.erase( new_end, _E12.end() );
-
-    // Erase the factor
-    _V2.erase( _V2.begin() + I );
-    
-    Regenerate();
-
-    return *this;
-}
-
-
-FactorGraph & FactorGraph::DeleteVar(size_t i) {
-    // Go through all edges
-    for( vector<_edge_t>::iterator edge = _E12.begin(); edge != _E12.end(); edge++ )
-        if( edge->first >= i ) {
-            if( edge->first == i )
-                edge->first = -1UL;
-            else 
-                (edge->first)--;
-        }
-    // Remove all edges containing i
-    for( vector<_edge_t>::iterator edge = _E12.begin(); edge != _E12.end(); edge++ )
-        if( edge->first == -1UL )
-            edge = _E12.erase( edge );
-                
-//  vector<_edge_t>::iterator new_end = _E12.remove_if( _E12.begin(), _E12.end(), compose1( bind2nd(equal_to<size_t>(), -1), select1st<_edge_t>() ) );
-//  _E12.erase( new_end, _E12.end() );
-
-    // Erase the variable
-    _V1.erase( _V1.begin() + i );
-    
-    Regenerate();
-
-    return *this;
-}*/
-
-
 long FactorGraph::ReadFromFile(const char *filename) {
     ifstream infile;
     infile.open (filename);
@@ -408,8 +307,9 @@ long FactorGraph::WriteToDotFile(const char *filename) const {
             outfile << "node[shape=box,style=filled,color=lightgrey,width=0.3,height=0.3,fixedsize=true];" << endl;
             for( size_t I = 0; I < nrFactors(); I++ )
                 outfile << "\tp" << I << ";" << endl;
-            for( size_t iI = 0; iI < nr_edges(); iI++ )
-                outfile << "\tx" << var(edge(iI).first).label() << " -- p" << edge(iI).second << ";" << endl;
+            for( size_t i = 0; i < nrVars(); i++ )
+                foreach( const Neighbor &I, nbV(i) )  // for all neighboring factors I of i
+                    outfile << "\tx" << var(i).label() << " -- p" << I << ";" << endl;
             outfile << "}" << endl;
         } catch (char *e) {
             cout << e << endl;
@@ -467,22 +367,6 @@ void RemoveShortLoops(vector<Factor> &P) {
 }
 
 
-Factor FactorGraph::ExactMarginal(const VarSet & x) const {
-    Factor P;
-    for( size_t I = 0; I < nrFactors(); I++ )
-        P *= factor(I);
-    return P.marginal(x);
-}
-
-
-Real FactorGraph::ExactlogZ() const {
-    Factor P;
-    for( size_t I = 0; I < nrFactors(); I++ )
-        P *= factor(I);
-    return std::log(P.totalSum());
-}
-
-
 vector<VarSet> FactorGraph::Cliques() const {
     vector<VarSet> result;
     
@@ -503,52 +387,14 @@ vector<VarSet> FactorGraph::Cliques() const {
 void FactorGraph::clamp( const Var & n, size_t i ) {
     assert( i <= n.states() );
 
-/*  if( do_surgery ) {
-        size_t ni = find( vars().begin(), vars().end(), n) - vars().begin();
-
-        if( ni != nrVars() ) {
-            for( _nb_cit I = nb1(ni).begin(); I != nb1(ni).end(); I++ ) {
-                if( factor(*I).size() == 1 )
-                    // Remove this single-variable factor
-    //              I = (_V2.erase(I))--;
-                    _E12.erase( _E12.begin() + VV2E(ni, *I) );
-                else {
-                    // Replace it by the slice
-                    Index ind_I_min_n( factor(*I), factor(*I) / n );
-                    Index ind_n( factor(*I), n );
-                    Factor slice_I( factor(*I) / n );
-                    for( size_t ind_I = 0; ind_I < factor(*I).stateSpace(); ++ind_I, ++ind_I_min_n, ++ind_n )
-                        if( ind_n == i )
-                            slice_I[ind_I_min_n] = factor(*I)[ind_I];
-                    factor(*I) = slice_I;
-
-                    // Remove the edge between n and I
-                    _E12.erase( _E12.begin() + VV2E(ni, *I) );
-                }
-            }
-
-            Regenerate();
-            
-            // remove all unconnected factors
-            for( size_t I = 0; I < nrFactors(); I++ )
-                if( nb2(I).size() == 0 )
-                    DeleteFactor(I--);
-
-            DeleteVar( ni );
-
-            // FIXME
-        }
-    } */
-
-    // The cheap solution (at least in terms of coding time) is to multiply every factor
-    // that contains the variable with a delta function
+    // Multiply each factor that contains the variable with a delta function
 
     Factor delta_n_i(n,0.0);
     delta_n_i[i] = 1.0;
 
     // For all factors that contain n
     for( size_t I = 0; I < nrFactors(); I++ ) 
-        if( factor(I).vars() && n )
+        if( factor(I).vars().contains( n ) )
             // Multiply it with a delta function
             factor(I) *= delta_n_i;
 
@@ -577,14 +423,14 @@ void FactorGraph::saveProbs( const VarSet &ns ) {
     if( !_undoProbs.empty() )
         cout << "FactorGraph::saveProbs:  WARNING: _undoProbs not empy!" << endl;
     for( size_t I = 0; I < nrFactors(); I++ )
-        if( factor(I).vars() && ns )
+        if( factor(I).vars().intersects( ns ) )
             _undoProbs[I] = factor(I).p();
 }
 
 
 void FactorGraph::undoProbs( const VarSet &ns ) {
     for( map<size_t,Prob>::iterator uI = _undoProbs.begin(); uI != _undoProbs.end(); ) {
-        if( factor((*uI).first).vars() && ns ) {
+        if( factor((*uI).first).vars().intersects( ns ) ) {
 //          cout << "undoing " << factor((*uI).first).vars() << endl;
 //          cout << "from " << factor((*uI).first).p() << " to " << (*uI).second << endl;
             factor((*uI).first).p() = (*uI).second;
@@ -595,36 +441,4 @@ void FactorGraph::undoProbs( const VarSet &ns ) {
 }
 
 
-bool FactorGraph::isConnected() const {
-    if( nrVars() == 0 )
-        return false;
-    else {
-        Var n = var( 0 );
-
-        VarSet component = n;
-
-        VarSet remaining;
-        for( size_t i = 1; i < nrVars(); i++ )
-            remaining |= var(i);
-
-        bool found_new_vars = true;
-        while( found_new_vars ) {
-            VarSet new_vars;
-            for( VarSet::const_iterator m = remaining.begin(); m != remaining.end(); m++ )
-                if( delta(*m) && component )
-                    new_vars |= *m;
-
-            if( new_vars.empty() )
-                found_new_vars = false;
-            else 
-                found_new_vars = true;
-
-            component |= new_vars;
-            remaining /= new_vars;
-        };
-        return remaining.empty();
-    }
-}
-
-
 } // end of namespace dai