Made cartesian product static, and added specialization in DiscreteVa…

…lues. Added markdown and html methods for the latter.
borglab · dellaert · Jan 10, 2022 · Jan 9, 2022 · Jan 9, 2022 · Jan 9, 2022
commit c1561dba02e3299a769ad788f1587c79bdfbeedc
diff --git a/examples/UGM_small.cpp b/examples/UGM_small.cpp
@@ -50,7 +50,8 @@ int main(int argc, char** argv) {
 
   // Print the UGM distribution
   cout << "\nUGM distribution:" << endl;
-  auto allPosbValues = cartesianProduct(Cathy & Heather & Mark & Allison);
+  auto allPosbValues =
+      DiscreteValues::CartesianProduct(Cathy & Heather & Mark & Allison);
   for (size_t i = 0; i < allPosbValues.size(); ++i) {
     DiscreteFactor::Values values = allPosbValues[i];
     double prodPot = graph(values);

diff --git a/gtsam/discrete/Assignment.h b/gtsam/discrete/Assignment.h
@@ -19,32 +19,30 @@
 #pragma once
 
 #include <iostream>
-#include <vector>
 #include <map>
-
+#include <utility>
+#include <vector>
 
 namespace gtsam {
 
-  /**
-   * An assignment from labels to value index (size_t).
-   * Assigns to each label a value. Implemented as a simple map.
-   * A discrete factor takes an Assignment and returns a value.
-   */
-  template<class L>
-  class Assignment: public std::map<L, size_t> {
-  public:
-    void print(const std::string& s = "Assignment: ") const {
-      std::cout << s << ": ";
-      for(const typename Assignment::value_type& keyValue: *this)
-        std::cout << "(" << keyValue.first << ", " << keyValue.second << ")";
-      std::cout << std::endl;
-    }
-
-    bool equals(const Assignment& other, double tol = 1e-9) const {
-      return (*this == other);
-    }
-  };  //Assignment
+/**
+ * An assignment from labels to value index (size_t).
+ * Assigns to each label a value. Implemented as a simple map.
+ * A discrete factor takes an Assignment and returns a value.
+ */
+template <class L>
+class Assignment : public std::map<L, size_t> {
+ public:
+  void print(const std::string& s = "Assignment: ") const {
+    std::cout << s << ": ";
+    for (const typename Assignment::value_type& keyValue : *this)
+      std::cout << "(" << keyValue.first << ", " << keyValue.second << ")";
+    std::cout << std::endl;
+  }
 
+  bool equals(const Assignment& other, double tol = 1e-9) const {
+    return (*this == other);
+  }
 
   /**
    * @brief Get Cartesian product consisting all possible configurations
@@ -58,29 +56,28 @@ namespace gtsam {
    * variables with each having cardinalities 4, we get 4096 possible
    * configurations!!
    */
-  template<typename L>
-  std::vector<Assignment<L> > cartesianProduct(
-      const std::vector<std::pair<L, size_t> >& keys) {
-    std::vector<Assignment<L> > allPossValues;
-    Assignment<L> values;
+  template <typename Derived = Assignment<L>>
+  static std::vector<Derived> CartesianProduct(
+      const std::vector<std::pair<L, size_t>>& keys) {
+    std::vector<Derived> allPossValues;
+    Derived values;
     typedef std::pair<L, size_t> DiscreteKey;
-    for(const DiscreteKey& key: keys)
-      values[key.first] = 0;  //Initialize from 0
+    for (const DiscreteKey& key : keys)
+      values[key.first] = 0;  // Initialize from 0
     while (1) {
       allPossValues.push_back(values);
       size_t j = 0;
       for (j = 0; j < keys.size(); j++) {
         L idx = keys[j].first;
         values[idx]++;
-        if (values[idx] < keys[j].second)
-          break;
-        //Wrap condition
+        if (values[idx] < keys[j].second) break;
+        // Wrap condition
         values[idx] = 0;
       }
-      if (j == keys.size())
-        break;
+      if (j == keys.size()) break;
     }
     return allPossValues;
   }
+};  // Assignment
 
-} // namespace gtsam
+}  // namespace gtsam
diff --git a/gtsam/discrete/DecisionTreeFactor.cpp b/gtsam/discrete/DecisionTreeFactor.cpp
@@ -22,6 +22,7 @@
 #include <gtsam/base/FastSet.h>
 
 #include <boost/make_shared.hpp>
+#include <utility>
 
 using namespace std;
 
@@ -150,9 +151,9 @@ namespace gtsam {
     for (auto& key : keys()) {
       pairs.emplace_back(key, cardinalities_.at(key));
     }
-    // Reverse to make cartesianProduct output a more natural ordering.
+    // Reverse to make cartesian product output a more natural ordering.
     std::vector<std::pair<Key, size_t>> rpairs(pairs.rbegin(), pairs.rend());
-    const auto assignments = cartesianProduct(rpairs);
+    const auto assignments = DiscreteValues::CartesianProduct(rpairs);
 
     // Construct unordered_map with values
     std::vector<std::pair<DiscreteValues, double>> result;
@@ -212,7 +213,7 @@ namespace gtsam {
       auto assignment = kv.first;
       for (auto& key : keys()) {
         size_t index = assignment.at(key);
-        ss << Translate(names, key, index) << "|";
+        ss << DiscreteValues::Translate(names, key, index) << "|";
       }
       ss << kv.second << "|\n";
     }
@@ -244,7 +245,7 @@ namespace gtsam {
       auto assignment = kv.first;
       for (auto& key : keys()) {
         size_t index = assignment.at(key);
-        ss << "<th>" << Translate(names, key, index) << "</th>";
+        ss << "<th>" << DiscreteValues::Translate(names, key, index) << "</th>";
       }
       ss << "<td>" << kv.second << "</td>";  // value
       ss << "</tr>\n";

diff --git a/gtsam/discrete/DiscreteConditional.cpp b/gtsam/discrete/DiscreteConditional.cpp
@@ -180,35 +180,30 @@ DecisionTreeFactor::shared_ptr DiscreteConditional::likelihood(
   return likelihood(values);
 }
 
-/* ******************************************************************************** */
+/* ************************************************************************** */
 void DiscreteConditional::solveInPlace(DiscreteValues* values) const {
-  // TODO: Abhijit asks: is this really the fastest way? He thinks it is.
-  ADT pFS = Choose(*this, *values); // P(F|S=parentsValues)
+  // TODO(Abhijit): is this really the fastest way? He thinks it is.
+  ADT pFS = Choose(*this, *values);  // P(F|S=parentsValues)
 
   // Initialize
   DiscreteValues mpe;
   double maxP = 0;
 
-  DiscreteKeys keys;
-  for(Key idx: frontals()) {
-    DiscreteKey dk(idx, cardinality(idx));
-    keys & dk;
-  }
   // Get all Possible Configurations
-  const auto allPosbValues = cartesianProduct(keys);
+  const auto allPosbValues = frontalAssignments();
 
   // Find the MPE
-  for(const auto& frontalVals: allPosbValues) {
-    double pValueS = pFS(frontalVals); // P(F=value|S=parentsValues)
+  for (const auto& frontalVals : allPosbValues) {
+    double pValueS = pFS(frontalVals);  // P(F=value|S=parentsValues)
     // Update MPE solution if better
     if (pValueS > maxP) {
       maxP = pValueS;
       mpe = frontalVals;
     }
   }
 
-  //set values (inPlace) to mpe
-  for(Key j: frontals()) {
+  // set values (inPlace) to mpe
+  for (Key j : frontals()) {
     (*values)[j] = mpe[j];
   }
 }
@@ -295,20 +290,20 @@ size_t DiscreteConditional::sample() const {
 }
 
 /* ************************************************************************* */
-vector<Assignment<Key>> DiscreteConditional::frontalAssignments() const {
+vector<DiscreteValues> DiscreteConditional::frontalAssignments() const {
   vector<pair<Key, size_t>> pairs;
   for (Key key : frontals()) pairs.emplace_back(key, cardinalities_.at(key));
   vector<pair<Key, size_t>> rpairs(pairs.rbegin(), pairs.rend());
-  return cartesianProduct(rpairs);
+  return DiscreteValues::CartesianProduct(rpairs);
 }
 
 /* ************************************************************************* */
-vector<Assignment<Key>> DiscreteConditional::allAssignments() const {
+vector<DiscreteValues> DiscreteConditional::allAssignments() const {
   vector<pair<Key, size_t>> pairs;
   for (Key key : parents()) pairs.emplace_back(key, cardinalities_.at(key));
   for (Key key : frontals()) pairs.emplace_back(key, cardinalities_.at(key));
   vector<pair<Key, size_t>> rpairs(pairs.rbegin(), pairs.rend());
-  return cartesianProduct(rpairs);
+  return DiscreteValues::CartesianProduct(rpairs);
 }
 
 /* ************************************************************************* */
@@ -358,7 +353,7 @@ std::string DiscreteConditional::markdown(const KeyFormatter& keyFormatter,
   for (const auto& a : frontalAssignments) {
     for (auto&& it = beginFrontals(); it != endFrontals(); ++it) {
       size_t index = a.at(*it);
-      ss << Translate(names, *it, index);
+      ss << DiscreteValues::Translate(names, *it, index);
     }
     ss << "|";
   }
@@ -377,7 +372,7 @@ std::string DiscreteConditional::markdown(const KeyFormatter& keyFormatter,
       ss << "|";
       for (auto&& it = beginParents(); it != endParents(); ++it) {
         size_t index = a.at(*it);
-        ss << Translate(names, *it, index) << "|";
+        ss << DiscreteValues::Translate(names, *it, index) << "|";
       }
     }
     ss << operator()(a) << "|";
@@ -413,7 +408,7 @@ string DiscreteConditional::html(const KeyFormatter& keyFormatter,
     ss << "<th>";
     for (auto&& it = beginFrontals(); it != endFrontals(); ++it) {
       size_t index = a.at(*it);
-      ss << Translate(names, *it, index);
+      ss << DiscreteValues::Translate(names, *it, index);
     }
     ss << "</th>";
   }
@@ -429,7 +424,7 @@ string DiscreteConditional::html(const KeyFormatter& keyFormatter,
       ss << "    <tr>";
       for (auto&& it = beginParents(); it != endParents(); ++it) {
         size_t index = a.at(*it);
-        ss << "<th>" << Translate(names, *it, index) << "</th>";
+        ss << "<th>" << DiscreteValues::Translate(names, *it, index) << "</th>";
       }
     }
     ss << "<td>" << operator()(a) << "</td>";  // value

diff --git a/gtsam/discrete/DiscreteConditional.h b/gtsam/discrete/DiscreteConditional.h
@@ -25,6 +25,7 @@
 #include <boost/make_shared.hpp>
 #include <boost/shared_ptr.hpp>
 #include <string>
+#include <vector>
 
 namespace gtsam {
 
@@ -182,10 +183,10 @@ class GTSAM_EXPORT DiscreteConditional
   void sampleInPlace(DiscreteValues* parentsValues) const;
 
   /// Return all assignments for frontal variables.
-  std::vector<Assignment<Key>> frontalAssignments() const;
+  std::vector<DiscreteValues> frontalAssignments() const;
 
   /// Return all assignments for frontal *and* parent variables.
-  std::vector<Assignment<Key>> allAssignments() const;
+  std::vector<DiscreteValues> allAssignments() const;
 
   /// @}
   /// @name Wrapper support

diff --git a/gtsam/discrete/DiscreteFactor.cpp b/gtsam/discrete/DiscreteFactor.cpp
@@ -25,14 +25,4 @@ using namespace std;
 
 namespace gtsam {
 
-string DiscreteFactor::Translate(const Names& names, Key key, size_t index) {
-  if (names.empty()) {
-    stringstream ss;
-    ss << index;
-    return ss.str();
-  } else {
-    return names.at(key)[index];
-  }
-}
-
 }  // namespace gtsam
diff --git a/gtsam/discrete/DiscreteFactor.h b/gtsam/discrete/DiscreteFactor.h
@@ -22,6 +22,7 @@
 #include <gtsam/inference/Factor.h>
 #include <gtsam/base/Testable.h>
 
+#include <string>
 namespace gtsam {
 
 class DecisionTreeFactor;
@@ -90,14 +91,11 @@ class GTSAM_EXPORT DiscreteFactor: public Factor {
   /// @{
 
   /// Translation table from values to strings.
-  using Names = std::map<Key, std::vector<std::string>>;
-
-  /// Translate an integer index value for given key to a string.
-  static std::string Translate(const Names& names, Key key, size_t index);
+  using Names = DiscreteValues::Names;
 
   /**
    * @brief Render as markdown table
-   * 
+   *
    * @param keyFormatter GTSAM-style Key formatter.
    * @param names optional, category names corresponding to choices.
    * @return std::string a markdown string.

diff --git a/gtsam/discrete/DiscreteValues.cpp b/gtsam/discrete/DiscreteValues.cpp
@@ -0,0 +1,86 @@
+/* ----------------------------------------------------------------------------
+
+ * GTSAM Copyright 2010, Georgia Tech Research Corporation,
+ * Atlanta, Georgia 30332-0415
+ * All Rights Reserved
+ * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
+
+ * See LICENSE for the license information
+
+ * -------------------------------------------------------------------------- */
+
+/**
+ *  @file DiscreteValues.cpp
+ *  @date January, 2022
+ *  @author Frank Dellaert
+ */
+
+#include <gtsam/discrete/DiscreteValues.h>
+
+#include <sstream>
+
+using std::cout;
+using std::endl;
+using std::string;
+using std::stringstream;
+
+namespace gtsam {
+
+void DiscreteValues::print(const string& s,
+                           const KeyFormatter& keyFormatter) const {
+  cout << s << ": ";
+  for (auto&& kv : *this)
+    cout << "(" << keyFormatter(kv.first) << ", " << kv.second << ")";
+  cout << endl;
+}
+
+string DiscreteValues::Translate(const Names& names, Key key, size_t index) {
+  if (names.empty()) {
+    stringstream ss;
+    ss << index;
+    return ss.str();
+  } else {
+    return names.at(key)[index];
+  }
+}
+
+string DiscreteValues::markdown(const KeyFormatter& keyFormatter,
+                                const Names& names) const {
+  stringstream ss;
+
+  // Print out header and separator with alignment hints.
+  ss << "|Variable|value|\n|:-:|:-:|\n";
+
+  // Print out all rows.
+  for (const auto& kv : *this) {
+    ss << "|" << keyFormatter(kv.first) << "|"
+       << Translate(names, kv.first, kv.second) << "|\n";
+  }
+
+  return ss.str();
+}
+
+std::string DiscreteValues::html(const KeyFormatter& keyFormatter,
+                                 const Names& names) const {
+  stringstream ss;
+
+  // Print out preamble.
+  ss << "<div>\n<table class=\'DiscreteValues\'>\n  <thead>\n";
+
+  // Print out header row.
+  ss << "    <tr><th>Variable</th><th>value</th></tr>\n";
+
+  // Finish header and start body.
+  ss << "  </thead>\n  <tbody>\n";
+
+  // Print out all rows.
+  for (const auto& kv : *this) {
+    ss << "    <tr>";
+    ss << "<th>" << keyFormatter(kv.first) << "</th><td>\'"
+       << Translate(names, kv.first, kv.second) << "</td>";
+    ss << "</tr>\n";
+  }
+  ss << "  </tbody>\n</table>\n</div>";
+  return ss.str();
+}
+}  // namespace gtsam