src/proof/dimacs.cpp

   1 /*********************                                                        */
   2 /*! \file dimacs.cpp
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Alex Ozdemir
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2020 by the authors listed in the file AUTHORS
   8  ** in the top-level source directory) and their institutional affiliations.
   9  ** All rights reserved.  See the file COPYING in the top-level source
  10  ** directory for licensing information.\endverbatim
  11  **
  12  ** \brief DIMACS SAT Problem Format
  13  **
  14  ** Defines serialization for SAT problems as DIMACS
  15  **/
  16
  17 #include "proof/dimacs.h"
  18
  19 #include "base/check.h"
  20
  21 #include <iostream>
  22
  23 namespace CVC4 {
  24 namespace proof {
  25
  26 // Prints the literal as a (+) or (-) int
  27 // Not operator<< b/c that represents negation as ~
  28 std::ostream& textOut(std::ostream& o, const prop::SatLiteral& l)
  29 {
  30   if (l.isNegated())
  31   {
  32     o << "-";
  33   }
  34   return o << l.getSatVariable() + 1;
  35 }
  36
  37 // Prints the clause as a space-separated list of ints
  38 // Not operator<< b/c that represents negation as ~
  39 std::ostream& textOut(std::ostream& o, const prop::SatClause& c)
  40 {
  41   for (const auto& l : c)
  42   {
  43     textOut(o, l) << " ";
  44   }
  45   return o << "0";
  46 }
  47
  48 void printDimacs(std::ostream& o,
  49                  const std::unordered_map<ClauseId, prop::SatClause>& clauses,
  50                  const std::vector<ClauseId>& usedIndices)
  51 {
  52   size_t maxVar = 0;
  53   for (const ClauseId i : usedIndices)
  54   {
  55     const prop::SatClause& c = clauses.at(i);
  56     for (const auto& l : c)
  57     {
  58       if (l.getSatVariable() + 1 > maxVar)
  59       {
  60         maxVar = l.getSatVariable() + 1;
  61       }
  62     }
  63   }
  64   o << "p cnf " << maxVar << " " << usedIndices.size() << '\n';
  65   for (const ClauseId i : usedIndices)
  66   {
  67     const prop::SatClause& c = clauses.at(i);
  68     for (const auto& l : c)
  69     {
  70       if (l.isNegated())
  71       {
  72         o << '-';
  73       }
  74       o << l.getSatVariable() + 1 << " ";
  75     }
  76     o << "0\n";
  77   }
  78 }
  79
  80 std::vector<prop::SatClause> parseDimacs(std::istream& in)
  81 {
  82   std::string tag;
  83   uint64_t nVars;
  84   uint64_t nClauses;
  85
  86   in >> tag;
  87   Assert(in.good());
  88   Assert(tag == "p");
  89
  90   in >> tag;
  91   Assert(in.good());
  92   Assert(tag == "cnf");
  93
  94   in >> nVars;
  95   Assert(nVars >= 0);
  96
  97   in >> nClauses;
  98   Assert(nClauses >= 0);
  99
 100   std::vector<prop::SatClause> cnf;
 101   for (uint64_t i = 0; i < nClauses; ++i)
 102   {
 103     cnf.emplace_back();
 104     int64_t lit;
 105     in >> lit;
 106     Assert(in.good());
 107     while (lit != 0)
 108     {
 109       cnf.back().emplace_back(std::abs(lit) - 1, lit < 0);
 110       in >> lit;
 111       Assert(static_cast<uint64_t>(std::abs(lit)) <= nVars);
 112       Assert(in.good());
 113     }
 114   }
 115
 116   return cnf;
 117 }
 118
 119 }  // namespace proof
 120 }  // namespace CVC4