gtsam  4.0.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(OptionalOrdering ordering = boost::none) const;
64 
65 // /*
66 // * Perform loopy belief propagation
67 // * True belief propagation would check for each value in domain
68 // * whether any satisfying separator assignment can be found.
69 // * This corresponds to hyper-arc consistency in CSP speak.
70 // * This can be done by creating a mini-factor graph and search.
71 // * For a nine-by-nine Sudoku, the search tree will be 8+6+6=20 levels deep.
72 // * It will be very expensive to exclude values that way.
73 // */
74 // void applyBeliefPropagation(size_t nrIterations = 10) const;
75 
76  /*
77  * Apply arc-consistency ~ Approximate loopy belief propagation
78  * We need to give the domains to a constraint, and it returns
79  * a domain whose values don't conflict in the arc-consistency way.
80  * TODO: should get cardinality from Indices
81  */
82  void runArcConsistency(size_t cardinality, size_t nrIterations = 10,
83  bool print = false) const;
84  }; // CSP
85 
86 } // gtsam
87 
void addAllDiff(const DiscreteKeys &dkeys)
Add a general AllDiff constraint.
Definition: CSP.h:49
A Discrete Factor Graph is a factor graph where all factors are Discrete, i.e.
Definition: DiscreteFactorGraph.h:65
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition: Matrix.cpp:141
SingleValue constraint.
Definition: SingleValue.h:18
Binary AllDiff constraint Returns 1 if values for two keys are different, 0 otherwise DiscreteFactors...
Definition: BinaryAllDiff.h:23
void addAllDiff(const DiscreteKey &key1, const DiscreteKey &key2)
Add a binary AllDiff constraint.
Definition: CSP.h:42
void addSingleValue(const DiscreteKey &dkey, size_t value)
Add a unary constraint, allowing only a single value.
Definition: CSP.h:36
Constraint Satisfaction Problem class A specialization of a DiscreteFactorGraph.
Definition: CSP.h:21
An assignment from labels to value index (size_t).
Definition: Assignment.h:34
KeyVector Indices
A map from keys to values.
Definition: CSP.h:25
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:56
std::pair< Key, size_t > DiscreteKey
Key type for discrete conditionals Includes name and cardinality.
Definition: DiscreteKey.h:34
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
General AllDiff constraint Returns 1 if values for all keys are different, 0 otherwise DiscreteFactor...
Definition: AllDiff.h:22
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:37