gtsam 4.1.1 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
11#include <gtsam_unstable/discrete/AllDiff.h>
12#include <gtsam_unstable/discrete/SingleValue.h>
13
14namespace gtsam {
15
21class GTSAM_UNSTABLE_EXPORT CSP : public DiscreteFactorGraph {
22 public:
25 typedef Assignment<Key> Values;
26 typedef boost::shared_ptr<Values> sharedValues;
27
28 public:
29 // /// Constructor
30 // CSP() {
31 // }
32
34 void addSingleValue(const DiscreteKey& dkey, size_t value) {
35 boost::shared_ptr<SingleValue> factor(new SingleValue(dkey, value));
36 push_back(factor);
37 }
38
40 void addAllDiff(const DiscreteKey& key1, const DiscreteKey& key2) {
41 boost::shared_ptr<BinaryAllDiff> factor(new BinaryAllDiff(key1, key2));
42 push_back(factor);
43 }
44
46 void addAllDiff(const DiscreteKeys& dkeys) {
47 boost::shared_ptr<AllDiff> factor(new AllDiff(dkeys));
48 push_back(factor);
49 }
50
51 // /** return product of all factors as a single factor */
52 // DecisionTreeFactor product() const {
53 // DecisionTreeFactor result;
54 // for(const sharedFactor& factor: *this)
55 // if (factor) result = (*factor) * result;
56 // return result;
57 // }
58
60 sharedValues optimalAssignment() const;
61
63 sharedValues optimalAssignment(const Ordering& ordering) 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
72 // deep.
73 // * It will be very expensive to exclude values that way.
74 // */
75 // void applyBeliefPropagation(size_t nrIterations = 10) const;
76
77 /*
78 * Apply arc-consistency ~ Approximate loopy belief propagation
79 * We need to give the domains to a constraint, and it returns
80 * a domain whose values don't conflict in the arc-consistency way.
81 * TODO: should get cardinality from Indices
82 */
83 void runArcConsistency(size_t cardinality, size_t nrIterations = 10,
84 bool print = false) const;
85}; // CSP
86
87} // namespace gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:86
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition: Matrix.cpp:155
std::pair< Key, size_t > DiscreteKey
Key type for discrete conditionals Includes name and cardinality.
Definition: DiscreteKey.h:34
An assignment from labels to value index (size_t).
Definition: Assignment.h:34
A Discrete Factor Graph is a factor graph where all factors are Discrete, i.e.
Definition: DiscreteFactorGraph.h:66
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:37
Definition: Ordering.h:34
General AllDiff constraint Returns 1 if values for all keys are different, 0 otherwise DiscreteFactor...
Definition: AllDiff.h:22
Binary AllDiff constraint Returns 1 if values for two keys are different, 0 otherwise DiscreteFactors...
Definition: BinaryAllDiff.h:23
Constraint Satisfaction Problem class A specialization of a DiscreteFactorGraph.
Definition: CSP.h:21
void addSingleValue(const DiscreteKey &dkey, size_t value)
Add a unary constraint, allowing only a single value.
Definition: CSP.h:34
KeyVector Indices
A map from keys to values.
Definition: CSP.h:24