Greedy Set Cover Sample Implementation

greedy_set_cover.cpp

#include <iostream>
#include <iterator>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <cassert>

using namespace std;

struct subset {
  int cost;
  set<int> elements;

  static string to_s(const subset &ss) {
    const set<int> &v = ss.elements;
    ostringstream o;
    o << "Cost " << ss.cost << " (";
    copy(v.begin(), v.end(), ostream_iterator<int>(o, " "));
    o << ")";
    return o.str();
  }
};

struct greedy_set_cover {
  int universe; // Defines the number of elements in the universe.
  vector<subset> subsets;

  void input(istream &in) {
    int m; // The number of the subsets.
    in >> universe;
    in >> m;
    for (int k = 0; k < m; k++) {
      subset ss;
      int cost;
      in >> cost;
      ss.cost = cost;
      int card; // The cardinality of a subset.
      in >> card;
      for (int j = 0; j < card; j++) {
        int v;
        in >> v;
        ss.elements.insert(v);
      }
      subsets.push_back(ss);
    }
  }

  void show() {
    cout << "Universe " << universe << endl;
    transform(subsets.begin(), subsets.end(),
        ostream_iterator<string>(cout, "\n"), subset::to_s);
  }

  int solve() {
    set<int> covered; // Set of elements covered so far.
    vector<int> answer;
    vector<int> costs;
    while (covered.size() < universe) {
      vector<double> ce; // Cost effectiveness.
      for (vector<subset>::iterator ss = subsets.begin();
          ss != subsets.end();
          ss++) {
        set<int> uncovered;
        set_difference(ss->elements.begin(), ss->elements.end(),
            covered.begin(), covered.end(),
            inserter(uncovered, uncovered.end()));
        double d = ((uncovered.size() == 0)
            ? numeric_limits<double>::infinity()
            : (ss->cost) / uncovered.size());
        ce.push_back(d);
      }
      vector<double>::iterator min_iter = min_element(ce.begin(), ce.end());
      int index = static_cast<int>(min_iter - ce.begin());
      subset &min_ss = subsets[index];
      covered.insert(min_ss.elements.begin(), min_ss.elements.end());
      answer.push_back(index);
      costs.push_back(min_ss.cost);
    }
    int total = accumulate(costs.begin(), costs.end(), 0);
    copy(answer.begin(), answer.end(), ostream_iterator<int>(cout, " "));
    cout << endl << "Total Cost " << total << endl;
    return total;
  }
};

int test(const string &src, int cost, const string &indices) {
  greedy_set_cover sc;
  istringstream iss(src);

  sc.input(iss);
  sc.show();
  sc.solve();

  return 0;
}

/*
 * universe #_of_subsets
 * cost_of_subset_0 size_of_subset_0 element_0_of_subset_0 ...
 * cost_of_subset_1 size_of_subset_1 element_0_of_subset_1 ...
 * ...
 * */
struct _pat {
  string s;
  int c;
  string i;
} patterns[] = {
  {
    string(
        "5 3"
        " 5 3 4 1 3"
        " 10 2 2 5"
        " 3 4 1 4 3 2"
        ),
    13,
    string("1 2")
  }
};

int main() {
  /* Testing infinity.
     double pinf = std::numeric_limits<double>::infinity();
     double ninf = - pinf;
     cout << "-inf < inf " << ((ninf < pinf) ? "yes" : "no") << endl;
     cout << "0.0 < inf " << ((0.0 < pinf) ? "yes" : "no") << endl;
     cout << "1.0 < inf " << ((1.0 < pinf) ? "yes" : "no") << endl;
     */
  for (int i = 0; i < sizeof(patterns)/sizeof(patterns[0]); i++) {
    test(patterns[i].s, patterns[i].c, patterns[i].i);
  }
  return 0;
}