greedy_binomial_random.cc

Go to the documentation of this file.

#include <iostream>
#include <lemon/smart_graph.h>
#include <utils/generators/binomial.hh>
#include <minlca/greedy.hh>
#include <minlca/profiler.hh>
#include <lemon/graph_to_eps.h>
using namespace std;
using namespace lemon;
using namespace minlca;
using namespace minlca::utils;

template<typename Graph>
int shape(typename Graph::Node)
{
  return 0;
}


int main(int argc, char **argv)
{
  GRAPH_TYPEDEFS(BinomialRandom<>);
  Timer timer;
  BinomialRandom<> g(atoi(argv[3]));
  g.init(atoi(argv[1]), atof(argv[2])).generate();
  cout << "Graph generation time: " << timer.elapsed() << endl;
  cout << endl;

  int n = countNodes(g);
  cout << "Total nodes: " << n << endl;
  cout << "Total edges: " << countEdges(g) << endl;
  cout << "Edge prob.: " << g.p() << endl;
  cout << "Random seed: " << argv[3] << endl;

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

  MinLCAProfiler<MinLCAGreedyNearestBfs<BinomialRandom<>>> 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<BinomialRandom<>>> 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;
  }

  BinomialRandom<>::NodeMap<dim2::Point<double>> coords(g);

  for (NodeIt v(g); v != INVALID; ++v) {
    int id = g.id(v);
    coords[v] = dim2::Point<double>(cos(id * 2.0 * M_PI / n),
                                    sin(id * 2.0 * M_PI / n));
  }

  auto shapes = functorToMap(shape<BinomialRandom<>>);

  if (argc > 4)
    graphToEps(g, argv[4])
    .coords(coords)
    .nodeShapes(shapes)
    .nodeScale(.003)
    .edgeWidthScale(.0005)
    .undirected()
    .scaleToA4()
    .run();
}