Several small changes
authorJoris Mooij <jorism@osun.tuebingen.mpg.de>
Fri, 19 Sep 2008 12:24:19 +0000 (14:24 +0200)
committerJoris Mooij <jorism@osun.tuebingen.mpg.de>
Fri, 19 Sep 2008 12:24:19 +0000 (14:24 +0200)
- Added BipGraph::addEdge(...)
- Removed *::updatedFactor(...)
- Removed FactorGraph::_normtype and FactorGraph::NormType()

STATUS
include/dai/bipgraph.h
include/dai/daialg.h
include/dai/factorgraph.h
include/dai/regiongraph.h
src/bp.cpp
src/factorgraph.cpp
src/hak.cpp
src/lc.cpp
src/mf.cpp

diff --git a/STATUS b/STATUS
index 1f17959..d712b2c 100644 (file)
--- a/STATUS
+++ b/STATUS
@@ -16,8 +16,6 @@ A disadvantage of this approach may be worse cachability.
   to replace the linear searches that are performed every time for findVar()?
   No, a better idea is to avoid calls to findVar() as much as possible.
 - Can the FactorGraph constructors be optimized further?
-- Move FactorGraph::_normType somewhere else (maybe to InfAlg or DAIAlg<T>)
-- Remove updatedFactor
 
 TODO FOR RELEASE:
 - Test Visual C++ compatibility
index c9701ef..19eb434 100644 (file)
@@ -241,12 +241,35 @@ class BipartiteGraph {
             _nb2.push_back( nbs2new );
         }
 
-        /// Remove node of type 1 and all incident edges.
+        /// Remove node n1 of type 1 and all incident edges.
         void erase1( size_t n1 );
 
-        /// Remove node of type 2 and all incident edges.
+        /// Remove node n2 of type 2 and all incident edges.
         void erase2( size_t n2 );
 
+        /// Add edge between node n1 of type 1 and node n2 of type 2.
+        /** If check == true, only adds the edge if it does not exist already.
+         */
+        void addEdge( size_t n1, size_t n2, bool check = true ) {
+            assert( n1 < nr1() );
+            assert( n2 < nr2() );
+            bool exists = false;
+            if( check ) {
+                // Check whether the edge already exists
+                foreach( const Neighbor &nb2, nb1(n1) )
+                    if( nb2 == n2 ) {
+                        exists = true;
+                        break;
+                    }
+            }
+            if( !exists ) { // Add edge
+                Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
+                Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
+                _nb1[n1].push_back( nb_1 );
+                _nb2[n2].push_back( nb_2 );
+            }
+        }
+
         /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
         /** If include == true, include n1 itself, otherwise exclude n1.
          */
@@ -282,11 +305,11 @@ void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, Ed
     _nb2.resize( nr2 );
 
     for( EdgeInputIterator e = begin; e != end; e++ ) {
-        // Each edge yields a neighbor pair
-        Neighbor nb_1( _nb1[e->first].size(), e->second, _nb2[e->second].size() );
-        Neighbor nb_2( nb_1.dual, e->first, nb_1.iter );
-        _nb1[e->first].push_back( nb_1 );
-        _nb2[e->second].push_back( nb_2 );
+#ifdef DAI_DEBUG
+        addEdge( e->first, e->second, true );
+#else
+        addEdge( e->first, e->second, false );
+#endif
     }
 }
 
index 049d8a4..bfb2b84 100644 (file)
@@ -156,9 +156,6 @@ class InfAlg {
         /// Set all factors interacting with var(i) to 1
         virtual void makeCavity( size_t i ) = 0;
 
-        /// Factor I has been updated
-        virtual void updatedFactor( size_t I ) = 0;
-
         /// Get reference to underlying FactorGraph
         virtual FactorGraph &fg() = 0;
 
@@ -202,9 +199,6 @@ class DAIAlg : public InfAlg, public T {
         /// Set all factors interacting with var(i) to 1 (using T::makeCavity)
         void makeCavity( size_t i ) { T::makeCavity( i ); }
 
-        /// Factor I has been updated (using T::updatedFactor)
-        void updatedFactor( size_t I ) { T::updatedFactor(I); }
-
         /// Get reference to underlying FactorGraph
         FactorGraph &fg() { return (FactorGraph &)(*this); }
 
index a502ae8..567d9bb 100644 (file)
@@ -47,13 +47,12 @@ class FactorGraph {
 
     protected:
         std::map<size_t,Prob>  _undoProbs;
-        Prob::NormType         _normtype;
 
     public:
         /// Default constructor
-        FactorGraph() : G(), vars(), factors(), _undoProbs(), _normtype(Prob::NORMPROB) {};
+        FactorGraph() : G(), vars(), factors(), _undoProbs() {};
         /// Copy constructor
-        FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), factors(x.factors), _undoProbs(x._undoProbs), _normtype(x._normtype) {};
+        FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), factors(x.factors), _undoProbs(x._undoProbs) {};
         /// Construct FactorGraph from vector of Factors
         FactorGraph(const std::vector<Factor> &P);
         // Construct a FactorGraph from given factor and variable iterators
@@ -67,7 +66,6 @@ class FactorGraph {
                 vars       = x.vars;
                 factors    = x.factors;
                 _undoProbs = x._undoProbs;
-                _normtype  = x._normtype;
             }
             return *this;
         }
