maxcut.cc

#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/property_map/property_map.hpp>
#include <fstream>
#include <iostream>
#include <scil/scil.h>
#include <scil/constraints/cut.h>
#include <string>

//#define INPATH "/home/baumann/projects/scil/tests/"
#define INPATH ""

using std::cout;
using std::cerr;
using std::endl;
using std::ifstream;
using std::atoi;

using namespace boost;
using namespace SCIL;
using namespace std;

typedef adjacency_list<vecS, vecS, undirectedS> Graph;
typedef boost::graph_traits<Graph> GraphTraits;
typedef GraphTraits::vertex_descriptor vertex_descriptor;
typedef GraphTraits::edge_descriptor edge_descriptor;

class mc_heuristic : public primal_heuristic {
   private:
      Graph& G;
      var_map<edge_descriptor>& VM;
      int start;

   public:
      mc_heuristic(Graph& G_, var_map<edge_descriptor>& VM_)
         : G(G_), VM(VM_), start(1) { }
      int heuristic(subproblem& S, solution& newSol) {
         if( start > 0 ) {
            start--;
            return 0;
         }

         typedef map<edge_descriptor, double> weight_map_t;
         typedef map<vertex_descriptor, size_t> vertex_index_t;

         weight_map_t tc;
         edge_descriptor e;
         BGL_FORALL_EDGES(e, G, Graph)
            tc[e] = fabs(S.value(VM[e]) - .5);
         vertex_index_t vertex_index_map;
         int i = 0;
         vertex_descriptor v;
         BGL_FORALL_VERTICES(v, G, Graph)
            vertex_index_map[v] = i++;
      
         associative_property_map<weight_map_t> pm_weight(tc);
         typedef associative_property_map<vertex_index_t> pm_vertex_index_t;
         pm_vertex_index_t pm_vertex_index(vertex_index_map);

         list<edge_descriptor> tree;

         kruskal_minimum_spanning_tree(G, back_inserter(tree), boost::weight_map
            (pm_weight).vertex_index_map(pm_vertex_index));

         BGL_FORALL_EDGES(e, G, Graph)
            tc[e] = -1.;
      
         BOOST_FOREACH(e, tree)
            tc[e] = S.value(VM[e]) > .5 ? 1. : 0.;

         map<vertex_descriptor, bool> color;
         v = *(vertices(G).first);
         if(!SCIL::color_graph<Graph, vertex_descriptor, edge_descriptor> 
             (G, v, tc, color)) {
            return 0;
         }

         BGL_FORALL_EDGES(e, G, Graph)
            if( color[source(e, G)] != color[target(e, G)] )
               newSol.set_value(VM[e], 1.);
            else
               newSol.set_value(VM[e], 0.);
         return 1;
      }

};

bool readgraph(int base, const char* infile, Graph& G, 
               map<vertex_descriptor, int>& vertex_index,
               map<edge_descriptor, double>& edge_property) {
   string path(INPATH);
   path += infile;
   ifstream file(path.c_str());
   if( file.fail() ) {
      cerr << "%%%%%%%% Could not open file " << infile << endl;
      cerr << "%%%%%%%% tried " << path << endl;
      exit(1);
   }
   double sign = 1.;
   if( base == -1 ) {
      base = 1;
      sign = -1.;
   }

   //skip leading comments, i.e. ignore the line if the
   //first character is not a number
   char buf[1024];
   while( file.peek() != '#' ) //search for '#' indicating the size of the graph
      file.getline(buf, 1024);

   //read the size of the graph and the edge data
   char c;
   int s, t, numnodes, numedges;
   double u;
   file >> c;
   file >> numnodes; //read the number of nodes in the graph
   file >> numedges; //read the number of edges in the graph

   vertex_descriptor* nodelist = new vertex_descriptor[numnodes];

   for( int i = 0; i < numnodes; i++) {
      nodelist[i] = add_vertex(G);
      vertex_index[nodelist[i]]=i;
   }

    while((file >> s >> t >> u) && file.good()) {
       edge_descriptor e;
       e = (add_edge(nodelist[s-base], nodelist[t-base], G)).first;
       edge_property[e] = sign * u;
   }

   delete[]nodelist;
   return true;
}


int main(int argc, char** argv)
{
   if( argc != 3 ) {
      cerr << "Please give the base of the node numbering";
      cerr << " and the name of an input file!" << endl;
      return 1;
   }

   //initialize the graph
   Graph G;
   map<vertex_descriptor, int> vertex_index;
   map<edge_descriptor, double> edge_property;
   int base = atoi(argv[1]);
   readgraph(base, argv[2], G, vertex_index, edge_property);

   //initialize the ILP
   ILP_Problem IP(Optsense_Max);
   edge_descriptor e;
   //FIXME
   //var_map<edge> VM;
   row_map<edge_descriptor> VM;
   BGL_FORALL_EDGES(e, G, Graph)
      VM[e]=IP.add_binary_variable(edge_property[e]);

   //add the symbolic constraint
   CUT<Graph>* scc = new CUT<Graph>(G, VM);
   IP.add_sym_constraint(scc);

   //IP.set_primal_heuristic(new mc_heuristic(G, VM));
   //solve the problem
   IP.optimize();

   //output the solution
   solution sol =  IP.get_solution();
   double optimum = IP.get_optimum();
   cout << "\nName: " << argv[2] << endl;

   if(base == -1) optimum *= -1;
   cout.precision(2);
   cout << fixed << "solution value: " << optimum << endl;

   list<vertex_descriptor> configuration = scc->getConfiguration(sol);
   vertex_descriptor v;
   BOOST_FOREACH(v, configuration)
      cout << vertex_index[v] + abs(base) << " ";
   cout << endl;

   return 0;
}

---