OR-Tools  8.2
set_covering_parser.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include "absl/strings/numbers.h"
17#include "absl/strings/str_split.h"
19
20namespace operations_research {
21namespace scp {
22
23ScpParser::ScpParser() : section_(INIT), line_(0), remaining_(0), current_(0) {}
24
25bool ScpParser::LoadProblem(const std::string& filename, Format format,
26 ScpData* data) {
27 section_ = INIT;
28 line_ = 0;
29 remaining_ = 0;
30 current_ = 0;
31
32 for (const std::string& line : FileLines(filename)) {
33 ProcessLine(line, format, data);
34 if (section_ == ERROR) return false;
35 }
36 return section_ == END;
37}
38
39void ScpParser::ProcessLine(const std::string& line, Format format,
40 ScpData* data) {
41 line_++;
42 const std::vector<std::string> words =
43 absl::StrSplit(line, absl::ByAnyChar(" :\t\r"), absl::SkipEmpty());
44 switch (section_) {
45 case INIT: {
46 if (words.size() != 2) {
47 LogError(line, "Problem reading the size of the problem");
48 return;
49 }
50 const int num_rows = strtoint32(words[0]);
51 const int num_columns = strtoint32(words[1]);
52 data->SetProblemSize(num_rows, num_columns);
53 current_ = 0;
54 switch (format) {
55 case SCP_FORMAT: {
56 section_ = COSTS;
57 break;
58 }
59 case RAILROAD_FORMAT: {
60 section_ = COLUMN;
61 break;
62 }
63 case TRIPLET_FORMAT: {
64 section_ = COLUMN;
65 break;
66 }
67 case SPP_FORMAT: {
68 section_ = COLUMN;
69 data->set_is_set_partitioning(true);
70 break;
71 }
72 }
73 break;
74 }
75 case COSTS: {
76 const int num_items = words.size();
77 if (current_ + num_items > data->num_columns()) {
78 LogError(line, "Too many cost items");
79 return;
80 }
81 for (int i = 0; i < num_items; ++i) {
82 data->SetColumnCost(current_++, strtoint32(words[i]));
83 }
84 if (current_ == data->num_columns()) {
85 section_ = NUM_COLUMNS_IN_ROW;
86 current_ = 0;
87 }
88 break;
89 }
90 case COLUMN: {
91 switch (format) {
92 case SCP_FORMAT: {
93 LogError(line, "Wrong state in the loader");
94 return;
95 }
96 case RAILROAD_FORMAT:
97 ABSL_FALLTHROUGH_INTENDED;
98 case SPP_FORMAT: {
99 if (words.size() < 2) {
100 LogError(line, "Column declaration too short");
101 return;
102 }
103 const int cost = strtoint32(words[0]);
104 data->SetColumnCost(current_, cost);
105 const int num_items = strtoint32(words[1]);
106 if (words.size() != 2 + num_items) {
107 LogError(line, "Mistatch in column declaration");
108 return;
109 }
110 for (int i = 0; i < num_items; ++i) {
111 const int row = strtoint32(words[i + 2]) - 1; // 1 based.
112 data->AddRowInColumn(row, current_);
113 }
114 current_++;
115 if (current_ == data->num_columns()) {
116 section_ = format == RAILROAD_FORMAT ? END : NUM_NON_ZEROS;
117 }
118 break;
119 }
120 case TRIPLET_FORMAT: {
121 if (words.size() != 3) {
122 LogError(line, "Column declaration does not contain 3 rows");
123 break;
124 }
125 data->SetColumnCost(current_, 1);
126 for (int i = 0; i < 3; ++i) {
127 const int row = strtoint32(words[i]) - 1; // 1 based.
128 data->AddRowInColumn(row, current_);
129 }
130 current_++;
131 if (current_ == data->num_columns()) {
132 section_ = END;
133 }
134 break;
135 }
136 }
137 break;
138 }
139 case NUM_COLUMNS_IN_ROW: {
140 if (words.size() != 1) {
141 LogError(line, "The header of a column should be one number");
142 return;
143 }
144 remaining_ = strtoint32(words[0]);
145 section_ = ROW;
146 break;
147 }
148 case ROW: {
149 const int num_items = words.size();
150 if (num_items > remaining_) {
151 LogError(line, "Too many columns in a row declaration");
152 return;
153 }
154 for (const std::string& w : words) {
155 remaining_--;
156 const int column = strtoint32(w) - 1; // 1 based.
157 data->AddRowInColumn(current_, column);
158 }
159 if (remaining_ == 0) {
160 current_++;
161 if (current_ == data->num_rows()) {
162 section_ = END;
163 } else {
164 section_ = NUM_COLUMNS_IN_ROW;
165 }
166 }
167 break;
168 }
169 case NUM_NON_ZEROS: {
170 if (words.size() != 1) {
171 LogError(line, "The header of a column should be one number");
172 return;
173 }
174 section_ = END;
175 break;
176 }
177 case END: {
178 break;
179 }
180 case ERROR: {
181 break;
182 }
183 }
184}
185
186void ScpParser::LogError(const std::string& line, const std::string& message) {
187 LOG(ERROR) << "Error on line " << line_ << ": " << message << "(" << line
188 << ")";
189 section_ = ERROR;
190}
191
192int ScpParser::strtoint32(const std::string& word) {
193 int result;
194 CHECK(absl::SimpleAtoi(word, &result));
195 return result;
196}
197
198int64 ScpParser::strtoint64(const std::string& word) {
199 int64 result;
200 CHECK(absl::SimpleAtoi(word, &result));
201 return result;
202}
203
204} // namespace scp
205} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define LOG(severity)
Definition: base/logging.h:420
void SetProblemSize(int num_rows, int num_columns)
void SetColumnCost(int column_id, int cost)
void AddRowInColumn(int row, int column)
bool LoadProblem(const std::string &filename, Format format, ScpData *data)
int64_t int64
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 cost
int64 current_
Definition: search.cc:2953
std::string message
Definition: trace.cc:395