google-research

1
// Copyright 2024 The Google Research Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
#include "pokec_oracle.h"
16

17
#include <fstream>
18
#include <iostream>
19
#include <map>
20
#include <ostream>
21
#include <string>
22

23
#include "absl/container/btree_map.h"
24
#include "utils.h"
25

26
namespace fair_secretary {
27

28
using std::map;
29
using std::string;
30
using std::vector;
31

32
vector<SecretaryInstance> PokecOracle::GetSecretaryInput() {
33
  string input_bmi = "";
34
  string input_edges = "";
35
  std::ifstream in_bmi(input_bmi);
36
  std::ifstream in_edges(input_edges);
37
  absl::btree_map<int, int> nodes;
38
  absl::btree_map<int, int> ids;
39
  int id, color;
40
  int counter = 0;
41
  while (in_bmi >> id >> color) {
42
    if (nodes.find(id) != nodes.end()) {
43
      std::cout << "Error: ID '" << id  << "' does not exists." << std::endl;
44
    }
45
    nodes[id] = color;
46
    ids[id] = counter++;
47
  }
48
  std::cout << counter << std::endl;
49
  vector<int> degrees(counter, 0);
50
  int v1, v2;
51
  while (in_edges >> v1 >> v2) {
52
    if (ids.find(v1) != ids.end() && ids.find(v2) != ids.end()) {
53
      degrees[ids[v1]]++;
54
      degrees[ids[v2]]++;
55
    }
56
  }
57
  vector<SecretaryInstance> instance;
58
  instance.reserve(counter);
59
  for (int i = 0; i < counter; i++) {
60
    instance.push_back(SecretaryInstance(degrees[i] + i * 0.0000001, nodes[i]));
61
  }
62
  num_colors = 0;
63
  for (int i = 0; i < instance.size(); i++) {
64
    num_colors = std::max(num_colors, instance[i].color);
65
  }
66
  num_colors++;
67
  return instance;
68
}
69

70
}  //  namespace fair_secretary
71