gtsam  4.1.0
gtsam
CSP.h
1 /*
2  * CSP.h
3  * @brief Constraint Satisfaction Problem class
4  * @date Feb 6, 2012
5  * @author Frank Dellaert
6  */
7 
8 #pragma once
9 
10 #include <gtsam_unstable/discrete/AllDiff.h>
11 #include <gtsam_unstable/discrete/SingleValue.h>
13 
14 namespace gtsam {
15 
21  class GTSAM_UNSTABLE_EXPORT CSP: public DiscreteFactorGraph {
22  public:
23 
25  typedef KeyVector Indices;
26  typedef Assignment<Key> Values;
27  typedef boost::shared_ptr<Values> sharedValues;
28 
29  public:
30 
31 // /// Constructor
32 // CSP() {
33 // }
34 
36  void addSingleValue(const DiscreteKey& dkey, size_t value) {
37  boost::shared_ptr<SingleValue> factor(new SingleValue(dkey, value));
38  push_back(factor);
39  }
40 
42  void addAllDiff(const DiscreteKey& key1, const DiscreteKey& key2) {
43  boost::shared_ptr<BinaryAllDiff> factor(
44  new BinaryAllDiff(key1, key2));
45  push_back(factor);
46  }
47 
49  void addAllDiff(const DiscreteKeys& dkeys) {
50  boost::shared_ptr<AllDiff> factor(new AllDiff(dkeys));
51  push_back(factor);
52  }
53 
54 // /** return product of all factors as a single factor */
55 // DecisionTreeFactor product() const {
56 // DecisionTreeFactor result;
57 // for(const sharedFactor& factor: *this)
58 // if (factor) result = (*factor) * result;
59 // return result;
60 // }
61 
63  sharedValues optimalAssignment() const;
64 
66  sharedValues optimalAssignment(const Ordering& ordering) const;
67 
68 // /*
69 // * Perform loopy belief propagation
70 // * True belief propagation would check for each value in domain
71 // * whether any satisfying separator assignment can be found.
72 // * This corresponds to hyper-arc consistency in CSP speak.
73 // * This can be done by creating a mini-factor graph and search.
74 // * For a nine-by-nine Sudoku, the search tree will be 8+6+6=20 levels deep.
75 // * It will be very expensive to exclude values that way.
76 // */
77 // void applyBeliefPropagation(size_t nrIterations = 10) const;
78 
79  /*
80  * Apply arc-consistency ~ Approximate loopy belief propagation
81  * We need to give the domains to a constraint, and it returns
82  * a domain whose values don't conflict in the arc-consistency way.
83  * TODO: should get cardinality from Indices
84  */
85  void runArcConsistency(size_t cardinality, size_t nrIterations = 10,
86  bool print = false) const;
87  }; // CSP
88 
89 } // gtsam
90 
gtsam::DiscreteKey
std::pair< Key, size_t > DiscreteKey
Key type for discrete conditionals Includes name and cardinality.
Definition: DiscreteKey.h:34
gtsam::Ordering
Definition: Ordering.h:34
gtsam::BinaryAllDiff
Binary AllDiff constraint Returns 1 if values for two keys are different, 0 otherwise DiscreteFactors...
Definition: BinaryAllDiff.h:23
gtsam::Assignment
An assignment from labels to value index (size_t).
Definition: Assignment.h:34
gtsam::CSP::Indices
KeyVector Indices
A map from keys to values.
Definition: CSP.h:25
gtsam::CSP::addAllDiff
void addAllDiff(const DiscreteKeys &dkeys)
Add a general AllDiff constraint.
Definition: CSP.h:49
gtsam::CSP
Constraint Satisfaction Problem class A specialization of a DiscreteFactorGraph.
Definition: CSP.h:21
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::print
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition: Matrix.cpp:155
gtsam::CSP::addSingleValue
void addSingleValue(const DiscreteKey &dkey, size_t value)
Add a unary constraint, allowing only a single value.
Definition: CSP.h:36
gtsam::DiscreteFactorGraph
A Discrete Factor Graph is a factor graph where all factors are Discrete, i.e.
Definition: DiscreteFactorGraph.h:66
gtsam::SingleValue
SingleValue constraint.
Definition: SingleValue.h:18
gtsam::AllDiff
General AllDiff constraint Returns 1 if values for all keys are different, 0 otherwise DiscreteFactor...
Definition: AllDiff.h:22
gtsam::KeyVector
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:86
DiscreteFactorGraph.h
gtsam::CSP::addAllDiff
void addAllDiff(const DiscreteKey &key1, const DiscreteKey &key2)
Add a binary AllDiff constraint.
Definition: CSP.h:42
gtsam::DiscreteKeys
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:37