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