OR-Tools  8.1
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 
14 #include "ortools/data/rcpsp_parser.h"
15 
16 #include "absl/strings/match.h"
17 #include "absl/strings/numbers.h"
18 #include "absl/strings/str_split.h"
19 #include "ortools/base/filelineiter.h"
20 #include "ortools/data/rcpsp.pb.h"
21 
22 namespace operations_research {
23 namespace data {
24 namespace rcpsp {
25 
26 RcpspParser::RcpspParser()
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 
36 bool 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 
68 void RcpspParser::ReportError(const std::string& line) {
69  LOG(ERROR) << "Error: status = " << load_status_ << ", line = " << line;
70  load_status_ = ERROR_FOUND;
71 }
72 
73 void RcpspParser::SetNumDeclaredTasks(int t) {
74  num_declared_tasks_ = t;
75  recipe_sizes_.resize(t + 2, 0); // The data format adds 2 sentinels.
76 }
77 
78 void 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 
254 void 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 
483 void 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 
593 int RcpspParser::strtoint32(const std::string& word) {
594  int result;
595  CHECK(absl::SimpleAtoi(word, &result));
596  return result;
597 }
598 
599 int64 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
INFO
const int INFO
Definition: log_severity.h:31
VLOG
#define VLOG(verboselevel)
Definition: base/logging.h:978
LOG
#define LOG(severity)
Definition: base/logging.h:420
ERROR
const int ERROR
Definition: log_severity.h:32
operations_research::data::rcpsp::RcpspParser::RcpspParser
RcpspParser()
Definition: rcpsp_parser.cc:26
FATAL
const int FATAL
Definition: log_severity.h:32
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
int64
int64_t int64
Definition: integral_types.h:34
filelineiter.h
operations_research::data::rcpsp::RcpspParser::ParseFile
bool ParseFile(const std::string &file_name)
Definition: rcpsp_parser.cc:36
demand
int64 demand
Definition: resource.cc:123
rcpsp.pb.h
rcpsp_parser.h
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
FileLines
Definition: filelineiter.h:115