PageRank.cpp

std::vector<double> PageRank(const std::vector<Page>& pages, const int K, const bool normalizable) {
  std::map<int, int> pid_conv;
  for(int i = 0; i < static_cast<int>(pages.size()); ++i) {
    pid_conv[pages[i].id()] = i;
  }

  std::vector<double> importances(pages.size(), 1.0);

  for(int k = 0; k < K; ++k) {
    std::vector<double> sums(pages.size(), 0.0);
    for(int i = 0; i < static_cast<int>(pages.size()); ++i) {
      int num_links = pages[i].links().size();
      for(int to_pid : pages[i].links()) {
	      sums[pid_conv[to_pid]] += importances[i]/num_links;
      }
    }
    for(int i = 0; i < static_cast<int>(pages.size()); ++i) {
      importances[i] = 0.15 + 0.85*sums[i];
    }
  }

  if(normalizable) {
    double max_importance = *std::max_element(importances.begin(), importances.end());
    for(int i = 0; i < static_cast<int>(pages.size()); ++i) {
      importances[i] /= max_importance;
    }
  }

  return importances;
}