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 number (with respect to cardinality) of
41 * negative literals. This is done be adding a constraint on the number of
42 * negative literals each time a model if found (the number of negative literals
43 * occuring in the model minus one).
44 *
45 * @author leberre
46 * @see org.sat4j.specs.ISolver#addAtMost(IVecInt, int)
47 */
48 public class Minimal4CardinalityModel extends AbstractMinimalModel {
49
50 private static final long serialVersionUID = 1L;
51
52 private int[] prevfullmodel;
53
54 /**
55 * @param solver
56 */
57 public Minimal4CardinalityModel(ISolver solver) {
58 super(solver);
59 }
60
61 public Minimal4CardinalityModel(ISolver solver, IVecInt p,
62 SolutionFoundListener modelListener) {
63 super(solver, p, modelListener);
64 }
65
66 public Minimal4CardinalityModel(ISolver solver, IVecInt p) {
67 super(solver, p);
68 }
69
70 public Minimal4CardinalityModel(ISolver solver,
71 SolutionFoundListener modelListener) {
72 super(solver, modelListener);
73 }
74
75 /*
76 * (non-Javadoc)
77 *
78 * @see org.sat4j.ISolver#model()
79 */
80 @Override
81 public int[] model() {
82 int[] prevmodel = null;
83 IConstr lastOne = null;
84 IVecInt literals = new VecInt(pLiterals.size());
85 for (int p : pLiterals) {
86 literals.push(p);
87 }
88 try {
89 do {
90 prevfullmodel = super.modelWithInternalVariables();
91 prevmodel = super.model();
92 int counter = 0;
93 for (int q : prevfullmodel) {
94 if (pLiterals.contains(q)) {
95 counter++;
96 }
97 }
98 lastOne = addAtMost(literals, counter - 1);
99 } while (isSatisfiable());
100 } catch (TimeoutException e) {
101 throw new IllegalStateException("Solver timed out"); //$NON-NLS-1$
102 } catch (ContradictionException e) {
103 // added trivial unsat clauses
104 }
105 if (lastOne != null) {
106 removeConstr(lastOne);
107 }
108 return prevmodel;
109 }
110
111 @Override
112 public int[] modelWithInternalVariables() {
113 model();
114 return prevfullmodel;
115 }
116 }