OKlibrary  0.2.1.6
BoundedTransversals_bv.cpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 6.6.2009 (Swansea)
00002 /* Copyright 2009, 2010 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00033 #include <string>
00034 #include <set>
00035 #include <functional>
00036 #include <iostream>
00037 
00038 #include <boost/lexical_cast.hpp>
00039 
00040 #include <OKlib/Programming/Utilities/OrderRelations/OrderConstructions.hpp>
00041 #include <OKlib/Satisfiability/Interfaces/InputOutput/ClauseSetAdaptors.hpp>
00042 #include <OKlib/Satisfiability/Interfaces/InputOutput/Dimacs.hpp>
00043 #include <OKlib/Combinatorics/Hypergraphs/Transversals/Bounded/VertexBranching.hpp>
00044 
00045 namespace {
00046 
00047   enum {
00048     error_parameters = 1,
00049     error_empty = 2,
00050     error_symbol1 = 3,
00051     error_symbol2 = 4,
00052     error_empty_hyperedge = 5
00053   };
00054 
00055   const std::string version = "0.0.5";
00056 
00057 }
00058 
00059 int main(const int argc, const char* const argv[]) {
00060 
00061   if (argc > 2) {
00062     std::cerr << "ERROR[BoundedTransversals_bv]:\n"
00063       " Either zero or one parameter is required, which is of the form\n"
00064       " \"=n\" or \">=n\" for some natural number n >= 0.\n"
00065       " However, the actual number of input parameters was " << argc-1 << ".\n";
00066     return error_parameters;
00067   }
00068 
00069   typedef unsigned int vertex_type; // currently ignored
00070   typedef int literal_type; // necessary since (currently) we are using clause-set input- and output-facilities
00071   typedef std::set<literal_type> hyperedge_type;
00072   typedef hyperedge_type::size_type size_type;
00073 
00074   bool iterated_; size_type B_;
00075   if (argc == 1) { iterated_ = true; B_ = 0; }
00076   else {
00077     const std::string par(argv[1]);
00078     if (par.empty()) {
00079       std::cerr << "ERROR[BoundedTransversals_bv]:\n"
00080         "The parameter is the empty string.\n";
00081       return error_empty;
00082     }
00083     if (par[0] == '=') {
00084       iterated_ = false;
00085       B_ = boost::lexical_cast<size_type>(par.substr(1));
00086     }
00087     else {
00088       if (par[0] != '>') {
00089         std::cerr << "ERROR[BoundedTransversals_bv]:\n"
00090           "Unrecognised leading symbol " << par[0] << ".\n";
00091         return error_symbol1;
00092       }
00093       if (par.size() == 1 or par[1] != '=') {
00094         std::cerr << "ERROR[BoundedTransversals_bv]:\n"
00095           "After \">\" the symbol \"=\" is expected.\n";
00096         return error_symbol2;
00097       }
00098       iterated_ = true;
00099       B_ = boost::lexical_cast<size_type>(par.substr(2));
00100     }
00101   }
00102   const bool iterated(iterated_); const size_type B(B_);
00103 
00104   typedef OKlib::Programming::Utilities::OrderRelations::SizeLessThan<std::less<hyperedge_type> > hyperedge_ordering_type;
00105   typedef std::set<hyperedge_type, hyperedge_ordering_type> set_system_type;
00106   typedef OKlib::InputOutput::RawDimacsCLSAdaptorSets<literal_type, set_system_type> dimacs_adaptor_type;
00107   typedef OKlib::InputOutput::StandardDIMACSInput<dimacs_adaptor_type> dimacs_input_type;
00108   
00109   dimacs_adaptor_type in;
00110   dimacs_input_type(std::cin, in);
00111   
00112   typedef OKlib::Combinatorics::Hypergraphs::Transversals::Bounded::Bounded_transversals_bv<set_system_type> transversal_enumerator_type;
00113   typedef transversal_enumerator_type::transversal_list_type transversal_list_type;
00114   
00115   transversal_enumerator_type t_e(in.clause_set, B);
00116   if (iterated and not t_e.G_orig.empty() and t_e.G_orig.begin() -> empty()) {
00117     std::cerr << "ERROR[BoundedTransversals_bv]:\n"
00118       "The iteration would not terminate due to the presence of the empty hyperedge.\n";
00119     return error_empty_hyperedge;
00120   }
00121   const transversal_list_type transversals(iterated ? t_e.iterated() : t_e());
00122   
00123   typedef OKlib::InputOutput::CLSAdaptorDIMACSOutput<> dimacs_adaptor2_type;
00124   typedef OKlib::InputOutput::ListTransfer<dimacs_adaptor2_type> dimacs_output_type;
00125   dimacs_adaptor2_type out(std::cout);
00126   dimacs_output_type(transversals, out, "Bounded transversals of size " + boost::lexical_cast<std::string>(t_e.bound));
00127 
00128 }
00129