View Javadoc

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.reader;
31  
32  import java.io.IOException;
33  import java.io.PrintWriter;
34  
35  import org.sat4j.core.VecInt;
36  import org.sat4j.specs.ContradictionException;
37  import org.sat4j.specs.IProblem;
38  import org.sat4j.specs.ISolver;
39  import org.sat4j.specs.IVecInt;
40  import org.sat4j.tools.GateTranslator;
41  
42  /**
43   * Reader for the ASCII And Inverter Graph format defined by Armin Biere.
44   * 
45   * @author daniel
46   * 
47   */
48  public class AAGReader extends Reader {
49  
50      private final static int FALSE = 0;
51  
52      private final static int TRUE = 1;
53  
54      private final GateTranslator solver;
55  
56      private int maxvarid;
57  
58      private int nbinputs;
59  
60      AAGReader(ISolver s) {
61          this.solver = new GateTranslator(s);
62      }
63  
64      @Override
65      public String decode(int[] model) {
66          StringBuffer stb = new StringBuffer();
67          for (int i = 0; i < this.nbinputs; i++) {
68              stb.append(model[i] > 0 ? 1 : 0);
69          }
70          return stb.toString();
71      }
72  
73      @Override
74      public void decode(int[] model, PrintWriter out) {
75          for (int i = 0; i < this.nbinputs; i++) {
76              out.print(model[i] > 0 ? 1 : 0);
77          }
78      }
79  
80      @Override
81      public IProblem parseInstance(java.io.InputStream in)
82              throws ParseFormatException, ContradictionException, IOException {
83          EfficientScanner scanner = new EfficientScanner(in);
84          String prefix = scanner.next();
85          if (!"aag".equals(prefix)) {
86              throw new ParseFormatException("AAG format only!");
87          }
88          this.maxvarid = scanner.nextInt();
89          this.nbinputs = scanner.nextInt();
90          int nblatches = scanner.nextInt();
91          int nboutputs = scanner.nextInt();
92          if (nboutputs > 1) {
93              throw new ParseFormatException(
94                      "CNF conversion allowed for single output circuit only!");
95          }
96          int nbands = scanner.nextInt();
97          this.solver.newVar(this.maxvarid + 1);
98          this.solver.setExpectedNumberOfClauses(3 * nbands + 2);
99          readInput(this.nbinputs, scanner);
100         assert nblatches == 0;
101         if (nboutputs > 0) {
102             int output0 = readOutput(nboutputs, scanner);
103             readAnd(nbands, output0, scanner);
104         }
105         return this.solver;
106     }
107 
108     private void readAnd(int nbands, int output0, EfficientScanner scanner)
109             throws ContradictionException, IOException, ParseFormatException {
110 
111         for (int i = 0; i < nbands; i++) {
112             int lhs = scanner.nextInt();
113             int rhs0 = scanner.nextInt();
114             int rhs1 = scanner.nextInt();
115             this.solver.and(toDimacs(lhs), toDimacs(rhs0), toDimacs(rhs1));
116         }
117         this.solver.gateTrue(this.maxvarid + 1);
118         this.solver.gateTrue(toDimacs(output0));
119     }
120 
121     private int toDimacs(int v) {
122         if (v == FALSE) {
123             return -(this.maxvarid + 1);
124         }
125         if (v == TRUE) {
126             return this.maxvarid + 1;
127         }
128         int var = v >> 1;
129         if ((v & 1) == 0) {
130             return var;
131         }
132         return -var;
133     }
134 
135     private int readOutput(int nboutputs, EfficientScanner scanner)
136             throws IOException, ParseFormatException {
137         IVecInt outputs = new VecInt(nboutputs);
138         for (int i = 0; i < nboutputs; i++) {
139             outputs.push(scanner.nextInt());
140         }
141         return outputs.get(0);
142     }
143 
144     private IVecInt readInput(int numberOfInputs, EfficientScanner scanner)
145             throws IOException, ParseFormatException {
146         IVecInt inputs = new VecInt(numberOfInputs);
147         for (int i = 0; i < numberOfInputs; i++) {
148             inputs.push(scanner.nextInt());
149         }
150         return inputs;
151     }
152 }