26#include "absl/log/check.h"
27#include "absl/log/log.h"
28#include "absl/strings/numbers.h"
29#include "absl/strings/str_cat.h"
30#include "absl/strings/str_format.h"
31#include "absl/strings/str_split.h"
32#include "absl/strings/string_view.h"
52 size_t SkipBlanks(
size_t pos)
const;
53 size_t SkipNonBlanks(
size_t pos)
const;
55 absl::string_view line_;
68size_t SetCoverReader::SkipBlanks(
size_t pos)
const {
69 const size_t size = line_.size();
72 for (; pos < size && line_[pos] ==
' '; ++pos) {
75 for (; pos < size && std::isspace(line_[pos]); ++pos) {
80size_t SetCoverReader::SkipNonBlanks(
size_t pos)
const {
81 const size_t size = line_.size();
82 for (; pos < size && !std::isspace(line_[pos]); ++pos) {
88 const size_t size = line_.size();
89 start_pos_ = SkipBlanks(end_pos_);
90 if (start_pos_ >= size) {
93 start_pos_ = SkipBlanks(0);
95 end_pos_ = SkipNonBlanks(start_pos_);
96 return line_.substr(start_pos_, end_pos_ - start_pos_);
112double Percent(SubsetIndex subset,
BaseInt total) {
113 return subset.value() == 0 ? 0 : 100.0 * subset.value() / total;
116double Percent(ElementIndex element,
BaseInt total) {
117 return element.value() == 0 ? 0 : 100.0 * element.value() / total;
135 LOG_EVERY_N_SEC(INFO, 5)
136 << absl::StrFormat(
"Reading element %d (%.1f%%)", element.value(),
139 for (RowEntryIndex entry(0); entry < row_size; ++entry) {
145 LOG(INFO) <<
"Read " << model.
num_subsets() <<
" subsets, "
162 LOG_EVERY_N_SEC(INFO, 5)
163 << absl::StrFormat(
"Reading subset %d (%.1f%%)", subset.value(),
175 LOG(INFO) <<
"Read " << model.
num_subsets() <<
" subsets, "
185 SubsetIndex subset(0);
187 BaseInt smallest_element = std::numeric_limits<BaseInt>::max();
189 for (
const std::string& line :
FileLines(filename)) {
190 std::vector<std::string> elements = absl::StrSplit(line,
' ');
191 if (elements.back().empty() || elements.back()[0] ==
'\0') {
194 for (
const std::string& number_str : elements) {
196 CHECK(absl::SimpleAtoi(number_str, &element));
197 smallest_element = std::min(smallest_element, element);
198 largest_element = std::max(largest_element, element);
201 DLOG(INFO) <<
"Smallest element: " << smallest_element
202 <<
", Largest element: " << largest_element;
204 for (
const std::string& line :
FileLines(filename)) {
205 LOG_EVERY_N_SEC(INFO, 5)
206 << absl::StrFormat(
"Reading subset %d", subset.value());
207 std::vector<std::string> elements = absl::StrSplit(line,
' ');
208 if (elements.back().empty() || elements.back()[0] ==
'\0') {
214 std::vector<ElementIndex> elements_list;
215 for (
const std::string& number_str : elements) {
217 CHECK(absl::SimpleAtoi(number_str, &raw_element));
219 ElementIndex element(raw_element - smallest_element);
220 if (element_seen[element]) {
221 DLOG(INFO) <<
"Element " << element <<
" already in subset "
225 element_seen[element] =
true;
226 elements_list.push_back(element);
227 CHECK_GE(element.value(), 0);
231 for (
const ElementIndex element : elements_list) {
232 element_seen[element] =
false;
236 LOG(INFO) <<
"Read " << model.
num_subsets() <<
" subsets, "
264 : LineFormatter(
file,
std::numeric_limits<int64_t>::max()) {}
265 LineFormatter(File* file, int64_t max_cols)
266 : num_cols_(0), max_cols_(max_cols), line_(), file_(file) {}
267 ~LineFormatter() { CHECK(line_.empty()); }
269 void Append(absl::string_view text) {
270 const int text_size = text.size();
271 if (!text.empty() && text_size + num_cols_ > max_cols_) {
274 absl::StrAppend(&line_, text);
275 num_cols_ += text_size;
278 void Append(
BaseInt value) { Append(absl::StrCat(value,
" ")); }
280 void Append(
double value) { Append(absl::StrFormat(
"%.17g ", value)); }
299 LineFormatter formatter(
file);
302 formatter.FlushLine();
303 for (
const SubsetIndex subset : model.
SubsetRange()) {
306 formatter.FlushLine();
307 for (
const ElementIndex element : model.
ElementRange()) {
308 LOG_EVERY_N_SEC(INFO, 5)
309 << absl::StrFormat(
"Writing element %d (%.1f%%)", element.value(),
311 formatter.Append(absl::StrCat(model.
rows()[element].size(),
"\n"));
312 for (
const SubsetIndex subset : model.
rows()[element]) {
313 formatter.Append(subset.value() + 1);
315 formatter.FlushLine();
317 LOG(INFO) <<
"Finished writing the model.";
327 LineFormatter formatter(
file);
328 for (
const SubsetIndex subset : model.
SubsetRange()) {
329 LOG_EVERY_N_SEC(INFO, 5)
330 << absl::StrFormat(
"Writing subset %d (%.1f%%)", subset.value(),
333 formatter.Append(
static_cast<BaseInt>(model.
columns()[subset].size()));
334 for (
const ElementIndex element : model.
columns()[subset]) {
335 formatter.Append(element.value() + 1);
337 formatter.FlushLine();
339 LOG(INFO) <<
"Finished writing the model.";
361 for (
int i = 0; i < cardinality; ++i) {
383 solution[SubsetIndex(subset)] =
true;
390 absl::string_view filename) {
394 for (SubsetIndex subset(0); subset.value() <
solution.size(); ++subset) {
401 file, absl::StrCat(
solution.size(),
" ", cardinality,
" ", cost,
"\n"),
403 LineFormatter formatter(
file);
405 if (
solution[SubsetIndex(subset)]) {
406 formatter.Append(subset);
409 formatter.FlushLine();
415 absl::string_view filename,
bool binary) {
419 for (SubsetIndex subset(0); subset.value() <
solution.size(); ++subset) {
Implements the minimum interface for a range-based for loop iterator.
Main class for describing a weighted set-covering problem.
void ImportModelFromProto(const SetCoverProto &message)
Imports the model from a SetCoverProto.
void ResizeNumSubsets(BaseInt num_subsets)
void ReserveNumElementsInSubset(BaseInt num_elements, BaseInt subset)
Reserves num_elements rows in the column indexed by subset.
util_intops::StrongIntRange< ElementIndex > ElementRange() const
void AddElementToLastSubset(BaseInt element)
void AddEmptySubset(Cost cost)
const SparseRowView & rows() const
Row view of the set covering problem.
BaseInt num_elements() const
util_intops::StrongIntRange< SubsetIndex > SubsetRange() const
Access to the ranges of subsets and elements.
void AddElementToSubset(BaseInt element, BaseInt subset)
void SetSubsetCost(BaseInt subset, Cost cost)
const SubsetCostVector & subset_costs() const
Vector of costs for each subset.
void CreateSparseRowView()
SetCoverProto ExportModelAsProto() const
const SparseColumnView & columns() const
Column view of the set covering problem.
BaseInt num_subsets() const
int64_t ParseNextInteger()
absl::string_view GetNextToken()
SetCoverReader(File *file)
::int64_t num_subsets() const
void add_subset(::int64_t value)
void set_num_subsets(::int64_t value)
void set_cost(double value)
::int64_t subset(int index) const
absl::Status Exists(absl::string_view path, Options options)
absl::Status SetBinaryProto(absl::string_view file_name, const google::protobuf::Message &proto, Options options)
absl::Status SetTextProto(absl::string_view file_name, const google::protobuf::Message &proto, Options options)
absl::Status GetTextProto(absl::string_view file_name, google::protobuf::Message *proto, Options options)
-— Protobuf API -—
File * OpenOrDie(absl::string_view file_name, absl::string_view mode, Options options)
absl::Status WriteString(File *file, absl::string_view contents, Options options)
absl::Status GetBinaryProto(const absl::string_view file_name, google::protobuf::Message *proto, Options options)
In SWIG mode, we don't want anything besides these top-level includes.
SetCoverModel ReadOrlibScp(absl::string_view filename)
This is a row-based format where the elements are 1-indexed.
void WriteSetCoverProto(const SetCoverModel &model, absl::string_view filename, bool binary)
SetCoverModel ReadSetCoverProto(absl::string_view filename, bool binary)
void WriteSetCoverSolutionProto(const SetCoverModel &model, const SubsetBoolVector &solution, absl::string_view filename, bool binary)
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
util_intops::StrongIntRange< SubsetIndex > SubsetRange
SubsetBoolVector ReadSetCoverSolutionText(absl::string_view filename)
util_intops::StrongIntRange< ColumnEntryIndex > ColumnEntryRange
void WriteSetCoverSolutionText(const SetCoverModel &model, const SubsetBoolVector &solution, absl::string_view filename)
SetCoverModel ReadOrlibRail(absl::string_view filename)
This is a column-based format where the elements are 1-indexed.
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
util_intops::StrongVector< ElementIndex, bool > ElementBoolVector
void WriteOrlibScp(const SetCoverModel &model, absl::string_view filename)
void WriteOrlibRail(const SetCoverModel &model, absl::string_view filename)
Beware the fact that elements written are converted to 1-indexed.
SubsetBoolVector ReadSetCoverSolutionProto(absl::string_view filename, bool binary)
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
util_intops::StrongIntRange< ElementIndex > ElementRange
SetCoverModel ReadFimiDat(absl::string_view filename)