chinese_postman.cc

#include<scil/scil.h>
#include<scil/constraints/tjoin.h>
#include<boost/graph/iteration_macros.hpp>
#include<boost/graph/adjacency_list.hpp>
#include<map>

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

   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;

void read_instance(char* file_name, Graph& G, var_map<edge_descriptor>& VM, ILP_Problem& IP)
{
   int n, m;
   vertex_descriptor a, b;
   double c;
   char buf[1024];
   char d;
   string s;

   string path(file_name);
   ifstream file(path.c_str());
   if(file.fail()) {
      cerr<<"no file with name "<< file_name<<" found!"<< endl;
      exit(1);
   }
   file >> n >> m;
   for(int i = 0; i < n; i++)
      add_vertex(G);

   file.getline(buf, 1024);

   for(int j = 0; j < m; j++){
      file >> a >> b >> c;
      VM[add_edge(a,b,G).first] = IP.add_binary_variable(c);
   }

}

int main(int argc, char** argv){

   vertex_descriptor v, w;
   edge_descriptor e;
   var_map<edge_descriptor> VM;
   map<vertex_descriptor, bool> T;
   Graph G;

   ILP_Problem IP(Optsense_Min);

   read_instance(argv[1], G, VM, IP);

   vector<int> components(num_vertices(G));
   if(connected_components(G, &components[0]) != 1){
      cerr<<"Graph is not connected!"<<endl;
      exit(1);
   }

   //find vertices with odd degree
   BGL_FORALL_VERTICES(v, G, Graph)
      if(out_degree(v, G) % 2 == 1){
         cout<<v<<endl;
         T[v] = true;
      }
      else{
         cout<<v<<" even"<<endl;
         T[v] = false;
      }
   
   IP.add_sym_constraint(new TJOIN<Graph>(G, VM, T));

   IP.optimize();

   //print solution
   
   solution sol = IP.get_solution();
   cout<<"Additional edges (Minimum T-Join):"<<endl;
   double sum = 0;
   BGL_FORALL_EDGES(e, G, Graph){
     cout<<e<<": "<<sol.value(VM[e])<<endl;
     sum += IP.get_obj_coefficient(VM[e]) * (1 + sol.value(VM[e]));
   }
   cout<<"Weight of Postman Tour: "<<sum<<endl; 
   
   
   return 0;
}

---