C++でページランクを実装

実験で使いそうなベースラインがページランク的なアルゴリズムだったので、Rubyの実装を適当にC++に翻訳してみただけ。超簡単なのでよい。

Rubyでもっとも重要なライブラリは何か？PageRankで計算してみた - aikeの日記

#include <map>
#include <cmath>

#include <iostream>
#include <vector>

typedef std::map<int, std::vector<int> > AdjacentMatrix;

class PageRank {
public:
  PageRank(AdjacentMatrix graph, int n, double damping = 0.85) {
	graph_ = graph;
	N_ = n;
	damping_ = damping;
	
	for (AdjacentMatrix::iterator it = graph_.begin(); it != graph_.end(); it++) {
// 	  std::cout << it->first << ": ";
// 	  for (std::vector<int>::iterator jit = it->second.begin(); jit != it->second.end(); jit++) {
// 		std::cout << *jit << " ";
// 	  }
	  std::cout << std::endl;
	  pagerank_[it->first] = 1.0 / N_;
	  temprank_[it->first] = 0.0;
	}

	for (int iter = 0; iter < 100; iter++) {
	  double change = 0.0;
	  double total = 0.0;

	  for (AdjacentMatrix::iterator it = graph_.begin(); it != graph_.end(); it++) {
		int node = it->first;
		std::vector<int> out_edges = it->second;
		int out = out_edges.size();
		for (std::vector<int>::iterator jit = out_edges.begin(); jit != out_edges.end(); jit++) {
		  temprank_[*jit] += pagerank_[node] / out;
		}
	  }

	  for (AdjacentMatrix::iterator it = graph_.begin(); it != graph_.end(); it++) {
		int node = it->first;
		temprank_[node] = (1.0 - damping_) / N_ + damping * temprank_[node];
		change += fabs(pagerank_[node] - temprank_[node]);
		pagerank_[node] = temprank_[node];
		temprank_[node] = 0.0;
		total += pagerank_[node];
	  }

	  for (AdjacentMatrix::iterator it = graph_.begin(); it != graph_.end(); it++) {
		int node = it->first;	  
		pagerank_[node] /= total;
	  }
	  std::cout << "Convergence: " << change << std::endl;
	}
	for (std::map<int, double>::iterator it = pagerank_.begin(); it != pagerank_.end(); it++) {
	  std::cout << it->first << "\t" << it->second << std::endl;
	}
  };
  
private:
  AdjacentMatrix graph_;
  std::map<int, double> pagerank_;
  std::map<int, double> temprank_;
  int N_;
  double damping_;
};

int main(int argc, char **argv) {
  AdjacentMatrix g;
  std::vector<int> v;
  
  v.push_back(3);
  v.push_back(4);
  g[1] = v;
  v.clear();

  v.push_back(3);
  v.push_back(4);
  g[2] = v;
  v.clear();

  v.push_back(1);
  v.push_back(2);
  g[3] = v;
  v.clear();

  v.push_back(2);
  v.push_back(3);
  g[4] = v;
  v.clear();

  PageRank(g, 4, 0.8);

  return 0;
}