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/discrete/DiscreteFactorGraph.h>
11#include <gtsam_unstable/discrete/AllDiff.h>
12#include <gtsam_unstable/discrete/SingleValue.h>
13
14namespace gtsam {
15
16/**
17 * Constraint Satisfaction Problem class
18 * A specialization of a DiscreteFactorGraph.
19 * It knows about CSP-specific constraints and algorithms
20 */
21class GTSAM_UNSTABLE_EXPORT CSP : public DiscreteFactorGraph {
22 public:
23 using Values = DiscreteValues; ///< backwards compatibility
24
25 /// Add a unary constraint, allowing only a single value
26 void addSingleValue(const DiscreteKey& dkey, size_t value) {
27 emplace_shared<SingleValue>(args: dkey, args&: value);
28 }
29
30 /// Add a binary AllDiff constraint
31 void addAllDiff(const DiscreteKey& key1, const DiscreteKey& key2) {
32 emplace_shared<BinaryAllDiff>(args: key1, args: key2);
33 }
34
35 /// Add a general AllDiff constraint
36 void addAllDiff(const DiscreteKeys& dkeys) { emplace_shared<AllDiff>(args: dkeys); }
37
38 // /** return product of all factors as a single factor */
39 // DecisionTreeFactor product() const {
40 // DecisionTreeFactor result;
41 // for(const sharedFactor& factor: *this)
42 // if (factor) result = (*factor) * result;
43 // return result;
44 // }
45
46 // /*
47 // * Perform loopy belief propagation
48 // * True belief propagation would check for each value in domain
49 // * whether any satisfying separator assignment can be found.
50 // * This corresponds to hyper-arc consistency in CSP speak.
51 // * This can be done by creating a mini-factor graph and search.
52 // * For a nine-by-nine Sudoku, the search tree will be 8+6+6=20 levels
53 // deep.
54 // * It will be very expensive to exclude values that way.
55 // */
56 // void applyBeliefPropagation(size_t maxIterations = 10) const;
57
58 /*
59 * Apply arc-consistency ~ Approximate loopy belief propagation
60 * We need to give the domains to a constraint, and it returns
61 * a domain whose values don't conflict in the arc-consistency way.
62 * TODO: should get cardinality from DiscreteKeys
63 */
64 Domains runArcConsistency(size_t cardinality,
65 size_t maxIterations = 10) const;
66
67 /// Run arc consistency for all variables, return true if any domain changed.
68 bool runArcConsistency(const VariableIndex& index, Domains* domains) const;
69
70 /*
71 * Create a new CSP, applying the given Domain constraints.
72 */
73 CSP partiallyApply(const Domains& domains) const;
74}; // CSP
75
76} // namespace gtsam
77