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  
26  package org.sat4j.tools;
27  
28  import org.sat4j.core.VecInt;
29  import org.sat4j.specs.ContradictionException;
30  import org.sat4j.specs.ISolver;
31  import org.sat4j.specs.IVecInt;
32  import org.sat4j.specs.TimeoutException;
33  
34  /**
35   * Computes models with a minimal subset (with respect to set inclusion) of
36   * negative literals. This is done be adding a clause containing the negation of
37   * the negative literals appearing in the model found (which prevents any
38   * interpretation containing that subset of negative literals to be a model of
39   * the formula).
40   * 
41   * Computes only one model minimal for inclusion, since there is currently no
42   * way to save the state of the solver.
43   * 
44   * @author leberre
45   * 
46   * @see org.sat4j.specs.ISolver#addClause(IVecInt)
47   */
48  public class Minimal4InclusionModel extends SolverDecorator {
49  
50      private static final long serialVersionUID = 1L;
51  
52      /**
53       * @param solver
54       */
55      public Minimal4InclusionModel(ISolver solver) {
56          super(solver);
57      }
58  
59      /*
60       * (non-Javadoc)
61       * 
62       * @see org.sat4j.ISolver#model()
63       */
64      @Override
65      public int[] model() {
66          int[] prevmodel = null;
67          IVecInt vec = new VecInt();
68          IVecInt cube = new VecInt();
69          // backUp();
70          try {
71              do {
72                  prevmodel = super.model();
73                  vec.clear();
74                  cube.clear();
75                  for (int q : prevmodel) {
76                      if (q < 0) {
77                          vec.push(-q);
78                      } else {
79                          cube.push(q);
80                      }
81                  }
82                  // System.out.println("minimizing " + vec + "/" + cube);
83                  addClause(vec);
84              } while (isSatisfiable(cube));
85          } catch (TimeoutException e) {
86              // System.err.println("Solver timed out");
87          } catch (ContradictionException e) {
88              // System.out.println("added trivial unsat clauses?" + vec);
89          }
90          // restore();
91          int[] newmodel = new int[vec.size()];
92          for (int i = 0, j = 0; i < prevmodel.length; i++) {
93              if (prevmodel[i] < 0) {
94                  newmodel[j++] = prevmodel[i];
95              }
96          }
97  
98          return newmodel;
99      }
100 }