reachability-algorithms/benchmark/algorithm_bench.cc

#include <src/include/nanobench.h>
#include <doctest/doctest.h>

#include "algorithm/king.h"
#include "algorithm/henzinger_king.h"

#include <algorithm>
#include <random>
#include <fstream>
#include <iostream>
#include <memory>

using namespace graph;

TEST_CASE("Italiano and King inspired algorithms") {
  std::ifstream fdag{ "resources/dag.txt" };
  int u;
  int v;
  Digraph<int> G;
  std::vector<std::pair<int, int>> graphVertices;
  std::vector<std::pair<int, int>> graphVerticesReverse;

  while (fdag >> u >> v) {
    G.insert(u, v);
    graphVertices.push_back(std::make_pair(u, v));
    graphVerticesReverse.push_back(std::make_pair(v, u));
  }

  auto italiano = std::make_unique<algo::Italiano<int>>(G);
  italiano->init();

  auto king = std::make_unique<algo::King<int>>(G);
  king->init();

  ankerl::nanobench::Rng rng;
  rng.shuffle(graphVertices);

  std::vector<std::pair<int, int>> graphVerticesDeleteSubset(graphVertices.begin(), graphVertices.begin() + 25);
  std::vector<std::pair<int, int>> graphVerticesQuerySubset(graphVerticesReverse.begin() + 50, graphVerticesReverse.begin() + 75);

  // Deleting Phase

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Italiano::remove",
         [&italiano, graphVerticesDeleteSubset] {
           italiano->remove(graphVerticesDeleteSubset);
         });
  
  ankerl::nanobench::Bench()
    .epochs(1)
    .run("King::remove",
         [&king, graphVerticesDeleteSubset] {
           king->remove(graphVerticesDeleteSubset);
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Simple::remove(DAG)",
         [&G, graphVerticesDeleteSubset] {
           for (const auto& [w, z] : graphVerticesDeleteSubset) {
             G.remove(w, z);
           }
         });
  
  // Querying Phase

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Italiano::query",
         [&italiano, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(italiano->query(w, z));
           }
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("King::query",
         [&king, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(king->query(w, z));
           }
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Simple::query(DAG)",
         [&G, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(G.contains(w, z));
           }  
         });
}

TEST_CASE("Frigioni and Henzinger/King inspired algorithms") {
  std::ifstream fgeneral{ "resources/general.txt" };
  int u;
  int v;
  Digraph<int> G;
  std::vector<std::pair<int, int>> graphVertices;
  std::vector<std::pair<int, int>> graphVerticesReverse;

  while (fgeneral >> u >> v) {
    G.insert(u, v);
    graphVertices.push_back(std::make_pair(u, v));
    graphVerticesReverse.push_back(std::make_pair(v, u));
  }

  auto frigioni = std::make_unique<algo::Frigioni<int>>(G);
  frigioni->init();

  auto henzingerKing = std::make_unique<algo::HenzingerKing<int>>(G);
  henzingerKing->init();

  ankerl::nanobench::Rng rng;
  rng.shuffle(graphVertices);

  std::vector<std::pair<int, int>> graphVerticesDeleteSubset(graphVertices.begin(), graphVertices.begin() + 25);
  std::vector<std::pair<int, int>> graphVerticesQuerySubset(graphVerticesReverse.begin() + 50, graphVerticesReverse.begin() + 75);

  // Deleting Phase

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Frigioni::remove",
         [&frigioni, graphVerticesDeleteSubset] {
           frigioni->remove(graphVerticesDeleteSubset);
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("HenzingerKing::remove",
         [&henzingerKing, graphVerticesDeleteSubset] {
           henzingerKing->remove(graphVerticesDeleteSubset);
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Simple::remove(General)",
         [&G, graphVerticesDeleteSubset] {
           for (const auto& [w, z] : graphVerticesDeleteSubset) {
             G.remove(w, z);
           }
         });

  // Querying Phase

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Frigioni::query",
         [&frigioni, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(frigioni->query(w, z));
           }
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("HenzingerKing::query",
         [&henzingerKing, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(henzingerKing->query(w, z));
           }
         });

  ankerl::nanobench::Bench()
    .epochs(1)
    .run("Simple::query(General)",
         [&G, graphVerticesQuerySubset] {
           for (const auto& [w, z] : graphVerticesQuerySubset) {
             ankerl::nanobench::doNotOptimizeAway(G.contains(w, z));
           }
         });
}