Merge branch 'unstable' of github.com:lteacy/maxsum-cpp

Luke Teacy · Luke Teacy · commit feff767d1dac · 2013-04-03T16:25:54.000+01:00
diff --git a/include/DiscreteFunction.h b/include/DiscreteFunction.h
@@ -209,9 +209,29 @@ namespace maxsum
       /**
        * Sets this function to a constant scalar value.
        * @param[in] val the value to assign to this function.
+       * @post this function will no longer depend on any variables.
        */
       DiscreteFunction& operator=(ValType val);
 
+      /**
+       * Sets this function to a constant scalar value, but preserves
+       * domain.
+       * @param[in] val the value to assign to this function.
+       * @post the domain of this function will be unchanged, but all values
+       * will be set to the specified constant value.
+       */
+      DiscreteFunction& assignKeepDomain(ValType val)
+      {
+         for(std::vector<ValType>::iterator it=values_i.begin();
+               it!=values_i.end(); ++it)
+         {
+            (*it) = val;
+         }
+         
+         return *this;
+
+      } // assignKeepDomain
+
       /**
        * Sets this function to be equal to another.
        * @param[in] val the value to assign to this function.
@@ -241,7 +261,7 @@ namespace maxsum
       /**
        * Multiply function by -1
        */
-      DiscreteFunction operator-()
+      DiscreteFunction operator-() const
       {
          return DiscreteFunction(*this) *= -1;
       }
@@ -250,7 +270,16 @@ namespace maxsum
        * Identity function.
        * @returns a reference to this function.
        */
-      DiscreteFunction& operator+()
+      const DiscreteFunction& operator+() const
+      {
+         return *this;
+      }
+
+      /**
+       * Identity function.
+       * @returns a reference to this function.
+       */
+      DiscreteFunction& operator+() 
       {
          return *this;
       }
@@ -800,10 +829,25 @@ namespace maxsum
       ValType max() const; 
 
       /**
-       * Returns the linear index of the maximum value accross entire domain.
+       * Returns the linear index of the maximum value across entire domain.
        */
       ValIndex argmax() const;
 
+      /**
+       * Returns the linear index of the 2nd largest value.
+       * Example usage:
+       * <p>
+       * <code>
+       * ValIndex mx1 = fun.argmax();
+       * ValIndex mx2 = fun.argmax2(mx1);
+       * </code>
+       * </p>
+       * @param mxInd the value returned by DiscreteFunction::argmax()
+       * This is the maximum of the set of values, excluding the largest one,
+       * returned by DiscreteFunction::argmax
+       */
+      ValIndex argmax2(ValIndex mxInd) const;
+
       /**
        * Returns the maxnorm for this function.
        * The maxnorm is defined as the maximum absolute value of the function:
@@ -906,6 +950,106 @@ namespace maxsum
    {
       return !equalWithinTolerance(f1,f2,0.0);
    }
+   
+   /**
+    * Returns true iff function is less than specified value
+    * across its entire domain.
+    */
+   inline bool operator<(const DiscreteFunction& f, const ValType v)
+   {
+      for(int k=0; k<f.domainSize(); ++k)
+      {
+         if(f(k)>=v)
+         {
+            return false;
+         }
+      }
+      return true;
+   }
+   
+   /**
+    * Returns true iff function is less than specified value
+    * across its entire domain.
+    */
+   inline bool operator>=(const ValType v, const DiscreteFunction& f)
+   {
+      return f < v;
+   }
+   
+   /**
+    * Returns true iff function is less than or equal to specified value
+    * across its entire domain.
+    */
+   inline bool operator<=(const DiscreteFunction& f, const ValType v)
+   {
+      for(int k=0; k<f.domainSize(); ++k)
+      {
+         if(f(k)>v)
+         {
+            return false;
+         }
+      }
+      return true;
+   }
+   
+   /**
+    * Returns true iff function is less than or equal to specified value
+    * across its entire domain.
+    */
+   inline bool operator>(const ValType v, const DiscreteFunction& f)
+   {
+      return f <= v;
+   }
+   
+   /**
+    * Returns true iff function is greater than specified value
+    * across its entire domain.
+    */
+   inline bool operator>(const DiscreteFunction& f, const ValType v)
+   {
+      for(int k=0; k<f.domainSize(); ++k)
+      {
+         if(f(k)<=v)
+         {
+            return false;
+         }
+      }
+      return true;
+   }
+   
+   /**
+    * Returns true iff function is greater than specified value
+    * across its entire domain.
+    */
+   inline bool operator<=(const ValType v, const DiscreteFunction& f)
+   {
+      return f > v;
+   }
+   
+   /**
+    * Returns true iff function is greater than or equal to specified value
+    * across its entire domain.
+    */
+   inline bool operator>=(const DiscreteFunction& f, const ValType v)
+   {
+      for(int k=0; k<f.domainSize(); ++k)
+      {
+         if(f(k)<v)
+         {
+            return false;
+         }
+      }
+      return true;
+   }
+   
+   /**
+    * Returns true iff function is greater than or equal to specified value
+    * across its entire domain.
+    */
+   inline bool operator<(const ValType v, const DiscreteFunction& f)
+   {
+      return f >= v;
+   }
 
    /**
     * Peforms element-wise division of a scalar by a function.
diff --git a/include/MaxSumController.h b/include/MaxSumController.h
@@ -48,6 +48,14 @@ namespace maxsum
        */
       FactorMap factors_i;
 
