// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

#include <boost/test/minimal.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/page_rank.hpp>
#include <vector>
#include <iostream>
#include <stdlib.h>

using namespace boost;

bool close_to(double x, double y)
{
  double diff = x - y;
  if (diff < 0) diff = -diff;
  double base = (y == 0? x : y);
  if (base != 0) return diff / base < 0.01;
  else return true;
}

int test_main(int argc, char* argv[])
{
  using namespace boost::graph;

  int iterations = 20;
  if (argc > 1) {
    iterations = atoi(argv[1]);
  }

  std::cout << "Running " << iterations << " iterations\n";

  // create a typedef for the Graph type
  typedef adjacency_list<vecS, vecS, bidirectionalS,
                         /* vertex properties */ no_property,
                         /* edge properties */ property<edge_index_t, int>
                         > Graph;

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };

  // writing out the edges in the graph
  typedef std::pair<int, int> Edge;
  Edge edge_array[] =
    { Edge(A,B), Edge(A,C), Edge(B,C), Edge(C,A), Edge(D,C), Edge(C,E) };
  const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

  // declare a graph object
  Graph g;

  // add the edges to the graph object
  for (int i = 0; i < num_edges; ++i) {
    Graph::edge_descriptor e =
      add_edge(edge_array[i].first, edge_array[i].second, g).first;
    put(edge_index, g, e, i);
  }

  remove_dangling_links(g);

  std::vector<double> ranks(num_vertices(g));

  page_rank(g,
	    make_iterator_property_map(ranks.begin(),
				       get(boost::vertex_index, g)),
	    terminate = boost::graph::n_iterations(iterations));
  
  std::vector<double> ranks2(num_vertices(g));
  std::vector<double> ranks3(num_vertices(g));

  page_rank(g,
	    make_iterator_property_map(ranks2.begin(),
				       get(boost::vertex_index, g)),
	    rank_map2(make_iterator_property_map(ranks3.begin(),
						 get(boost::vertex_index, 
						     g))).
	    terminate(boost::graph::n_iterations(iterations)));

  double sum = 0.0;
  for(std::size_t i = 0; i < num_vertices(g); ++i) {
    std::cout << (char)('A' + i) << " = " << ranks[i] << std::endl;
    sum += ranks[i];
  }
  std::cout << "Sum = " << sum << "\n\n";

  BOOST_TEST(close_to(ranks[0], 0.400009));
  BOOST_TEST(close_to(ranks[1], 0.199993));
  BOOST_TEST(close_to(ranks[2], 0.399998));
  BOOST_TEST(close_to(ranks[3], 0));
  BOOST_TEST(close_to(sum, 1));
  BOOST_TEST(ranks == ranks2);

  return 0;
}