AllDiff.cpp
Go to the documentation of this file.
1 /*
2  * AllDiff.cpp
3  * @brief General "all-different" constraint
4  * @date Feb 6, 2012
5  * @author Frank Dellaert
6  */
7 
8 #include <gtsam/base/Testable.h>
11 
12 #include <optional>
13 
14 namespace gtsam {
15 
16 /* ************************************************************************* */
17 AllDiff::AllDiff(const DiscreteKeys& dkeys) : Constraint(dkeys.indices()) {
18  for (const DiscreteKey& dkey : dkeys) cardinalities_.insert(dkey);
19 }
20 
21 /* ************************************************************************* */
22 void AllDiff::print(const std::string& s, const KeyFormatter& formatter) const {
23  std::cout << s << "AllDiff on ";
24  for (Key dkey : keys_) std::cout << formatter(dkey) << " ";
25  std::cout << std::endl;
26 }
27 
28 /* ************************************************************************* */
30  std::set<size_t> taken; // record values taken by keys
31  for (Key dkey : keys_) {
32  size_t value = values.at(dkey); // get the value for that key
33  if (taken.count(value)) return 0.0; // check if value alreday taken
34  taken.insert(value); // if not, record it as taken and keep checking
35  }
36  return 1.0;
37 }
38 
39 /* ************************************************************************* */
41  // We will do this by converting the allDif into many BinaryAllDiff
42  // constraints
43  DecisionTreeFactor converted;
44  size_t nrKeys = keys_.size();
45  for (size_t i1 = 0; i1 < nrKeys; i1++)
46  for (size_t i2 = i1 + 1; i2 < nrKeys; i2++) {
47  BinaryAllDiff binary12(discreteKey(i1), discreteKey(i2));
48  converted = converted * binary12.toDecisionTreeFactor();
49  }
50  return converted;
51 }
52 
53 /* ************************************************************************* */
55  // TODO: can we do this more efficiently?
56  return toDecisionTreeFactor() * f;
57 }
58 
59 /* ************************************************************************* */
60 bool AllDiff::ensureArcConsistency(Key j, Domains* domains) const {
61  Domain& Dj = domains->at(j);
62 
63  // Though strictly not part of allDiff, we check for
64  // a value in domains->at(j) that does not occur in any other connected domain.
65  // If found, we make this a singleton...
66  // TODO: make a new constraint where this really is true
67  std::optional<Domain> maybeChanged = Dj.checkAllDiff(keys_, *domains);
68  if (maybeChanged) {
69  Dj = *maybeChanged;
70  return true;
71  }
72 
73  // Check all other domains for singletons and erase corresponding values.
74  // This is the same as arc-consistency on the equivalent binary constraints
75  bool changed = false;
76  for (Key k : keys_)
77  if (k != j) {
78  const Domain& Dk = domains->at(k);
79  if (Dk.isSingleton()) { // check if singleton
80  size_t value = Dk.firstValue();
81  if (Dj.contains(value)) {
82  Dj.erase(value); // erase value if true
83  changed = true;
84  }
85  }
86  }
87  return changed;
88 }
89 
90 /* ************************************************************************* */
92  DiscreteKeys newKeys;
93  // loop over keys and add them only if they do not appear in values
94  for (Key k : keys_)
95  if (values.find(k) == values.end()) {
96  newKeys.push_back(DiscreteKey(k, cardinalities_.at(k)));
97  }
98  return std::make_shared<AllDiff>(newKeys);
99 }
100 
101 /* ************************************************************************* */
103  const Domains& domains) const {
104  DiscreteValues known;
105  for (Key k : keys_) {
106  const Domain& Dk = domains.at(k);
107  if (Dk.isSingleton()) known[k] = Dk.firstValue();
108  }
109  return partiallyApply(known);
110 }
111 
112 /* ************************************************************************* */
113 } // namespace gtsam
gtsam::AllDiff::operator()
double operator()(const DiscreteValues &values) const override
Calculate value = expensive !
Definition: AllDiff.cpp:29
gtsam::AllDiff::cardinalities_
std::map< Key, size_t > cardinalities_
Definition: AllDiff.h:20
gtsam::DecisionTreeFactor
Definition: DecisionTreeFactor.h:44
gtsam::Domain::isSingleton
bool isSingleton() const
Definition: Domain.h:54
gtsam::Domain::contains
bool contains(size_t value) const
Definition: Domain.h:82
gtsam::AllDiff::print
void print(const std::string &s="", const KeyFormatter &formatter=DefaultKeyFormatter) const override
print
Definition: AllDiff.cpp:22
s
RealScalar s
Definition: level1_cplx_impl.h:126
Testable.h
Concept check for values that can be used in unit tests.
gtsam::BinaryAllDiff::toDecisionTreeFactor
DecisionTreeFactor toDecisionTreeFactor() const override
Convert into a decisiontree.
Definition: BinaryAllDiff.h:55
nrKeys
static const size_t nrKeys
Definition: testRegularJacobianFactor.cpp:31
formatter
const KeyFormatter & formatter
Definition: treeTraversal-inst.h:204
different_sigmas::values
HybridValues values
Definition: testHybridBayesNet.cpp:245
gtsam::DiscreteKeys
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:41
gtsam::BinaryAllDiff
Definition: BinaryAllDiff.h:20
gtsam::AllDiff::ensureArcConsistency
bool ensureArcConsistency(Key j, Domains *domains) const override
Definition: AllDiff.cpp:60
gtsam::Domain::erase
void erase(size_t value)
Erase a value, non const :-(.
Definition: Domain.h:50
test_eigen_tensor.indices
indices
Definition: test_eigen_tensor.py:33
AllDiff.h
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
gtsam::AllDiff::discreteKey
DiscreteKey discreteKey(size_t i) const
Definition: AllDiff.h:22
gtsam::KeyFormatter
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition: Key.h:35
gtsam::Domain
Definition: Domain.h:20
gtsam::Domains
std::map< Key, Domain > Domains
Definition: Constraint.h:29
gtsam::Domain::checkAllDiff
std::optional< Domain > checkAllDiff(const KeyVector keys, const Domains &domains) const
Definition: Domain.cpp:63
gtsam::AllDiff::partiallyApply
Constraint::shared_ptr partiallyApply(const DiscreteValues &) const override
Partially apply known values.
Definition: AllDiff.cpp:91
tree::f
Point2(* f)(const Point3 &, OptionalJacobian< 2, 3 >)
Definition: testExpression.cpp:218
Domain.h
gtsam::AllDiff::toDecisionTreeFactor
DecisionTreeFactor toDecisionTreeFactor() const override
Convert into a decisiontree, can be very expensive !
Definition: AllDiff.cpp:40
gtsam
traits
Definition: SFMdata.h:40
gtsam::Factor::keys_
KeyVector keys_
The keys involved in this factor.
Definition: Factor.h:88
i1
double i1(double x)
Definition: i1.c:150
gtsam::DiscreteValues
Definition: DiscreteValues.h:34
gtsam::DiscreteKey
std::pair< Key, size_t > DiscreteKey
Definition: DiscreteKey.h:38
gtsam::AllDiff::AllDiff
AllDiff(const DiscreteKeys &dkeys)
Construct from keys.
Definition: AllDiff.cpp:17
gtsam::AllDiff::operator*
DecisionTreeFactor operator*(const DecisionTreeFactor &f) const override
Multiply into a decisiontree.
Definition: AllDiff.cpp:54
gtsam::Domain::firstValue
size_t firstValue() const
Definition: Domain.h:56
gtsam::Constraint::shared_ptr
std::shared_ptr< Constraint > shared_ptr
Definition: Constraint.h:37
gtsam::Constraint
Definition: Constraint.h:35
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:97
test_callbacks.value
value
Definition: test_callbacks.py:160


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:01:48