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