Fixed long-standing bug in TreeEP (now, within-loop propagation optimization works)

diff --git a/include/dai/treeep.h b/include/dai/treeep.h
index 585613e..14e69f3 100644 (file)
--- a/include/dai/treeep.h
+++ b/include/dai/treeep.h
@@ -66,9 +66,6 @@ class TreeEP : public JTree {
 
             /// How to choose the tree
             TypeType type;
-
-            /// Optimize within-loop propagation? (currently buggy, so disabled by default)
-            bool optimize;
         } props;
 
         /// Name of this inference method

diff --git a/src/jtree.cpp b/src/jtree.cpp
index 037e868..c0e65c0 100644 (file)
--- a/src/jtree.cpp
+++ b/src/jtree.cpp
@@ -361,26 +361,21 @@ size_t JTree::findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t Prev
     RootedTree newTree( Graph( RTree.begin(), RTree.end() ), maxalpha );
 
     // identify subtree that contains all variables of vs which are not in the new root
-    VarSet vsrem = vs / OR(maxalpha).vars();
     set<DEdge> subTree;
-    // for each variable in vs that is not in the root clique
-    for( VarSet::const_iterator n = vsrem.begin(); n != vsrem.end(); n++ ) {
-        // find first occurence of *n in the tree, which is closest to the root
-        size_t e = 0;
-        for( ; e != newTree.size(); e++ ) {
-            if( OR(newTree[e].n2).vars().contains( *n ) )
-                break;
-        }
-        DAI_ASSERT( e != newTree.size() );
-
-        // track-back path to root and add edges to subTree
-        subTree.insert( newTree[e] );
-        size_t pos = newTree[e].n1;
-        for( ; e > 0; e-- )
-            if( newTree[e-1].n2 == pos ) {
-                subTree.insert( newTree[e-1] );
-                pos = newTree[e-1].n1;
+    // for each variable in vs
+    for( VarSet::const_iterator n = vs.begin(); n != vs.end(); n++ ) {
+        for( size_t e = 0; e < newTree.size(); e++ ) {
+            if( OR(newTree[e].n2).vars().contains( *n ) ) {
+                size_t f = e;
+                subTree.insert( newTree[f] );
+                size_t pos = newTree[f].n1;
+                for( ; f > 0; f-- )
+                    if( newTree[f-1].n2 == pos ) {
+                        subTree.insert( newTree[f-1] );
+                        pos = newTree[f-1].n1;
+                    }
             }
+        }
     }
     if( PreviousRoot != (size_t)-1 && PreviousRoot != maxalpha) {
         // find first occurence of PreviousRoot in the tree, which is closest to the new root

diff --git a/src/treeep.cpp b/src/treeep.cpp
index 5e3e8db..2aa3106 100644 (file)
--- a/src/treeep.cpp
+++ b/src/treeep.cpp
@@ -36,11 +36,6 @@ void TreeEP::setProperties( const PropertySet &opts ) {
     props.maxiter = opts.getStringAs<size_t>("maxiter");
     props.verbose = opts.getStringAs<size_t>("verbose");
     props.type = opts.getStringAs<Properties::TypeType>("type");
-
-    if( opts.hasKey("optimize") )
-        props.optimize = opts.getStringAs<bool>("optimize");
-    else
-        props.optimize = false;
 }
 
 
@@ -50,7 +45,6 @@ PropertySet TreeEP::getProperties() const {
     opts.Set( "maxiter", props.maxiter );
     opts.Set( "verbose", props.verbose );
     opts.Set( "type", props.type );
-    opts.Set( "optimize", props.optimize );
     return opts;
 }
 
@@ -61,8 +55,7 @@ string TreeEP::printProperties() const {
     s << "tol=" << props.tol << ",";
     s << "maxiter=" << props.maxiter << ",";
     s << "verbose=" << props.verbose << ",";
-    s << "type=" << props.type << ",";
-    s << "optimize=" << props.optimize << "]";
+    s << "type=" << props.type << "]";
     return s.str();
 }
 
@@ -132,6 +125,11 @@ void TreeEP::construct( const RootedTree &tree ) {
     // factor as off-tree.
     JTree::construct( cl, false );
 
+    if( props.verbose >= 1 )
+        cerr << "TreeEP::construct: The tree has size " << JTree::RTree.size() << endl;
+    if( props.verbose >= 3 )
+        cerr << "  it is " << JTree::RTree << " with cliques " << cl << endl;
+
     // Create factor approximations
     _Q.clear();
     size_t PreviousRoot = (size_t)-1;
@@ -143,10 +141,11 @@ void TreeEP::construct( const RootedTree &tree ) {
                 RootedTree subTree;
                 size_t subTreeSize = findEfficientTree( factor(I).vars(), subTree, PreviousRoot );
                 PreviousRoot = subTree[0].n1;
-                if( props.optimize ) {
-                    subTree.resize( subTreeSize );  // FIXME
-                    cerr << "subtree " << I << " has size " << subTreeSize << endl;
-                }
+                subTree.resize( subTreeSize );
+                if( props.verbose >= 1 )
+                    cerr << "Subtree " << I << " has size " << subTreeSize << endl;
+                if( props.verbose >= 3 )
+                    cerr << "  it is " << subTree << endl;
                 _Q[I] = TreeEPSubTree( subTree, RTree, Qa, Qb, &factor(I) );
                 if( repeats == 1 )
                     break;