1 /*******************************************************************************
2 * SAT4J: a SATisfiability library for Java Copyright (C) 2004, 2012 Artois University and CNRS
3 *
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *
9 * Alternatively, the contents of this file may be used under the terms of
10 * either the GNU Lesser General Public License Version 2.1 or later (the
11 * "LGPL"), in which case the provisions of the LGPL are applicable instead
12 * of those above. If you wish to allow use of your version of this file only
13 * under the terms of the LGPL, and not to allow others to use your version of
14 * this file under the terms of the EPL, indicate your decision by deleting
15 * the provisions above and replace them with the notice and other provisions
16 * required by the LGPL. If you do not delete the provisions above, a recipient
17 * may use your version of this file under the terms of the EPL or the LGPL.
18 *
19 * Based on the original MiniSat specification from:
20 *
21 * An extensible SAT solver. Niklas Een and Niklas Sorensson. Proceedings of the
22 * Sixth International Conference on Theory and Applications of Satisfiability
23 * Testing, LNCS 2919, pp 502-518, 2003.
24 *
25 * See www.minisat.se for the original solver in C++.
26 *
27 * Contributors:
28 * CRIL - initial API and implementation
29 *******************************************************************************/
30 package org.sat4j.tools;
31
32 import org.sat4j.core.VecInt;
33 import org.sat4j.specs.ContradictionException;
34 import org.sat4j.specs.IConstr;
35 import org.sat4j.specs.ISolver;
36 import org.sat4j.specs.IVecInt;
37 import org.sat4j.specs.TimeoutException;
38
39 /**
40 * Computes models with a minimal subset (with respect to set inclusion) of
41 * negative literals. This is done be adding a clause containing the negation of
42 * the negative literals appearing in the model found (which prevents any
43 * interpretation containing that subset of negative literals to be a model of
44 * the formula).
45 *
46 * Computes only one model minimal for inclusion, since there is currently no
47 * way to save the state of the solver.
48 *
49 * @author leberre
50 *
51 * @see org.sat4j.specs.ISolver#addClause(IVecInt)
52 */
53 public class Minimal4InclusionModel extends AbstractMinimalModel {
54
55 private static final long serialVersionUID = 1L;
56
57 private int[] prevfullmodel;
58
59 /**
60 *
61 * @param solver
62 * @param p
63 * the set of literals on which the minimality for inclusion is
64 * computed.
65 * @param modelListener
66 * an object to be notified when a new model is found.
67 */
68 public Minimal4InclusionModel(ISolver solver, IVecInt p,
69 SolutionFoundListener modelListener) {
70 super(solver, p, modelListener);
71 }
72
73 /**
74 *
75 * @param solver
76 * @param p
77 * the set of literals on which the minimality for inclusion is
78 * computed.
79 */
80 public Minimal4InclusionModel(ISolver solver, IVecInt p) {
81 this(solver, p, SolutionFoundListener.VOID);
82 }
83
84 /**
85 * @param solver
86 */
87 public Minimal4InclusionModel(ISolver solver) {
88 this(solver, negativeLiterals(solver), SolutionFoundListener.VOID);
89 }
90
91 /*
92 * (non-Javadoc)
93 *
94 * @see org.sat4j.ISolver#model()
95 */
96 @Override
97 public int[] model() {
98 int[] prevmodel = null;
99 IVecInt vec = new VecInt();
100 IVecInt cube = new VecInt();
101 IConstr prevConstr = null;
102 try {
103 do {
104 prevfullmodel = super.modelWithInternalVariables();
105 prevmodel = super.model();
106 modelListener.onSolutionFound(prevmodel);
107 vec.clear();
108 cube.clear();
109 for (int q : prevfullmodel) {
110 if (pLiterals.contains(q)) {
111 vec.push(-q);
112 } else if (pLiterals.contains(-q)) {
113 cube.push(q);
114 }
115 }
116 if (prevConstr != null) {
117 removeSubsumedConstr(prevConstr);
118 }
119 prevConstr = addBlockingClause(vec);
120 } while (isSatisfiable(cube));
121 } catch (TimeoutException e) {
122 throw new IllegalStateException("Solver timed out");
123 } catch (ContradictionException e) {
124 // added trivial unsat clauses
125 }
126
127 return prevmodel;
128
129 }
130
131 @Override
132 public int[] modelWithInternalVariables() {
133 model();
134 return prevfullmodel;
135 }
136 }