google-research

1
// Copyright 2023 The 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 "greedy_algorithm.h"
16

17
#include <memory>
18
#include <string>
19
#include <vector>
20

21
#include "fairness_constraint.h"
22
#include "matroid.h"
23
#include "matroid_intersection.h"
24
#include "submodular_function.h"
25

26
void GreedyAlgorithm::Init(const SubmodularFunction& sub_func_f,
27
                           const FairnessConstraint& fairness,
28
                           const Matroid& matroid) {
29
  Algorithm::Init(sub_func_f, fairness, matroid);
30
  matroid_by_color_.clear();
31
  solution_.clear();
32
  for (int i = 0; i < fairness_->GetColorNum(); ++i) {
33
    matroid_by_color_.push_back(matroid_->Clone());
34
  }
35
  fairness_matroid_ = fairness_->LowerBoundsToMatroid();
36
}
37

38
void GreedyAlgorithm::Insert(int element) {
39
  const int color = fairness_->GetColor(element);
40
  Matroid* matroid = matroid_by_color_[color].get();
41
  if (matroid->CanAdd(element)) {
42
    matroid->Add(element);
43
  }
44
}
45

46
double GreedyAlgorithm::GetSolutionValue() {
47
  std::vector<int> all_elements;
48
  for (int i = 0; i < matroid_by_color_.size(); ++i) {
49
    const Matroid* matroid = matroid_by_color_[i].get();
50
    const std::vector<int> elements = matroid->GetCurrent();
51
    all_elements.insert(all_elements.end(), elements.begin(), elements.end());
52
  }
53
  MaxIntersection(matroid_.get(), fairness_matroid_.get(), all_elements);
54
  solution_ = matroid_->GetCurrent();
55
  return sub_func_f_->ObjectiveAndIncreaseOracleCall(solution_);
56
}
57

58
std::vector<int> GreedyAlgorithm::GetSolutionVector() { return solution_; }
59

60
std::string GreedyAlgorithm::GetAlgorithmName() const {
61
  return "Basic greedy algorithm";
62
}
63