OR-Tools  8.2
rcpsp_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/match.h"
17#include "absl/strings/numbers.h"
18#include "absl/strings/str_split.h"
20#include "ortools/data/rcpsp.pb.h"
21
22namespace operations_research {
23namespace data {
24namespace rcpsp {
25
27 : seed_(-1),
28 load_status_(NOT_STARTED),
29 num_declared_tasks_(-1),
30 current_task_(-1),
31 unreads_(0) {
32 rcpsp_.set_deadline(-1);
33 rcpsp_.set_horizon(-1);
34}
35
36bool RcpspParser::ParseFile(const std::string& file_name) {
37 if (load_status_ != NOT_STARTED) {
38 return false;
39 }
40
41 const bool is_rcpsp_max =
42 absl::EndsWith(file_name, ".sch") || absl::EndsWith(file_name, ".SCH");
43 const bool is_patterson = absl::EndsWith(file_name, ".rcp");
44 load_status_ = HEADER_SECTION;
45
46 for (const std::string& line : FileLines(file_name)) {
47 if (is_rcpsp_max) {
48 ProcessRcpspMaxLine(line);
49 } else if (is_patterson) {
50 ProcessPattersonLine(line);
51 } else {
52 ProcessRcpspLine(line);
53 }
54 if (load_status_ == ERROR_FOUND) {
55 LOG(INFO) << rcpsp_.DebugString();
56 return false;
57 }
58 }
59 VLOG(1) << "Read file: " << file_name << ", max = " << is_rcpsp_max
60 << ", patterson = " << is_patterson << ", with "
61 << rcpsp_.tasks_size() << " tasks, and " << rcpsp_.resources_size()
62 << " resources.";
63 // Count the extra start and end tasks.
64 return num_declared_tasks_ + 2 == rcpsp_.tasks_size() &&
65 load_status_ == PARSING_FINISHED;
66}
67
68void RcpspParser::ReportError(const std::string& line) {
69 LOG(ERROR) << "Error: status = " << load_status_ << ", line = " << line;
70 load_status_ = ERROR_FOUND;
71}
72
73void RcpspParser::SetNumDeclaredTasks(int t) {
74 num_declared_tasks_ = t;
75 recipe_sizes_.resize(t + 2, 0); // The data format adds 2 sentinels.
76}
77
78void RcpspParser::ProcessRcpspLine(const std::string& line) {
79 if (absl::StartsWith(line, "***")) return;
80 if (absl::StartsWith(line, "---")) return;
81
82 const std::vector<std::string> words =
83 absl::StrSplit(line, absl::ByAnyChar(" :\t\r"), absl::SkipEmpty());
84
85 if (words.empty()) return;
86
87 switch (load_status_) {
88 case NOT_STARTED: {
89 ReportError(line);
90 break;
91 }
92 case HEADER_SECTION: {
93 if (words[0] == "file") {
94 rcpsp_.set_basedata(words[3]);
95 } else if (words[0] == "initial") {
96 rcpsp_.set_seed(strtoint64(words[4]));
97 load_status_ = PROJECT_SECTION;
98 } else if (words[0] == "jobs") {
99 // Workaround for the mmlib files which has less headers.
100 SetNumDeclaredTasks(strtoint32(words[4]) - 2);
101 load_status_ = PROJECT_SECTION;
102 } else {
103 ReportError(line);
104 }
105 break;
106 }
107 case PROJECT_SECTION: {
108 if (words[0] == "projects") {
109 // Nothing to do.
110 } else if (words[0] == "jobs") {
111 // This declaration counts the 2 sentinels.
112 SetNumDeclaredTasks(strtoint32(words[4]) - 2);
113 } else if (words[0] == "horizon") {
114 rcpsp_.set_horizon(strtoint32(words[1]));
115 } else if (words[0] == "RESOURCES") {
116 // Nothing to do.
117 } else if (words.size() > 1 && words[1] == "renewable") {
118 for (int i = 0; i < strtoint32(words[2]); ++i) {
119 Resource* const res = rcpsp_.add_resources();
120 res->set_max_capacity(-1);
121 res->set_renewable(true);
122 res->set_unit_cost(0);
123 }
124 } else if (words.size() > 1 && words[1] == "nonrenewable") {
125 for (int i = 0; i < strtoint32(words[2]); ++i) {
126 Resource* const res = rcpsp_.add_resources();
127 res->set_max_capacity(-1);
128 res->set_min_capacity(-1);
129 res->set_renewable(false);
130 res->set_unit_cost(0);
131 }
132 } else if (words.size() > 1 && words[1] == "doubly") {
133 // Nothing to do.
134 } else if (words.size() == 2 && words[0] == "PROJECT") {
135 load_status_ = INFO_SECTION;
136 } else if (words.size() == 2 && words[0] == "PRECEDENCE") {
137 // mmlib files have no info section.
138 load_status_ = PRECEDENCE_SECTION;
139 } else {
140 ReportError(line);
141 }
142 break;
143 }
144 case INFO_SECTION: {
145 if (words[0] == "pronr.") {
146 // Nothing to do.
147 } else if (words.size() == 6) {
148 SetNumDeclaredTasks(strtoint32(words[1]));
149 rcpsp_.set_release_date(strtoint32(words[2]));
150 rcpsp_.set_due_date(strtoint32(words[3]));
151 rcpsp_.set_tardiness_cost(strtoint32(words[4]));
152 rcpsp_.set_mpm_time(strtoint32(words[5]));
153 } else if (words.size() == 2 && words[0] == "PRECEDENCE") {
154 load_status_ = PRECEDENCE_SECTION;
155 } else {
156 ReportError(line);
157 }
158 break;
159 }
160 case PRECEDENCE_SECTION: {
161 if (words[0] == "jobnr.") {
162 // Nothing to do.
163 } else if (words.size() >= 3) {
164 const int task_index = strtoint32(words[0]) - 1;
165 CHECK_EQ(task_index, rcpsp_.tasks_size());
166 recipe_sizes_[task_index] = strtoint32(words[1]);
167 const int num_successors = strtoint32(words[2]);
168 if (words.size() != 3 + num_successors) {
169 ReportError(line);
170 break;
171 }
172 Task* const task = rcpsp_.add_tasks();
173 for (int i = 0; i < num_successors; ++i) {
174 // The array of tasks is 0-based for us.
175 task->add_successors(strtoint32(words[3 + i]) - 1);
176 }
177 } else if (words[0] == "REQUESTS/DURATIONS") {
178 load_status_ = REQUEST_SECTION;
179 } else {
180 ReportError(line);
181 }
182 break;
183 }
184 case REQUEST_SECTION: {
185 if (words[0] == "jobnr.") {
186 // Nothing to do.
187 } else if (words.size() == 3 + rcpsp_.resources_size()) {
188 // Start of a new task (index is 0-based for us).
189 current_task_ = strtoint32(words[0]) - 1;
190 const int current_recipe = strtoint32(words[1]) - 1;
191 CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
192 if (current_recipe != 0) {
193 ReportError(line);
194 break;
195 }
196 Recipe* const recipe =
197 rcpsp_.mutable_tasks(current_task_)->add_recipes();
198 recipe->set_duration(strtoint32(words[2]));
199 for (int i = 0; i < rcpsp_.resources_size(); ++i) {
200 const int demand = strtoint32(words[3 + i]);
201 if (demand != 0) {
202 recipe->add_demands(demand);
203 recipe->add_resources(i);
204 }
205 }
206 } else if (words.size() == 2 + rcpsp_.resources_size()) {
207 // New recipe for a current task.
208 const int current_recipe = strtoint32(words[0]) - 1;
209 CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
210 Recipe* const recipe =
211 rcpsp_.mutable_tasks(current_task_)->add_recipes();
212 recipe->set_duration(strtoint32(words[1]));
213 for (int i = 0; i < rcpsp_.resources_size(); ++i) {
214 const int demand = strtoint32(words[2 + i]);
215 if (demand != 0) {
216 recipe->add_demands(demand);
217 recipe->add_resources(i);
218 }
219 }
220 } else if (words[0] == "RESOURCEAVAILABILITIES" ||
221 (words[0] == "RESOURCE" && words[1] == "AVAILABILITIES")) {
222 load_status_ = RESOURCE_SECTION;
223 } else {
224 ReportError(line);
225 }
226 break;
227 }
228 case RESOURCE_SECTION: {
229 if (words.size() == 2 * rcpsp_.resources_size()) {
230 // Nothing to do.
231 } else if (words.size() == rcpsp_.resources_size()) {
232 for (int i = 0; i < words.size(); ++i) {
233 rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
234 }
235 load_status_ = PARSING_FINISHED;
236 } else {
237 ReportError(line);
238 }
239 break;
240 }
241 case RESOURCE_MIN_SECTION: {
242 LOG(FATAL) << "Should not be here";
243 break;
244 }
245 case PARSING_FINISHED: {
246 break;
247 }
248 case ERROR_FOUND: {
249 break;
250 }
251 }
252}
253
254void RcpspParser::ProcessRcpspMaxLine(const std::string& line) {
255 const std::vector<std::string> words =
256 absl::StrSplit(line, absl::ByAnyChar(" :\t[]\r"), absl::SkipEmpty());
257
258 switch (load_status_) {
259 case NOT_STARTED: {
260 ReportError(line);
261 break;
262 }
263 case HEADER_SECTION: {
264 rcpsp_.set_is_rcpsp_max(true);
265 if (words.size() == 2) {
266 rcpsp_.set_is_consumer_producer(true);
267 } else if (words.size() < 4 || strtoint32(words[3]) != 0) {
268 ReportError(line);
269 break;
270 }
271
272 if (words.size() == 5) {
273 rcpsp_.set_deadline(strtoint32(words[4]));
274 rcpsp_.set_is_resource_investment(true);
275 }
276
277 SetNumDeclaredTasks(strtoint32(words[0]));
278 temp_delays_.resize(num_declared_tasks_ + 2);
279
280 // Creates resources.
281 if (rcpsp_.is_consumer_producer()) {
282 const int num_nonrenewable_resources = strtoint32(words[1]);
283 for (int i = 0; i < num_nonrenewable_resources; ++i) {
284 Resource* const res = rcpsp_.add_resources();
285 res->set_max_capacity(-1);
286 res->set_min_capacity(-1);
287 res->set_renewable(false);
288 res->set_unit_cost(0);
289 }
290 } else {
291 const int num_renewable_resources = strtoint32(words[1]);
292 const int num_nonrenewable_resources = strtoint32(words[2]);
293 for (int i = 0; i < num_renewable_resources; ++i) {
294 Resource* const res = rcpsp_.add_resources();
295 res->set_max_capacity(-1);
296 res->set_renewable(true);
297 res->set_unit_cost(0);
298 }
299 for (int i = 0; i < num_nonrenewable_resources; ++i) {
300 Resource* const res = rcpsp_.add_resources();
301 res->set_max_capacity(-1);
302 res->set_min_capacity(-1);
303 res->set_renewable(false);
304 res->set_unit_cost(0);
305 }
306 }
307
308 // Set up for the next section.
309 load_status_ = PRECEDENCE_SECTION;
310 current_task_ = 0;
311 break;
312 }
313 case PROJECT_SECTION: {
314 LOG(FATAL) << "Should not be here";
315 break;
316 }
317 case INFO_SECTION: {
318 LOG(FATAL) << "Should not be here";
319 break;
320 }
321 case PRECEDENCE_SECTION: {
322 if (words.size() < 3) {
323 ReportError(line);
324 break;
325 }
326
327 const int task_id = strtoint32(words[0]);
328 if (task_id != current_task_) {
329 ReportError(line);
330 break;
331 } else {
332 current_task_++;
333 }
334
335 const int num_recipes = strtoint32(words[1]);
336 recipe_sizes_[task_id] = num_recipes;
337 const int num_successors = strtoint32(words[2]);
338
339 Task* const task = rcpsp_.add_tasks();
340
341 // Read successors.
342 for (int i = 0; i < num_successors; ++i) {
343 task->add_successors(strtoint32(words[3 + i]));
344 }
345
346 // Read flattened delays into temp_delays_.
347 for (int i = 3 + num_successors; i < words.size(); ++i) {
348 temp_delays_[task_id].push_back(strtoint32(words[i]));
349 }
350
351 if (task_id == num_declared_tasks_ + 1) {
352 // Convert the flattened delays into structured delays (1 vector per
353 // successor) in the task_size.
354 for (int t = 1; t <= num_declared_tasks_; ++t) {
355 const int num_recipes = recipe_sizes_[t];
356 const int num_successors = rcpsp_.tasks(t).successors_size();
357 int count = 0;
358 for (int s = 0; s < num_successors; ++s) {
359 PerSuccessorDelays* const succ_delays =
360 rcpsp_.mutable_tasks(t)->add_successor_delays();
361 for (int r1 = 0; r1 < num_recipes; ++r1) {
362 PerRecipeDelays* const recipe_delays =
363 succ_delays->add_recipe_delays();
364 const int other = rcpsp_.tasks(t).successors(s);
365 const int num_other_recipes = recipe_sizes_[other];
366 for (int r2 = 0; r2 < num_other_recipes; ++r2) {
367 recipe_delays->add_min_delays(temp_delays_[t][count++]);
368 }
369 }
370 }
371 CHECK_EQ(count, temp_delays_[t].size());
372 }
373
374 // Setup for next section.
375 current_task_ = 0;
376 load_status_ = REQUEST_SECTION;
377 }
378 break;
379 }
380 case REQUEST_SECTION: {
381 if (words.size() == 3 + rcpsp_.resources_size()) {
382 // Start of a new task.
383 current_task_ = strtoint32(words[0]);
384
385 // 0 based indices for the recipe.
386 const int current_recipe = strtoint32(words[1]) - 1;
387 CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
388 if (current_recipe != 0) {
389 ReportError(line);
390 break;
391 }
392 Recipe* const recipe =
393 rcpsp_.mutable_tasks(current_task_)->add_recipes();
394 recipe->set_duration(strtoint32(words[2]));
395 for (int i = 0; i < rcpsp_.resources_size(); ++i) {
396 const int demand = strtoint32(words[3 + i]);
397 if (demand != 0) {
398 recipe->add_demands(demand);
399 recipe->add_resources(i);
400 }
401 }
402 } else if (words.size() == 2 + rcpsp_.resources_size() &&
403 rcpsp_.is_consumer_producer()) {
404 // Start of a new task.
405 current_task_ = strtoint32(words[0]);
406
407 // 0 based indices for the recipe.
408 const int current_recipe = strtoint32(words[1]) - 1;
409 CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
410 if (current_recipe != 0) {
411 ReportError(line);
412 break;
413 }
414 Recipe* const recipe =
415 rcpsp_.mutable_tasks(current_task_)->add_recipes();
416 recipe->set_duration(0);
417 for (int i = 0; i < rcpsp_.resources_size(); ++i) {
418 const int demand = strtoint32(words[2 + i]);
419 if (demand != 0) {
420 recipe->add_demands(demand);
421 recipe->add_resources(i);
422 }
423 }
424 } else if (words.size() == 2 + rcpsp_.resources_size()) {
425 // New recipe for a current task.
426 const int current_recipe = strtoint32(words[0]) - 1;
427 CHECK_EQ(current_recipe, rcpsp_.tasks(current_task_).recipes_size());
428 Recipe* const recipe =
429 rcpsp_.mutable_tasks(current_task_)->add_recipes();
430 recipe->set_duration(strtoint32(words[1]));
431 for (int i = 0; i < rcpsp_.resources_size(); ++i) {
432 const int demand = strtoint32(words[2 + i]);
433 if (demand != 0) {
434 recipe->add_demands(demand);
435 recipe->add_resources(i);
436 }
437 }
438 }
439 if (current_task_ == num_declared_tasks_ + 1) {
440 if (rcpsp_.is_consumer_producer()) {
441 load_status_ = RESOURCE_MIN_SECTION;
442 } else {
443 load_status_ = RESOURCE_SECTION;
444 }
445 }
446 break;
447 }
448 case RESOURCE_SECTION: {
449 if (words.size() == rcpsp_.resources_size()) {
450 for (int i = 0; i < words.size(); ++i) {
451 if (rcpsp_.is_resource_investment()) {
452 rcpsp_.mutable_resources(i)->set_unit_cost(strtoint32(words[i]));
453 } else {
454 rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
455 }
456 }
457 load_status_ = PARSING_FINISHED;
458 } else {
459 ReportError(line);
460 }
461 break;
462 }
463 case RESOURCE_MIN_SECTION: {
464 if (words.size() == rcpsp_.resources_size()) {
465 for (int i = 0; i < words.size(); ++i) {
466 rcpsp_.mutable_resources(i)->set_min_capacity(strtoint32(words[i]));
467 }
468 load_status_ = RESOURCE_SECTION;
469 } else {
470 ReportError(line);
471 }
472 break;
473 }
474 case PARSING_FINISHED: {
475 break;
476 }
477 case ERROR_FOUND: {
478 break;
479 }
480 }
481}
482
483void RcpspParser::ProcessPattersonLine(const std::string& line) {
484 const std::vector<std::string> words =
485 absl::StrSplit(line, absl::ByAnyChar(" :\t[]\r"), absl::SkipEmpty());
486
487 if (words.empty()) return;
488
489 switch (load_status_) {
490 case NOT_STARTED: {
491 ReportError(line);
492 break;
493 }
494 case HEADER_SECTION: {
495 if (words.size() != 2) {
496 ReportError(line);
497 break;
498 }
499 SetNumDeclaredTasks(strtoint32(words[0]) - 2); // Remove the 2 sentinels.
500
501 // Creates resources.
502 const int num_renewable_resources = strtoint32(words[1]);
503 for (int i = 0; i < num_renewable_resources; ++i) {
504 Resource* const res = rcpsp_.add_resources();
505 res->set_max_capacity(-1);
506 res->set_min_capacity(-1);
507 res->set_renewable(true);
508 res->set_unit_cost(0);
509 }
510
511 // Set up for the next section.
512 load_status_ = RESOURCE_SECTION;
513 break;
514 }
515 case PROJECT_SECTION: {
516 LOG(FATAL) << "Should not be here";
517 break;
518 }
519 case INFO_SECTION: {
520 LOG(FATAL) << "Should not be here";
521 break;
522 }
523 case PRECEDENCE_SECTION: {
524 if (unreads_ > 0) {
525 for (int i = 0; i < words.size(); ++i) {
526 rcpsp_.mutable_tasks(current_task_)
527 ->add_successors(strtoint32(words[i]) - 1);
528 unreads_--;
529 CHECK_GE(unreads_, 0);
530 }
531 } else {
532 if (words.size() < 2 + rcpsp_.resources_size()) {
533 ReportError(line);
534 break;
535 }
536 CHECK_EQ(current_task_, rcpsp_.tasks_size());
537 Task* const task = rcpsp_.add_tasks();
538 Recipe* const recipe = task->add_recipes();
539 recipe->set_duration(strtoint32(words[0]));
540
541 const int num_resources = rcpsp_.resources_size();
542 for (int i = 1; i <= num_resources; ++i) {
543 const int demand = strtoint32(words[i]);
544 if (demand != 0) {
545 recipe->add_demands(demand);
546 recipe->add_resources(i - 1);
547 }
548 }
549
550 unreads_ = strtoint32(words[1 + num_resources]);
551 for (int i = 2 + num_resources; i < words.size(); ++i) {
552 // Successors are 1 based in the data file.
553 task->add_successors(strtoint32(words[i]) - 1);
554 unreads_--;
555 CHECK_GE(unreads_, 0);
556 }
557 }
558
559 if (unreads_ == 0 && ++current_task_ == num_declared_tasks_ + 2) {
560 load_status_ = PARSING_FINISHED;
561 }
562 break;
563 }
564 case REQUEST_SECTION: {
565 LOG(FATAL) << "Should not be here";
566 break;
567 }
568 case RESOURCE_SECTION: {
569 if (words.size() == rcpsp_.resources_size()) {
570 for (int i = 0; i < words.size(); ++i) {
571 rcpsp_.mutable_resources(i)->set_max_capacity(strtoint32(words[i]));
572 }
573 load_status_ = PRECEDENCE_SECTION;
574 current_task_ = 0;
575 } else {
576 ReportError(line);
577 }
578 break;
579 }
580 case RESOURCE_MIN_SECTION: {
581 LOG(FATAL) << "Should not be here";
582 break;
583 }
584 case PARSING_FINISHED: {
585 break;
586 }
587 case ERROR_FOUND: {
588 break;
589 }
590 }
591}
592
593int RcpspParser::strtoint32(const std::string& word) {
594 int result;
595 CHECK(absl::SimpleAtoi(word, &result));
596 return result;
597}
598
599int64 RcpspParser::strtoint64(const std::string& word) {
600 int64 result;
601 CHECK(absl::SimpleAtoi(word, &result));
602 return result;
603}
604
605} // namespace rcpsp
606} // namespace data
607} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
bool ParseFile(const std::string &file_name)
Definition: rcpsp_parser.cc:36
int64_t int64
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 demand
Definition: resource.cc:123