Implemented various heuristics for choosing a variable elimination sequence in JTree
[libdai.git] / include / dai / clustergraph.h
index 8c3730f..8be220b 100644 (file)
 namespace dai {
 
 
-    class ClusterGraph;
-
-    /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinFill" criterion.
-    /** The cost is measured as "number of added edges in the adjacency graph",
-     *  where the adjacency graph has the variables as its nodes and connects
-     *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
-     */
-    size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i );
-
-    /// Returns the best variable from \a remainingVars to eliminate in the cluster graph \a cl according to the "MinFill" criterion.
-    /** This function invokes eliminationCost_MinFill() for each variable in \a remainingVars, and returns
-     *  the variable which has lowest cost according to eliminationCost_MinFill().
-     *  \note This function can be passed to ClusterGraph::VarElim().
-     */
-    size_t eliminationChoice_MinFill( const ClusterGraph &cl, const std::set<size_t> &remainingVars );
-
-
     /// A ClusterGraph is a hypergraph with variables as nodes, and "clusters" (sets of variables) as hyperedges.
     /** It is implemented as a bipartite graph with variable (Var) nodes and cluster (VarSet) nodes.
      */
@@ -184,40 +167,13 @@ namespace dai {
 
         /// \name Variable elimination
         //@{
-            /// Calculates cost of eliminating the \a i 'th variable.
-            /** The cost is measured as "number of added edges in the adjacency graph",
-             *  where the adjacency graph has the variables as its nodes and connects
-             *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
-             *  \deprecated Please use dai::eliminationCost_MinFill() instead.
-             */
-            size_t eliminationCost( size_t i ) const {
-                return eliminationCost_MinFill( *this, i );
-            }
-
-            /// Performs Variable Elimination, only keeping track of the interactions that are created along the way.
-            /** \param ElimSeq The sequence in which to eliminate the variables
-             *  \return A set of elimination "cliques"
-             *  \deprecated Not used; if necessary, dai::ClusterGraph::VarElim( EliminationChoice & ) can be used instead.
-             */
-            ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
-
-            /// Performs Variable Elimination using the "MinFill" heuristic
-            /** The "MinFill" heuristic greedily minimizes the cost of eliminating a variable,
-             *  measured with eliminationCost().
-             *  \return A set of elimination "cliques"
-             *  \deprecated Please use dai::ClusterGraph::VarElim( eliminationChoice_MinFill ) instead.
-             */
-            ClusterGraph VarElim_MinFill() const {
-                return VarElim( eliminationChoice_MinFill );
-            }
-
             /// Performs Variable Elimination, only keeping track of the interactions that are created along the way.
             /** \tparam EliminationChoice should support "size_t operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars )"
-             *  \param f function object which returns the next variable index to eliminate; for example, eliminationChoice_MinFill()
-             *  \return A set of elimination "cliques"
+             *  \param f function object which returns the next variable index to eliminate; for example, a dai::greedyVariableElimination object.
+             *  \return A set of elimination "cliques".
              */
             template<class EliminationChoice>
-            ClusterGraph VarElim( EliminationChoice &f ) const {
+            ClusterGraph VarElim( EliminationChoice f ) const {
                 // Make a copy
                 ClusterGraph cl(*this);
                 cl.eraseNonMaximal();
@@ -232,6 +188,7 @@ namespace dai {
                 // Do variable elimination
                 while( !varindices.empty() ) {
                     size_t i = f( cl, varindices );
+                    DAI_ASSERT( i < vars.size() );
                     result.insert( cl.Delta( i ) );
                     cl.insert( cl.delta( i ) );
                     cl.eraseSubsuming( i );
@@ -241,10 +198,112 @@ namespace dai {
 
                 return result;
             }
+
+            /// Calculates cost of eliminating the \a i 'th variable.
+            /** The cost is measured as "number of added edges in the adjacency graph",
+             *  where the adjacency graph has the variables as its nodes and connects
+             *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
+             *  \deprecated Please use dai::eliminationCost_MinFill() instead.
+             */
+            size_t eliminationCost( size_t i ) const;
+
+            /// Performs Variable Elimination, only keeping track of the interactions that are created along the way.
+            /** \param ElimSeq The sequence in which to eliminate the variables
+             *  \return A set of elimination "cliques"
+             *  \deprecated Please use dai::ClusterGraph::VarElim( sequentialVariableElimination( ElimSeq ) ) instead.
+             */
+            ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
+
+            /// Performs Variable Elimination using the "MinFill" heuristic
+            /** The "MinFill" heuristic greedily minimizes the cost of eliminating a variable,
+             *  measured with eliminationCost().
+             *  \return A set of elimination "cliques".
+             *  \deprecated Please use dai::ClusterGraph::VarElim( greedyVariableElimination( eliminationCost_MinFill ) ) instead.
+             */
+            ClusterGraph VarElim_MinFill() const;
         //@}
     };
 
 
+    /// Helper object for dai::ClusterGraph::VarElim()
+    /** Chooses the next variable to eliminate by picking them sequentially from a given vector of variables.
+     */
+    class sequentialVariableElimination {
+        private:
+            /// The variable elimination sequence
+            std::vector<Var> seq;
+            /// Counter
+            size_t i;
+
+        public:
+            /// Construct from vector of variables
+            sequentialVariableElimination( const std::vector<Var> s ) : seq(s), i(0) {}
+
+            /// Returns next variable in sequence
+           size_t operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ );
+    };
+
+
+    /// Helper object for dai::ClusterGraph::VarElim()
+    /** Chooses the next variable to eliminate greedily by taking the one that minimizes
+     *  a given heuristic cost function.
+     */
+    class greedyVariableElimination {
+        public:
+            /// Type of cost functions to be used for greedy variable elimination
+            typedef size_t (*eliminationCostFunction)(const ClusterGraph &, size_t);
+
+        private:
+            /// Pointer to the cost function used
+            eliminationCostFunction heuristic;
+
+        public:
+            /// Construct from cost function
+            /** \note Examples of cost functions are eliminationCost_MinFill() and eliminationCost_WeightedMinFill().
+             */
+            greedyVariableElimination( eliminationCostFunction h ) : heuristic(h) {}
+
+            /// Returns the best variable from \a remainingVars to eliminate in the cluster graph \a cl by greedily minimizing the cost function.
+            /** This function calculates the cost for eliminating each variable in \a remaingVars and returns the variable which has lowest cost.
+             */
+            size_t operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars );
+    };
+
+
+    /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinNeighbors" criterion.
+    /** The cost is measured as "number of neigboring nodes in the current adjacency graph",
+     *  where the adjacency graph has the variables as its nodes and connects
+     *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
+     */
+    size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i );
+
+
+    /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinWeight" criterion.
+    /** The cost is measured as "product of weights of neighboring nodes in the current adjacency graph",
+     *  where the adjacency graph has the variables as its nodes and connects
+     *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
+     *  The weight of a node is the number of states of the corresponding variable.
+     */
+    size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i );
+
+
+    /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinFill" criterion.
+    /** The cost is measured as "number of added edges in the adjacency graph",
+     *  where the adjacency graph has the variables as its nodes and connects
+     *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
+     */
+    size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i );
+
+
+    /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "WeightedMinFill" criterion.
+    /** The cost is measured as "total weight of added edges in the adjacency graph",
+     *  where the adjacency graph has the variables as its nodes and connects
+     *  nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
+     *  The weight of an edge is the product of the number of states of the variables corresponding with its nodes.
+     */
+    size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i );
+
+
 } // end of namespace dai