View Javadoc

1   /*
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2006 Daniel Le Berre
3    * 
4    * Based on the original minisat specification from:
5    * 
6    * An extensible SAT solver. Niklas E?n and Niklas S?rensson. Proceedings of the
7    * Sixth International Conference on Theory and Applications of Satisfiability
8    * Testing, LNCS 2919, pp 502-518, 2003.
9    * 
10   * This library is free software; you can redistribute it and/or modify it under
11   * the terms of the GNU Lesser General Public License as published by the Free
12   * Software Foundation; either version 2.1 of the License, or (at your option)
13   * any later version.
14   * 
15   * This library is distributed in the hope that it will be useful, but WITHOUT
16   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17   * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18   * details.
19   * 
20   * You should have received a copy of the GNU Lesser General Public License
21   * along with this library; if not, write to the Free Software Foundation, Inc.,
22   * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23   * 
24   */
25  package org.sat4j.reader.csp;
26  
27  import java.util.HashMap;
28  import java.util.Map;
29  
30  import org.sat4j.core.VecInt;
31  import org.sat4j.specs.ContradictionException;
32  import org.sat4j.specs.ISolver;
33  import org.sat4j.specs.IVec;
34  import org.sat4j.specs.IVecInt;
35  
36  public class BinarySupportEncoding implements Encoding {
37  
38      private final Map<Integer, IVecInt> supportsa = new HashMap<Integer, IVecInt>();
39  
40      private final Map<Integer, IVecInt> supportsb = new HashMap<Integer, IVecInt>();
41  
42      private static final Encoding instance = new BinarySupportEncoding();
43  
44      private BinarySupportEncoding() {
45          // nothing here
46      }
47  
48      public static Encoding instance() {
49          return instance;
50      }
51  
52      public void onFinish(ISolver solver, IVec<Var> scope)
53              throws ContradictionException {
54          generateClauses(scope.get(0), supportsa, solver);
55          generateClauses(scope.get(1), supportsb, solver);
56  
57      }
58  
59      public void onInit(ISolver solver, IVec<Var> scope) {
60          supportsa.clear();
61          supportsb.clear();
62      }
63  
64      public void onNogood(ISolver solver, IVec<Var> scope,
65              Map<Evaluable, Integer> tuple) throws ContradictionException {
66      }
67  
68      public void onSupport(ISolver solver, IVec<Var> scope,
69              Map<Evaluable, Integer> tuple) throws ContradictionException {
70          Var vara = scope.get(0);
71          int va = tuple.get(vara);
72          Var varb = scope.get(1);
73          int vb = tuple.get(varb);
74          addSupport(va, varb, vb, supportsa);
75          addSupport(vb, vara, va, supportsb);
76      }
77  
78      private void addSupport(int head, Evaluable v, int value,
79              Map<Integer, IVecInt> supports) {
80          IVecInt sup = supports.get(head);
81          if (sup == null) {
82              sup = new VecInt();
83              supports.put(head, sup);
84          }
85          sup.push(v.translate(value));
86      }
87  
88      private void generateClauses(Evaluable v, Map<Integer, IVecInt> supports,
89              ISolver solver) throws ContradictionException {
90          IVecInt clause = new VecInt();
91          for (int key : v.domain()) {
92              clause.clear();
93              IVecInt support = supports.get(key);
94              clause.push(-v.translate(key));
95              if (support != null) {
96                  for (int i : support)
97                      clause.push(i);
98              }
99              solver.addClause(clause);
100         }
101     }
102 
103 }