Maximum Cut Solver; Modified version of Sahni-Gonzales's greedy heuristics by Kohruman et al.

maxcut-sg.cc

// Maximum Cut 
//   modified version of Sahni and Gonzales's greedy heuristics
//   by S. Kahruman, E. Kolotoglu, S. Butenko, and I. V. Hicks
//
//   http://ise.tamu.edu/people/faculty/butenko/papers/maxcut.pdf

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
#include <unordered_map>

using namespace std;


// === tick a time ===
#include <ctime>
double tick() {
  static clock_t oldtick;
  clock_t newtick = clock();
  double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  oldtick = newtick;
  return diff;
}

struct max_cut_solver {

  size_t n;
  struct edge {
    size_t src, dst;
    double weight;
  };
  vector<edge> edges;
  vector<vector<edge>> adj;

  void add_edge(size_t s, size_t t, double w = 1) {
    edges.push_back( {s, t, w} );
  }
  void make_graph() {
    n = 0;
    for (auto e: edges) 
      n = max(n, max(e.src, e.dst)+1);
    adj.resize(n);
    for (auto e: edges) {
      adj[e.src].push_back(e);
      swap(e.src, e.dst);
      adj[e.src].push_back(e);
    }
  }

  priority_queue< pair<double, size_t> > que;
  vector<double> wS, wT;
  vector<bool> S, T;

  double score(size_t u) {
    return abs(wS[u] - wT[u]);
  }

  void insert(size_t u, vector<bool> &U, vector<double> &wU) {
    U[u] = 1;
    for (auto e: adj[u]) {
      size_t v = e.dst;
      if (S[v] || T[v]) continue;
      wU[v] += e.weight;
      que.push( {score(v), v} );
    }
  }

  double solve() {
    while (!que.empty()) que.pop();
    for (size_t i = 0; i < n; ++i) 
      que.push( {0, i} );

    S.assign(n, 0);  T.assign(n, 0);
    wS.assign(n, 0); wT.assign(n, 0);

    edge emax = *max_element(edges.begin(), edges.end(),
        [](edge a, edge b) { return a.weight < b.weight; });

    double cut = emax.weight;
    insert(emax.src, S, wS);
    insert(emax.dst, T, wT);

    while (!que.empty()) {
      size_t u = que.top().second;
      double d = que.top().first;
      que.pop();
      if (S[u] || T[u]) continue; // already fixed
      if (abs( score(u) - d ) > 1e-8) continue; // already score modified
      cut += max( wS[u], wT[u] );
      if (wS[u] < wT[u]) insert(u, S, wS);
      else               insert(u, T, wT);
    }
    return cut;
  }

  // cf. random cut attains 1/2 opt
  double random() {
    vector<bool> S(n);
    for (size_t i = 0; i < n; ++i)
      S[i] = rand() % 2;

    double cut = 0;
    for (auto e: edges) 
      if (S[e.src] ^ S[e.dst]) 
        cut += e.weight;
    return cut;
  }
};

int main(int argc, char *argv[]) {
  max_cut_solver solver;

  FILE *fp = fopen(argv[1], "r");
  char buf[256];
//  fgets(buf, sizeof(buf), fp); // skip first line

  while ( fgets(buf, sizeof(buf), fp) ) {
    size_t s, t;
    double w;
    if ( sscanf(buf, "%zd %zd %lf", &s, &t, &w) == 2) w = 1;
    solver.add_edge(s, t, w);
  }

  solver.make_graph();

  tick();
  printf("[Sahni, Gonzales] %f", solver.solve());
  printf(", %f[s]\n", tick());

}