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  import java.util.Set;
30  import java.util.TreeSet;
31  
32  import org.sat4j.core.VecInt;
33  import org.sat4j.specs.ContradictionException;
34  import org.sat4j.specs.ISolver;
35  import org.sat4j.specs.IVec;
36  import org.sat4j.specs.IVecInt;
37  
38  public class GeneralizedSupportEncoding implements Encoding {
39  
40      private final Map<Set<Integer>, IVecInt> supports = new HashMap<Set<Integer>, IVecInt>();
41  
42      private static final Encoding instance = new GeneralizedSupportEncoding();
43  
44      private GeneralizedSupportEncoding() {
45  
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          // TODO Auto-generated method stub
55  
56      }
57  
58      public void onInit(ISolver solver, IVec<Var> scope) {
59          supports.clear();
60          int[] acc = new int[scope.size()];
61          fill(0, scope, acc, supports);
62      }
63  
64      public void onNogood(ISolver solver, IVec<Var> scope,
65              Map<Evaluable, Integer> tuple) throws ContradictionException {
66  
67      }
68  
69      public void onSupport(ISolver solver, IVec<Var> scope,
70              Map<Evaluable, Integer> tuple) throws ContradictionException {
71          for (int i = 0; i < scope.size(); i++) {
72              Set<Integer> set = new TreeSet<Integer>();
73              Var vari = scope.get(i);
74              for (int j = 0; j < scope.size(); j++) {
75                  if (i != j) {
76                      set.add(scope.get(j).translate(tuple.get(vari)));
77                  }
78              }
79              IVecInt support = supports.get(set);
80              assert support != null;
81              support.push(vari.translate(tuple.get(vari)));
82          }
83  
84      }
85  
86      private void fill(int n, IVec<Var> scope, int[] acc,
87              Map<Set<Integer>, IVecInt> supports) {
88          if (n == scope.size()) {
89              for (int j = 0; j < acc.length; j++) {
90                  Set<Integer> set = new TreeSet<Integer>();
91                  for (int i = 0; i < acc.length; i++)
92                      if (i != j)
93                          set.add(scope.get(i).translate(acc[i]));
94                  supports.put(set, new VecInt());
95              }
96          } else
97              for (int i : scope.get(n).domain()) {
98                  acc[n] = i;
99                  fill(n + 1, scope, acc, supports);
100             }
101 
102     }
103 }