+      /**
+       * Map storing the total value for each factor (the factor + the sum of
+       * all its input messages. This is used if we need to calculate
+       * additional things, such as the second best joint action for each
+       * factor (for VPI).
+       */
+      FactorMap factorTotalValue_i;
+
       /**
        * Type of container used to map (action) variables to their currently
        * assigned values.
@@ -145,6 +153,24 @@ namespace maxsum
       : maxIterations_i(maxIterations),
         maxNormThreshold_i(maxnorm) {}
 
+      /**
+       * Returns the total value for a specified factor.
+       * The total value is the factor plus the sum of all its received messages.
+       * @pre the optimise method must be called first to properly initialise
+       * this value.
+       * @returns the total value for this factor.
+       */
+      const DiscreteFunction& getTotalValue(FactorID fac) const
+      {
+         FactorMap::const_iterator pos = factorTotalValue_i.find(fac);
+         if(factors_i.end()==pos)
+         {
+            throw new NoSuchElementException("MaxSumController::getFactor()",
+                  "No such factor in factor graph.");
+         }
+         return pos->second;
+      }
+
       /**
        * Accessor method for factor function.
        * @param[in] id the unique identifier of the desired factor.
@@ -284,6 +310,58 @@ namespace maxsum
          return pos->second;
       }
 
+      /**
+       * Accessor method for (writable) reference to factor function.
+       * This version returns a writable reference to a function to allow
+       * efficient updates to the function values. Note this is an UNSAFE
+       * procedure, because the MaxSumController will not be notified if
+       * any change is made to function's domain through this handle, which
+       * in turn will change the factor graph. 
+       * 
+       * In future, we may modify this function to unsure that no unexpected
+       * domain changes are made, but for now, this allows us to bypass all
+       * the redundant copying and checking that is done by
+       * MaxSumController::setFactor. If you need a safe procedure use that
+       * function instead.
+       *
+       * Also, if the factor is modified in anyway through the returned
+       * reference, the MaxSumController must be notified by calling
+       * MaxSumController::notifyFactorChange.
+       *
+       * @param[in] id the unique identifier of the desired factor.
+       * @returns a reference to the function associated with the factor with
+       * unique identifier <code>id</code>.
+       * @throws maxsum::NoSuchElementException if the specified factor is not
+       * known to this maxsum::MaxSumController.
+       * @pre a factor with this id must already be in the factor graph.
+       * @post the caller must ensure that the domain of the returned function
+       * is not changed, and so promise only to modify its values. Any change
+       * in value must be flagged to the MaxSumController by calling 
+       * MaxSumController::notifyFactorChange.
+       */
+      DiscreteFunction& getUnSafeWritableFactorHandle(FactorID id) 
+      {
+         FactorMap::iterator pos = factors_i.find(id);
+         if(factors_i.end()==pos)
+         {
+            throw new NoSuchElementException("MaxSumController::getFactor()",
+                  "No such factor in factor graph.");
+         }
+         return pos->second;
+      }
+
+      /**
+       * Function used to notify this MaxSumController of any changes made
+       * to a factor without its knowledge.
+       * This function should be called after any change to a factor
+       * made using MaxSumController::getUnSafeWritableFactorHandle
+       * @param id the id of the changed factor
+       */
+      void notifyFactor(FactorID id)
+      {
+         var2facMsgs_i.notify(id);
+      }
+
       /**
        * Returns true if and only if the specified variable is in the domain
        * of at least one of the factors managed by this maxsum::MaxSumController.
diff --git a/src/DiscreteFunction.cpp b/src/DiscreteFunction.cpp
@@ -462,8 +462,8 @@ ValType DiscreteFunction::min() const
 }
 
 /**
-* Returns the linear index of the maximum value accross entire domain.
-*/
+ * Returns the linear index of the maximum value accross entire domain.
+ */
 ValIndex DiscreteFunction::argmax() const
 {
    std::vector<ValType>::const_iterator pos =
@@ -472,6 +472,44 @@ ValIndex DiscreteFunction::argmax() const
    return result;
 }
 
