ppsp.cc

#include "ppsp.h"

#include <fstream>
#include <functional>
#include <numeric>
#include <sstream>

#include "connectivity.h"
#include "dijkstra2.h"
// #include "dijkstra.h"

using namespace std;
using namespace parlay;

constexpr int NUM_SRC = 5;
constexpr int NUM_ROUND = 5;

template <class Algo>
void run(Algo &algo, const Graph &G, const sequence<NodeId> &largest_cc,
         bool verify) {
  size_t m = largest_cc.size();
  for (int v = 0; v < NUM_SRC; v++) {
    NodeId s = largest_cc[hash32(v) % m];
    NodeId t = largest_cc[hash32(s) % m];
    printf("source %d: %-10d\tdestination %d: %-10d\n", v, s, v, t);
    EdgeTy dist;

    {
      double total_time = 0;
      for (int i = 0; i <= NUM_ROUND; i++) {
        internal::timer tm;
        dist = algo.ppsp(s, t);
        tm.stop();
        if (i == 0) {
          printf("Warmup Round: %f\n", tm.total_time());
        } else {
          printf("Round %d: %f\n", i, tm.total_time());
          total_time += tm.total_time();
        }
      }
      double average_time = total_time / NUM_ROUND;
      printf("PPSP Average time: %f\n", average_time);

      ofstream ofs("ppsp.tsv", ios_base::app);
      ofs << average_time << '\t';
      ofs.close();
    }

    if (verify) {
      printf("Running verifier...\n");

      iternal::Rho_Stepping verifier(G);
      double total_time = 0;
      EdgeTy exp_dist;
      for (int i = 0; i <= NUM_ROUND; i++) {
        internal::timer tm;
        auto dist = verifier.sssp(s);
        exp_dist = dist[t];
        tm.stop();
        if (i == 0) {
          printf("Warmup Round: %f\n", tm.total_time());
        } else {
          printf("Round %d: %f\n", i, tm.total_time());
          total_time += tm.total_time();
        }
      }
      double average_time = total_time / NUM_ROUND;
      printf("SSSP Average time: %f\n", average_time);

      ofstream ofs("ppsp.tsv", ios_base::app);
      ofs << average_time << '\t';
      ofs.close();
      assert(check_equal(dist, exp_dist));
    }

    ofstream ofs("ppsp.tsv", ios_base::app);
    ofs << s << '\t' << t << '\t' << dist << '\n';
    printf("\n");
  }
}

int main(int argc, char *argv[]) {
  if (argc == 1) {
    fprintf(stderr,
            "Usage: %s [-i input_file] [-p parameter] [-w] [-s] [-v] [-a "
            "algorithm]\n"
            "Options:\n"
            "\t-i,\tinput file path\n"
            "\t-p,\tparameter(e.g. delta, rho)\n"
            "\t-w,\tweighted input graph\n"
            "\t-s,\tsymmetrized input graph\n"
            "\t-v,\tverify result\n"
            "\t-a,\talgorithm: [rho-stepping] [delta-stepping] [bellman-ford]\n"
            "\t-b,\tuse bidirectional search\n",
            argv[0]);
    exit(EXIT_FAILURE);
  }
  char c;
  bool weighted = false;
  bool symmetrized = false;
  bool verify = false;
  bool bidirection = false;
  string param;
  int algo = rho_stepping;
  char const *FILEPATH = nullptr;
  while ((c = getopt(argc, argv, "i:p:a:wsvb")) != -1) {
    switch (c) {
      case 'i':
        FILEPATH = optarg;
        break;
      case 'p':
        param = string(optarg);
        break;
      case 'a':
        if (!strcmp(optarg, "rho-stepping")) {
          algo = rho_stepping;
        } else if (!strcmp(optarg, "delta-stepping")) {
          algo = delta_stepping;
        } else if (!strcmp(optarg, "bellman-ford")) {
          algo = bellman_ford;
        } else {
          fprintf(stderr, "Error: Unknown algorithm %s\n", optarg);
          exit(EXIT_FAILURE);
        }
        break;
      case 'w':
        weighted = true;
        break;
      case 's':
        symmetrized = true;
        break;
      case 'v':
        verify = true;
        break;
      case 'b':
        bidirection = true;
        break;
      default:
        fprintf(stderr, "Error: Unknown option %c\n", optopt);
        exit(EXIT_FAILURE);
    }
  }
  Graph G(weighted, symmetrized);

  printf("Reading graph...\n");
  G.read_graph(FILEPATH);
  if (!weighted) {
    printf("Generating edge weights...\n");
    G.generate_weight();
  }

  fprintf(stdout,
          "Running on %s: |V|=%zu, |E|=%zu, param=%s, num_src=%d, "
          "num_round=%d\n",
          FILEPATH, G.n, G.m, param.c_str(), NUM_SRC, NUM_ROUND);

  auto largest_cc = get_largest_cc(G);

  if (algo == rho_stepping) {
    size_t rho = 1 << 20;
    if (param != "") {
      rho = stoull(param);
    }
    Rho_Stepping solver(G, bidirection, rho);
    run(solver, G, largest_cc, verify);
  } else if (algo == delta_stepping) {
    EdgeTy delta = 1 << 15;
    if (param != "") {
      if constexpr (is_integral_v<EdgeTy>) {
        delta = stoull(param);
      } else {
        delta = stod(param);
      }
    }
    Delta_Stepping solver(G, bidirection, delta);
    run(solver, G, largest_cc, verify);
  } else if (algo == bellman_ford) {
    Bellman_Ford solver(G, bidirection);
    run(solver, G, largest_cc, verify);
  }
  return 0;
}