@@ -128,7 +126,6 @@ class FactorGraph {
         virtual void clamp( const Var & n, size_t i );
         
         bool hasNegatives() const;
-        Prob::NormType NormType() const { return _normtype; }
         
         std::vector<VarSet> Cliques() const;
 
@@ -137,8 +134,6 @@ class FactorGraph {
         virtual void undoProb( size_t I );
         void saveProb( size_t I );
 
-        virtual void updatedFactor( size_t /*I*/ ) {};
-
     private:
         /// Part of constructors (creates edges, neighbors and adjacency matrix)
         void createGraph( size_t nrEdges );
@@ -147,7 +142,7 @@ class FactorGraph {
 
 // 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 ) : G(), _undoProbs(), _normtype(Prob::NORMPROB) {
+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(), _undoProbs() {
     // add factors
     size_t nrEdges = 0;
     factors.reserve( nr_fact_hint );
index 09e17a5..16916c0 100644 (file)
@@ -189,9 +189,6 @@ class RegionGraph : public FactorGraph {
         /// We have to overload FactorGraph::undoProb because the corresponding outer regions have to be recomputed
         void undoProb( size_t I ) { FactorGraph::undoProb( I ); RecomputeOR( I ); }
 
-        /// If updateFactor is called, we know that factor I has been changed and we should recompute the outer regions involving I
-        void updatedFactor( size_t I ) { RecomputeOR( I ); }
-
         /// Send RegionGraph to output stream
         friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
 };
index 580a4c6..bb8a21f 100644 (file)
@@ -170,7 +170,7 @@ void BP::calcNewMessage( size_t i, size_t _I ) {
     const ind_t ind = index(i,_I);
     for( size_t r = 0; r < prod.size(); ++r )
         marg[ind[r]] += prod[r];
-    marg.normalize( _normtype );
+    marg.normalize( Prob::NORMPROB );
     
     // Store result
     if( logDomain )
index 9c0f0ae..4df27c8 100644 (file)
@@ -38,7 +38,7 @@ namespace dai {
 using namespace std;
 
 
-FactorGraph::FactorGraph( const std::vector<Factor> &P ) : G(), _undoProbs(), _normtype(Prob::NORMPROB) {
+FactorGraph::FactorGraph( const std::vector<Factor> &P ) : G(), _undoProbs() {
     // add factors, obtain variables
     set<Var> _vars;
     factors.reserve( P.size() );
index 5570dee..1e5f9ad 100644 (file)
@@ -227,7 +227,7 @@ double HAK::doGBP() {
                 Qb_new *= muab(alpha,_beta) ^ (1 / (nbIR(beta).size() + IR(beta).c()));
             }
 
-            Qb_new.normalize( _normtype );
+            Qb_new.normalize( Prob::NORMPROB );
             if( Qb_new.hasNaNs() ) {
                 cout << "HAK::doGBP:  Qb_new has NaNs!" << endl;
                 return 1.0;
@@ -244,7 +244,7 @@ double HAK::doGBP() {
                 foreach( const Neighbor &gamma, nbOR(alpha) )
                     Qa_new *= muba(alpha,gamma.iter);
                 Qa_new ^= (1.0 / OR(alpha).c());
-                Qa_new.normalize( _normtype );
+                Qa_new.normalize( Prob::NORMPROB );
                 if( Qa_new.hasNaNs() ) {
                     cout << "HAK::doGBP:  Qa_new has NaNs!" << endl;
                     return 1.0;
index f0eb649..a2c1797 100644 (file)
@@ -153,7 +153,7 @@ double LC::CalcCavityDist (size_t i, const std::string &name, const Properties &
         maxdiff = cav->MaxDiff();
         delete cav;
     }
-    Bi.normalize( _normtype );
+    Bi.normalize( Prob::NORMPROB );
     _cavitydists[i] = Bi;
 
     return maxdiff;
@@ -223,7 +223,7 @@ void LC::init() {
               _pancakes[i] *= _phis[i][I.iter];
         }
         
-        _pancakes[i].normalize( _normtype );
+        _pancakes[i].normalize( Prob::NORMPROB );
 
         CalcBelief(i);
     }
@@ -245,10 +245,10 @@ Factor LC::NewPancake (size_t i, size_t _I, bool & hasNaNs) {
     Factor A_Ii = (_pancakes[i] * factor(I).inverse() * _phis[i][_I].inverse()).part_sum( Ivars / var(i) );
     Factor quot = A_I.divided_by(A_Ii);
 
-    piet *= quot.divided_by( _phis[i][_I] ).normalized( _normtype );
-    _phis[i][_I] = quot.normalized( _normtype );
+    piet *= quot.divided_by( _phis[i][_I] ).normalized( Prob::NORMPROB );
+    _phis[i][_I] = quot.normalized( Prob::NORMPROB );
 
-    piet.normalize( _normtype );
+    piet.normalize( Prob::NORMPROB );
 
     if( piet.hasNaNs() ) {
         cout << "LC::NewPancake(" << i << ", " << _I << "):  has NaNs!" << endl;
index 921692b..da60b55 100644 (file)
@@ -107,7 +107,7 @@ double MF::run() {
             jan *= piet; 
         }
 
-        jan.normalize( _normtype );
+        jan.normalize( Prob::NORMPROB );
 
         if( jan.hasNaNs() ) {
             cout << "MF::run():  ERROR: jan has NaNs!" << endl;