New git HEAD version
[libdai.git] / src / clustergraph.cpp
index 80e107e..f899c4d 100644 (file)
@@ -1,22 +1,9 @@
-/*  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 libDAI.
-
-    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.
-
-    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 libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
+/*  This file is part of libDAI - http://www.libdai.org/
+ *
+ *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
+ */
 
 
 #include <set>
@@ -32,90 +19,120 @@ namespace dai {
 using namespace std;
 
 
-ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
-    const long verbose = 0;
+ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : _G(), _vars(), _clusters() {
+    // construct vars, clusters and edge list
+    vector<Edge> edges;
+    bforeach( const VarSet &cl, cls ) {
+        if( find( clusters().begin(), clusters().end(), cl ) == clusters().end() ) {
+            // add cluster
+            size_t n2 = nrClusters();
+            _clusters.push_back( cl );
+            for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
+                size_t n1 = find( vars().begin(), vars().end(), *n ) - vars().begin();
+                if( n1 == nrVars() )
+                    // add variable
+                    _vars.push_back( *n );
+                edges.push_back( Edge( n1, n2 ) );
+            }
+        } // disregard duplicate clusters
+    }
+
+    // Create bipartite graph
+    _G.construct( nrVars(), nrClusters(), edges.begin(), edges.end() );
+}
+
 
-    // Make a copy
-    ClusterGraph _Cl(*this);
+ClusterGraph::ClusterGraph( const FactorGraph& fg, bool onlyMaximal ) : _G( fg.nrVars(), 0 ), _vars(), _clusters() {
+    // copy variables
+    _vars.reserve( fg.nrVars() );
+    for( size_t i = 0; i < fg.nrVars(); i++ )
+        _vars.push_back( fg.var(i) );
 
-    ClusterGraph result;
-    _Cl.eraseNonMaximal();
-    
-    // Do variable elimination
-    for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
-        assert( _Cl.vars() && *n );
-
-        if( verbose >= 1 )
-            cout << "Cost of eliminating " << *n << ": " << _Cl.eliminationCost( *n ) << " new edges" << endl;
-        
-        result.insert( _Cl.Delta(*n) );
-
-        if( verbose >= 1 )
-            cout << "_Cl = " << _Cl << endl;
-
-        if( verbose >= 1 )
-            cout << "After inserting " << _Cl.delta(*n) << ", _Cl = ";
-        _Cl.insert( _Cl.delta(*n) );
-        if( verbose >= 1 )
-            cout << _Cl << endl;
-
-        if( verbose >= 1 )
-            cout << "After erasing clusters that contain " << *n <<  ", _Cl = ";
-        _Cl.eraseSubsuming( *n );
-        if( verbose >= 1 )
-            cout << _Cl << endl;
-
-        if( verbose >= 1 )
-            cout << "After erasing nonmaximal clusters, _Cl = ";
-        _Cl.eraseNonMaximal();
-        if( verbose >= 1 )
-            cout << _Cl << endl;
+    if( onlyMaximal ) {
+        for( size_t I = 0; I < fg.nrFactors(); I++ )
+            if( fg.isMaximal( I ) ) {
+                _clusters.push_back( fg.factor(I).vars() );
+                size_t clind = _G.addNode2();
+                bforeach( const Neighbor &i, fg.nbF(I) )
+                    _G.addEdge( i, clind, true );
+            }
+    } else {
+        // copy clusters
+        _clusters.reserve( fg.nrFactors() );
+        for( size_t I = 0; I < fg.nrFactors(); I++ )
+            _clusters.push_back( fg.factor(I).vars() );
+        // copy bipartite graph
+        _G = fg.bipGraph();
     }
+}
+
+
+size_t sequentialVariableElimination::operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ ) {
+    return cl.findVar( seq.at(i++) );
+}
+
 
-    return result;
+size_t greedyVariableElimination::operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars ) {
+    set<size_t>::const_iterator lowest = remainingVars.end();
+    size_t lowest_cost = -1UL;
+    for( set<size_t>::const_iterator i = remainingVars.begin(); i != remainingVars.end(); i++ ) {
+        size_t cost = heuristic( cl, *i );
+        if( lowest == remainingVars.end() || lowest_cost > cost ) {
+            lowest = i;
+            lowest_cost = cost;
+        }
+    }
+    return *lowest;
 }
 
 
-ClusterGraph ClusterGraph::VarElim_MinFill() const {
-    const long verbose = 0;
+size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i ) {
+    return cl.bipGraph().delta1( i ).size();
+}
 
-    // Make a copy
-    ClusterGraph _Cl(*this);
-    VarSet _vars( vars() );
 
-    ClusterGraph result;
-    _Cl.eraseNonMaximal();
+size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i ) {
+    SmallSet<size_t> id_n = cl.bipGraph().delta1( i );
     
-    // Do variable elimination
-    while( !_vars.empty() ) {
-        if( verbose >= 1 )
-            cout << "Var  Eliminiation cost" << endl;
-        VarSet::const_iterator lowest = _vars.end();
-        size_t lowest_cost = -1UL;
-        for( VarSet::const_iterator n = _vars.begin(); n != _vars.end(); n++ ) {
-            size_t cost = _Cl.eliminationCost( *n );
-            if( verbose >= 1 )
-                cout << *n << "  " << cost << endl;
-            if( lowest == _vars.end() || lowest_cost > cost ) {
-                lowest = n;
-                lowest_cost = cost;
+    size_t cost = 1;
+    for( SmallSet<size_t>::const_iterator it = id_n.begin(); it != id_n.end(); it++ )
+        cost *= cl.vars()[*it].states();
+
+    return cost;
+}
+
+
+size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i ) {
+    SmallSet<size_t> id_n = cl.bipGraph().delta1( i );
+
+    size_t cost = 0;
+    // for each unordered pair {i1,i2} adjacent to n
+    for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+        for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+            if( it1 != it2 ) {
+                // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+                if( !cl.adj(*it1, *it2) )
+                    cost++;
             }
-        }
-        Var n = *lowest;
 
-        if( verbose >= 1 )
-            cout << "Lowest: " << n << " (" << lowest_cost << ")" << endl;
+    return cost;
+}
 
-        result.insert( _Cl.Delta(n) );
 
-        _Cl.insert( _Cl.delta(n) );
-        _Cl.eraseSubsuming( n );
-        _Cl.eraseNonMaximal();
-        _vars /= n;
+size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i ) {
+    SmallSet<size_t> id_n = cl.bipGraph().delta1( i );
 
-    }
+    size_t cost = 0;
+    // for each unordered pair {i1,i2} adjacent to n
+    for( SmallSet<size_t>::const_iterator it1 = id_n.begin(); it1 != id_n.end(); it1++ )
+        for( SmallSet<size_t>::const_iterator it2 = it1; it2 != id_n.end(); it2++ )
+            if( it1 != it2 ) {
+                // if i1 and i2 are not adjacent, eliminating n would make them adjacent
+                if( !cl.adj(*it1, *it2) )
+                    cost += cl.vars()[*it1].states() * cl.vars()[*it2].states();
+            }
 
-    return result;
+    return cost;
 }