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 
20 namespace operations_research {
21 namespace scp {
22 
23 ScpParser::ScpParser() : section_(INIT), line_(0), remaining_(0), current_(0) {}
24 
25 bool 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 
39 void 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 
186 void 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 
192 int ScpParser::strtoint32(const std::string& word) {
193  int result;
194  CHECK(absl::SimpleAtoi(word, &result));
195  return result;
196 }
197 
198 int64 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