+/**
+ * Returns the linear index of the 2nd largest value.
+ * Example usage:
+ * <p>
+ * <code>
+ * ValIndex mx1 = fun.argmax();
+ * ValIndex mx2 = fun.argmax2(mx1);
+ * </code>
+ * </p>
+ * @param mxInd the value returned by DiscreteFunction::argmax()
+ * This is the maximum of the set of values, excluding the largest one,
+ * returned by DiscreteFunction::argmax
+ */
+ValIndex DiscreteFunction::argmax2(const ValIndex mxInd) const
+{
+   ValType mx2Val = -std::numeric_limits<ValType>::max();
+   ValIndex mx2Ind = 0;
+
+   for(ValIndex it=0; it<domainSize(); ++it)
+   {
+      if(mxInd==it) // skip max to find largest of rest.
+      {
+         continue;
+      }
+
+      ValType curVal = at(it);
+      if(curVal>mx2Val)
+      {
+         mx2Val = curVal;
+         mx2Ind = it;
+      }
+      
+   } // for loop
+
+   return mx2Ind;
+
+} // argmax2
+
 /**
 * Returns the maxnorm for this function.
 * The maxnorm is defined as the maximum absolute value of the function:
diff --git a/src/MaxSumController.cpp b/src/MaxSumController.cpp
@@ -223,10 +223,8 @@ void MaxSumController::setFactor(FactorID id, const DiscreteFunction& factor)
    factors_i[id] = factor;
 
    //***************************************************************************
-   // Tell all factors and variables to recheck their mail.
-   // Only need to do this for factors, because once the factor 2 variable
-   // messages have been updated, the variables will in turn be notified of
-   // any change.
+   // Tell everyone to recheck their mail. Telling everyone to recheck is the
+   // safest option, because the factor graph may have changed.
    //***************************************************************************
    var2facMsgs_i.notifyAll();
 
@@ -390,7 +388,8 @@ int MaxSumController::updateFac2VarMsgs()
       //************************************************************************
       // Calculate the total sum of this factor and all its input messages
       //************************************************************************
-      DiscreteFunction msgSum(factors_i[fac]);
+      DiscreteFunction& msgSum = factorTotalValue_i[fac];
+      msgSum = factors_i[fac];
       V2FPostOffice::InMsgMap curInMsgs = var2facMsgs_i.curInMsgs(fac);
       typedef V2FPostOffice::InMsgIt InMsgIt;
       for(InMsgIt it=curInMsgs.begin(); it!=curInMsgs.end(); ++it)
diff --git a/tests/agg1Harness.cpp b/tests/agg1Harness.cpp
