mip_read_graph.cc

Go to the documentation of this file.

#include <lemon/smart_graph.h>
#include <utils/graph_utils.hh>
#include <minlca/greedy.hh>
#include <minlca/mip-model.hh>
#include <utils/timer.hh>
#include <minlca/profiler.hh>
#include <minlca/optimisation-profiler.hh>
using namespace std;
using namespace lemon;
using namespace minlca;
using namespace minlca::utils;

typedef GrbMip Mip;


int main(int argc, char **argv)
{
  GRAPH_TYPEDEFS(SmartGraph);
  SmartGraph g;
  ifstream graphFile(argv[1]);
  GraphFormat format = RMF;

  if (string(argv[2]) == "GRA") {
    format = GRA;
  }

  Timer timer;
  readGraph(g, format, graphFile);

  graphFile.close();

  cout << "Graph reading time: " << timer.elapsed() << endl;
  cout << endl;

  int n = countNodes(g);
  cout << "Total nodes: " << n << endl;
  cout << "Total edges: " << countEdges(g) << endl;

  cout << endl;
  cout << "Using greedy nearest:" << endl;

  MinLCAProfiler<MinLCAGreedyNearestBfs<SmartGraph>> greedyNearest(g);
  cout << "Creation elapsed time: " << greedyNearest.creationTime() << endl;
  greedyNearest.init();
  cout << "Initialisation elapsed time: " << greedyNearest.initTime() << endl;

  if (greedyNearest.run() == SOLUTION_FOUND) {
    cout << "Algorithm running time: " << greedyNearest.runTime() << endl;
    cout << "Max colours: " << greedyNearest.maxK() << endl;
    cout << "Colours used: " << greedyNearest.totalColours() << endl;
    cout << "LCA value: " << greedyNearest.lcaValue() << endl;
  }
  else {
    cout << "Could not find a solution!" << endl;
  }

  cout << endl;

  cout << "Using greedy least cost:" << endl;

  MinLCAProfiler<MinLCAGreedyLeastCostBfs<SmartGraph>> greedyLeastCost(g);
  cout << "Creation elapsed time: " << greedyLeastCost.creationTime() << endl;
  greedyLeastCost.init();
  cout << "Initialisation elapsed time: " << greedyLeastCost.initTime() << endl;

  if (greedyLeastCost.run() == SOLUTION_FOUND) {
    cout << "Algorithm running time: " << greedyLeastCost.runTime() << endl;
    cout << "Max colours: " << greedyLeastCost.maxK() << endl;
    cout << "Colours used: " << greedyLeastCost.totalColours() << endl;
    cout << "LCA value: " << greedyLeastCost.lcaValue() << endl;
  }
  else {
    cout << "Could not find a solution!" << endl;
  }

  cout << endl;

  int k;

  if (greedyLeastCost.lcaValue() < greedyNearest.lcaValue()) {
    k = greedyLeastCost.totalColours();
  }
  else {
    k = greedyNearest.totalColours();
  }

  cout << "Using MIP model:" << endl;
  MinLCAOptProfiler<MinLCAOptMip<SmartGraph>> mipModel(g, k);
  mipModel.init();

  if (argc > 4) {
    mipModel.timeLimit(atof(argv[4]));
  }

  if (argc > 5) {
    mipModel.model().getEnv().set(GRB_StringParam_LogFile, argv[5]);
  }

  mipModel.model().getEnv().set(GRB_IntParam_Method, GRB_METHOD_CONCURRENT);
  cout << "Initialisation elapsed time: " << mipModel.initTime() << endl;


  if (greedyLeastCost.lcaValue() < greedyNearest.lcaValue()) {
    mipModel.initialSolution(greedyLeastCost.colouring());
  }
  else {
    mipModel.initialSolution(greedyNearest.colouring());
  }

  cout << "Initial solution elapsed time: " << mipModel.initialSolutionTime() <<
       endl;

  if (mipModel.run() == SOLUTION_FOUND) {
    cout << "Algorithm running time: " << mipModel.runTime() << endl;
    cout << "Max colours: " << mipModel.maxK() << endl;
    cout << "Colours used: " << mipModel.totalColours() << endl;
    cout << "LCA value: " << mipModel.lcaValue() << endl;
    cout << "Optimal?: ";

    if (mipModel.model().getModel().get(GRB_IntAttr_Status) == GRB_OPTIMAL) {
      cout << "YES";
    }
    else {
      cout << "NO";
    }

    cout << endl;

    if (argc > 3) {
      ofstream outfile(argv[3], ofstream::out | ofstream::trunc);

      for (int i = 0; i < n - 1; ++i) {
        Node v = g.nodeFromId(i);
        outfile << mipModel.colouring()[v] << ' ';
      }

      outfile << mipModel.colouring()[g.nodeFromId(n - 1)] << endl;
      outfile.close();
    }
  }
  else {
    cout << "Could not find a solution!" << endl;
  }
}