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 "matroid_intersection.h"
16

17
#include <cassert>
18
#include <iostream>
19
#include <map>
20
#include <queue>
21
#include <set>
22
#include <vector>
23

24
#include "absl/container/btree_map.h"
25
#include "matroid.h"
26
#include "submodular_function.h"
27

28
void MaxIntersection(Matroid* matroid_a, Matroid* matroid_b,
29
                     const std::vector<int>& elements) {
30
  matroid_a->Reset();
31
  matroid_b->Reset();
32
  // Adjacency lists;
33
  std::map<int, std::vector<int>> exchange_graph;
34
  while (true) {
35
    // Greedily add elements to the solution;
36
    for (int element : elements) {
37
      if (matroid_a->InCurrent(element)) {
38
        continue;
39
      }
40
      if (matroid_a->CanAdd(element) && matroid_b->CanAdd(element)) {
41
        matroid_a->Add(element);
42
        matroid_b->Add(element);
43
      }
44
    }
45

46
    // Construct the exchange graph.
47
    exchange_graph.clear();
48
    for (int element : elements) {
49
      if (matroid_a->InCurrent(element)) {
50
        continue;
51
      }
52
      for (int a_swap : matroid_a->GetAllSwaps(element)) {
53
        exchange_graph[a_swap].push_back(element);
54
      }
55
      for (int b_swap : matroid_b->GetAllSwaps(element)) {
56
        exchange_graph[element].push_back(b_swap);
57
      }
58
    }
59

60
    // Find an augmenting path via BFS.
61
    std::map<int, int> bfs_parent;
62
    std::queue<int> queue;
63
    int aug_path_dest = -1;
64
    for (int element : elements) {
65
      if (matroid_a->InCurrent(element)) {
66
        continue;
67
      }
68
      if (matroid_a->CanAdd(element)) {
69
        bfs_parent[element] = -1;
70
        queue.push(element);
71
      }
72
    }
73
    while (!queue.empty()) {
74
      const int element = queue.front();
75
      queue.pop();
76
      if (!matroid_b->InCurrent(element) && matroid_b->CanAdd(element)) {
77
        aug_path_dest = element;
78
        break;
79
      }
80
      for (int neighbor : exchange_graph[element]) {
81
        if (!bfs_parent.count(neighbor)) {
82
          bfs_parent[neighbor] = element;
83
          queue.push(neighbor);
84
        }
85
      }
86
    }
87

88
    if (aug_path_dest == -1) {
89
      // No augmenting path found.
90
      break;
91
    }
92

93
    // Swap along the augmenting path.
94
    std::cerr << "we are applying an augmenting path" << std::endl;
95
    int out_element = aug_path_dest;
96
    int in_element = bfs_parent[aug_path_dest];
97
    while (in_element != -1) {
98
      matroid_a->Swap(out_element, in_element);
99
      matroid_b->Swap(out_element, in_element);
100
      out_element = bfs_parent[in_element];
101
      in_element = bfs_parent[out_element];
102
    }
103
    matroid_a->Add(out_element);
104
    matroid_b->Add(out_element);
105
  }
106

107
  assert(matroid_a->CurrentIsFeasible());
108
  assert(matroid_b->CurrentIsFeasible());
109
}
110

111
// Returns if an element is needed to be removed from `matroid_` to insert
112
// `element`. Returns "-1" if no element is needed to be remove and "-2" if
113
// the element cannot be swapped.
114
int MinWeightElementToRemove(Matroid* matroid,
115
                             absl::btree_map<int, double>& weight,
116
                             const std::set<int>& const_elements,
117
                             const int element) {
118
  if (matroid->CanAdd(element)) {
119
    return -1;
120
  }
121
  int best_element = -2;
122
  for (const int& swap : matroid->GetAllSwaps(element)) {
123
    if (const_elements.find(swap) != const_elements.end()) continue;
124
    if (best_element < 0 || weight[best_element] > weight[swap]) {
125
      best_element = swap;
126
    }
127
  }
128
  return best_element;
129
}
130

131
void SubMaxIntersection(Matroid* matroid_a, Matroid* matroid_b,
132
                        SubmodularFunction* sub_func_f,
133
                        const std::set<int>& const_elements,
134
                        const std::vector<int>& universe) {
135
  // DO NOT reset the matroids here.
136
  absl::btree_map<int, double> weight;
137
  for (const int& element : universe) {
138
    if (const_elements.count(element)) continue;  // don't add const_elements
139
    int first_swap =
140
        MinWeightElementToRemove(matroid_a, weight, const_elements, element);
141
    int second_swap =
142
        MinWeightElementToRemove(matroid_b, weight, const_elements, element);
143
    if (first_swap == -2 || second_swap == -2) continue;
144
    double total_decrease = weight[first_swap] + weight[second_swap];
145
    double cont_element = sub_func_f->DeltaAndIncreaseOracleCall(element);
146
    if (2 * total_decrease <= cont_element) {
147
      if (first_swap >= 0) {
148
        matroid_a->Remove(first_swap);
149
        matroid_b->Remove(first_swap);
150
        sub_func_f->Remove(first_swap);
151
      }
152
      if (second_swap >= 0 && first_swap != second_swap) {
153
        matroid_a->Remove(second_swap);
154
        matroid_b->Remove(second_swap);
155
        sub_func_f->Remove(second_swap);
156
      }
157
      matroid_a->Add(element);
158
      matroid_b->Add(element);
159
      sub_func_f->Add(element);
160
      weight[element] = cont_element;
161
    }
162
  }
163
}
164