19#include "absl/log/check.h"
20#include "ortools/algorithms/set_cover.pb.h"
26void SetCoverModel::UpdateAllSubsetsList() {
27 const SubsetIndex new_size = columns_.
size();
28 const SubsetIndex old_size(all_subsets_.size());
29 DCHECK_LE(old_size, new_size);
30 all_subsets_.resize(new_size.value());
31 for (SubsetIndex subset(old_size); subset < new_size; ++subset) {
32 all_subsets_[subset.value()] = subset;
41 CHECK_EQ(all_subsets_.size(), columns_.
size());
42 CHECK_EQ(all_subsets_.size(), subset_costs_.
size());
43 row_view_is_valid_ =
false;
47 columns_.
back().push_back(element);
48 num_elements_ = std::max(num_elements_, element + 1);
50 row_view_is_valid_ =
false;
58 CHECK(std::isfinite(cost));
60 const SubsetIndex subset_index(subset);
62 const SubsetIndex new_size = std::max(
num_subsets, subset_index + 1);
64 subset_costs_.
resize(new_size, 0.0);
65 subset_costs_[subset_index] = cost;
66 UpdateAllSubsetsList();
67 row_view_is_valid_ =
false;
71 const SubsetIndex subset_index(subset);
72 const SubsetIndex new_size = std::max(columns_.
size(), subset_index + 1);
73 subset_costs_.
resize(new_size, 0.0);
75 UpdateAllSubsetsList();
76 const ElementIndex new_element(element);
77 columns_[subset_index].
push_back(new_element);
78 num_elements_ = std::max(num_elements_, new_element + 1);
79 row_view_is_valid_ =
false;
86 subset_costs_.
resize(size, 0.0);
91 const SubsetIndex size = std::max(columns_.
size(), SubsetIndex(subset + 1));
92 subset_costs_.
resize(size, 0.0);
95 columns_[SubsetIndex(subset)].
reserve(num_entries);
99 if (row_view_is_valid_) {
104 for (SubsetIndex subset(0); subset < columns_.
size(); ++subset) {
105 std::sort(columns_[subset].
begin(), columns_[subset].
end());
106 for (
const ElementIndex element : columns_[subset]) {
107 ++row_sizes[element];
110 for (ElementIndex element(0); element < num_elements_; ++element) {
111 rows_[element].
reserve(EntryIndex(row_sizes[element]));
113 for (SubsetIndex subset(0); subset < columns_.
size(); ++subset) {
114 for (
const ElementIndex element : columns_[subset]) {
118 row_view_is_valid_ =
true;
122 CHECK_GT(num_elements_, 0);
123 CHECK_GT(columns_.
size(), 0);
124 CHECK_EQ(columns_.
size(), subset_costs_.
size());
127 for (
const Cost cost : subset_costs_) {
131 CHECK_GT(
column.size(), 0);
132 for (
const ElementIndex element :
column) {
136 for (ElementIndex element(0); element < num_elements_; ++element) {
137 CHECK_GE(coverage[element], 0);
138 if (coverage[element] == 0) {
142 VLOG(1) <<
"Max possible coverage = "
143 << *std::max_element(coverage.
begin(), coverage.
end());
144 for (SubsetIndex subset(0); subset < columns_.
size(); ++subset) {
145 CHECK_EQ(all_subsets_[subset.value()], subset) <<
"subset = " << subset;
152 for (SubsetIndex subset(0); subset < columns_.
size(); ++subset) {
153 SetCoverProto::Subset* subset_proto =
message.add_subset();
154 subset_proto->set_cost(subset_costs_[subset]);
155 std::sort(columns_[subset].
begin(), columns_[subset].
end());
156 for (
const ElementIndex element : columns_[subset]) {
157 subset_proto->add_element(element.value());
165 subset_costs_.
clear();
167 SubsetIndex subset_index(0);
168 for (
const SetCoverProto::Subset& subset_proto :
message.subset()) {
169 subset_costs_[SubsetIndex(subset_index)] = subset_proto.cost();
170 if (subset_proto.element_size() > 0) {
171 columns_[subset_index].
reserve(EntryIndex(subset_proto.element_size()));
172 for (
auto element : subset_proto.element()) {
173 columns_[subset_index].
push_back(ElementIndex(element));
175 ElementIndex(std::max(num_elements_.value(), element + 1));
180 UpdateAllSubsetsList();
void push_back(const value_type &x)
void ImportModelFromProto(const SetCoverProto &message)
Imports the model from a SetCoverProto.
void SetSubsetCost(int subset, Cost cost)
void AddEmptySubset(Cost cost)
void ReserveNumElementsInSubset(int num_elements, int subset)
Reserves num_elements rows in the column indexed by subset.
SetCoverProto ExportModelAsProto()
void AddElementToSubset(int element, int subset)
Adds 'element' to and already existing 'subset'.
void ReserveNumSubsets(int num_subsets)
Reserves num_subsets columns in the model.
bool ComputeFeasibility() const
void CreateSparseRowView()
Creates the sparse ("dual") representation of the problem.
SubsetIndex num_subsets() const
void AddElementToLastSubset(int element)
ElementIndex num_elements() const
void resize(IntType size)
void reserve(IntType size)
In SWIG mode, we don't want anything besides these top-level includes.
glop::StrictITIVector< EntryIndex, ElementIndex > SparseColumn
glop::StrictITIVector< EntryIndex, SubsetIndex > SparseRow
double Cost
Basic non-strict type for cost.
std::optional< int64_t > end