// 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

/*

 * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

*/

#include <boost/graph/fruchterman_reingold.hpp>

#include <boost/graph/random_layout.hpp>

#include <boost/graph/kamada_kawai_spring_layout.hpp>

#include <boost/graph/circle_layout.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/random/linear_congruential.hpp>

#include <boost/test/minimal.hpp>

#include <iostream>

#include <boost/limits.hpp>

#include <fstream>

#include <string>

#ifdef __SYMBIAN32__

#include "std_log_result.h"

#define LOG_FILENAME_LINE __FILE__, __LINE__

#endif

using namespace boost;

enum vertex_position_t { vertex_position };

namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }

struct point

{

  double x;

  double y;

};

template<typename Graph, typename PositionMap>

void print_graph_layout(const Graph& g, PositionMap position)

{

  typename graph_traits<Graph>::vertex_iterator vi, vi_end;

  int xmin = 0, xmax = 0, ymin = 0, ymax = 0;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {

    if ((int)position[*vi].x < xmin) xmin = (int)position[*vi].x;

    if ((int)position[*vi].x > xmax) xmax = (int)position[*vi].x;

    if ((int)position[*vi].y < ymin) ymin = (int)position[*vi].y;

    if ((int)position[*vi].y > ymax) ymax = (int)position[*vi].y;

  }

  for (int y = ymin; y <= ymax; ++y) {

    for (int x = xmin; x <= xmax; ++x) {

      // Find vertex at this position

      typename graph_traits<Graph>::vertices_size_type index = 0;

      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++index) {

        if ((int)position[*vi].x == x && (int)position[*vi].y == y)

          break;

      }

      if (vi == vi_end) std::cout << ' ';

      else std::cout << (char)(index + 'A');

    }

    std::cout << std::endl;

  }

}

template<typename Graph, typename PositionMap>

void dump_graph_layout(std::string name, const Graph& g, PositionMap position)

{

  std::ofstream out((name + ".dot").c_str());

  out << "graph " << name << " {" << std::endl;

  typename graph_traits<Graph>::vertex_iterator vi, vi_end;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {

    out << "  n" << get(vertex_index, g, *vi) << "[ pos=\"" 

        << (int)position[*vi].x + 25 << ", " << (int)position[*vi].y + 25 

        << "\" ];\n";

  }

  typename graph_traits<Graph>::edge_iterator ei, ei_end;

  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    out << "  n" << get(vertex_index, g, source(*ei, g)) << " -- n"

        << get(vertex_index, g, target(*ei, g)) << ";\n";

  }

  out << "}\n";

}

template<typename Graph>

void 

test_circle_layout(Graph*, typename graph_traits<Graph>::vertices_size_type n)

{

  typedef typename graph_traits<Graph>::vertex_descriptor vertex;

  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

  typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;

  typedef typename graph_traits<Graph>::edges_size_type edges_size_type;

  Graph g(n);

  // Initialize vertex indices

  vertex_iterator vi = vertices(g).first;

  for (vertices_size_type i = 0; i < n; ++i, ++vi) 

    put(vertex_index, g, *vi, i);

  circle_graph_layout(g, get(vertex_position, g), 10.0);

  std::cout << "Regular polygon layout with " << n << " points.\n";

  print_graph_layout(g, get(vertex_position, g));

}

struct simple_edge

{

  int first, second;

};

struct kamada_kawai_done 

{

  kamada_kawai_done() : last_delta() {}

  template<typename Graph>

  bool operator()(double delta_p, 

                  typename boost::graph_traits<Graph>::vertex_descriptor p,

                  const Graph& g,

                  bool global)

  {

    if (global) {

      double diff = last_delta - delta_p;

      if (diff < 0) diff = -diff;

      last_delta = delta_p;

      return diff < 0.01;

    } else {

      return delta_p < 0.01;

    }

  }

  double last_delta;

};

template<typename Graph>

void

test_triangle(Graph*)

{

  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

  Graph g;

  vertex_descriptor u = add_vertex(g); put(vertex_index, g, u, 0);

  vertex_descriptor v = add_vertex(g); put(vertex_index, g, v, 1);

  vertex_descriptor w = add_vertex(g); put(vertex_index, g, w, 2);

  edge_descriptor e1 = add_edge(u, v, g).first; put(edge_weight, g, e1, 1.0);

  edge_descriptor e2 = add_edge(v, w, g).first; put(edge_weight, g, e2, 1.0);

  edge_descriptor e3 = add_edge(w, u, g).first; put(edge_weight, g, e3, 1.0);

  circle_graph_layout(g, get(vertex_position, g), 25.0);

  bool ok = kamada_kawai_spring_layout(g, 

                                       get(vertex_position, g),

                                       get(edge_weight, g),

                                       side_length(50.0));

  BOOST_CHECK(ok);

  std::cout << "Triangle layout (Kamada-Kawai).\n";

  print_graph_layout(g, get(vertex_position, g));

}

template<typename Graph>

void

test_cube(Graph*)

{

  enum {A, B, C, D, E, F, G, H};

  simple_edge cube_edges[12] = {

    {A, E}, {A, B}, {A, D}, {B, F}, {B, C}, {C, D}, {C, G}, {D, H}, 

    {E, H}, {E, F}, {F, G}, {G, H}

  };

  Graph g(&cube_edges[0], &cube_edges[12], 8);

  typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

  vertex_iterator vi, vi_end;

  int i = 0;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

    put(vertex_index, g, *vi, i++);

  edge_iterator ei, ei_end;

  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    put(edge_weight, g, *ei, 1.0);

    std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') 

              << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

              << ") ";

  }

  std::cerr << std::endl;

  circle_graph_layout(g, get(vertex_position, g), 25.0);

  bool ok = kamada_kawai_spring_layout(g, 

                                       get(vertex_position, g),

                                       get(edge_weight, g),

                                       side_length(50.0),

                                       kamada_kawai_done());

  BOOST_CHECK(ok);

  std::cout << "Cube layout (Kamada-Kawai).\n";

  print_graph_layout(g, get(vertex_position, g));

  dump_graph_layout("cube", g, get(vertex_position, g));

  minstd_rand gen;

  random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0, 

                      gen);

  std::vector<point> displacements(num_vertices(g));

  fruchterman_reingold_force_directed_layout

    (g,

     get(vertex_position, g),

     50.0,

     50.0,

     square_distance_attractive_force(),

     square_distance_repulsive_force(),

     all_force_pairs(),

     linear_cooling<double>(100),

     make_iterator_property_map(displacements.begin(),

                                get(vertex_index, g),

                                point()));

  std::cout << "Cube layout (Fruchterman-Reingold).\n";

  print_graph_layout(g, get(vertex_position, g));

  dump_graph_layout("cube-fr", g, get(vertex_position, g));

}

template<typename Graph>

void

test_triangular(Graph*)

{

  enum {A, B, C, D, E, F, G, H, I, J};

  simple_edge triangular_edges[18] = {

    {A, B}, {A, C}, {B, C}, {B, D}, {B, E}, {C, E}, {C, F}, {D, E}, {D, G},

    {D, H}, {E, F}, {E, H}, {E, I}, {F, I}, {F, J}, {G, H}, {H, I}, {I, J}

  };

  Graph g(&triangular_edges[0], &triangular_edges[18], 10);

  typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

  vertex_iterator vi, vi_end;

  int i = 0;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

    put(vertex_index, g, *vi, i++);

  edge_iterator ei, ei_end;

  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    put(edge_weight, g, *ei, 1.0);

    std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') 

              << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

              << ") ";

  }

  std::cerr << std::endl;

  circle_graph_layout(g, get(vertex_position, g), 25.0);

  bool ok = kamada_kawai_spring_layout(g, 

                                       get(vertex_position, g),

                                       get(edge_weight, g),

                                       side_length(50.0),

                                       kamada_kawai_done());

  BOOST_CHECK(ok);

  std::cout << "Triangular layout (Kamada-Kawai).\n";

  print_graph_layout(g, get(vertex_position, g));

  dump_graph_layout("triangular-kk", g, get(vertex_position, g));

  minstd_rand gen;

  random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0, 

                      gen);

  dump_graph_layout("random", g, get(vertex_position, g));

  std::vector<point> displacements(num_vertices(g));

  fruchterman_reingold_force_directed_layout

    (g,

     get(vertex_position, g),

     50.0,

     50.0,

     attractive_force(square_distance_attractive_force()).

     cooling(linear_cooling<double>(100)));

  std::cout << "Triangular layout (Fruchterman-Reingold).\n";

  print_graph_layout(g, get(vertex_position, g));

  dump_graph_layout("triangular-fr", g, get(vertex_position, g));

}

template<typename Graph>

void

test_disconnected(Graph*)

{

  enum {A, B, C, D, E, F, G, H};

  simple_edge triangular_edges[13] = {

    {A, B}, {B, C}, {C, A}, 

    {D, E}, {E, F}, {F, G}, {G, H}, {H, D},

    {D, F}, {F, H}, {H, E}, {E, G}, {G, D}

  };

  Graph g(&triangular_edges[0], &triangular_edges[13], 8);

  typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

  vertex_iterator vi, vi_end;

  int i = 0;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

    put(vertex_index, g, *vi, i++);

  edge_iterator ei, ei_end;

  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    put(edge_weight, g, *ei, 1.0);

    std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') 

              << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

              << ") ";

  }

  std::cerr << std::endl;

  circle_graph_layout(g, get(vertex_position, g), 25.0);

  bool ok = kamada_kawai_spring_layout(g, 

                                       get(vertex_position, g),

                                       get(edge_weight, g),

                                       side_length(50.0),

                                       kamada_kawai_done());

  BOOST_CHECK(!ok);

  minstd_rand gen;

  random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0, 

                      gen);

  std::vector<point> displacements(num_vertices(g));

  fruchterman_reingold_force_directed_layout

    (g,

     get(vertex_position, g),

     50.0,

     50.0,

     attractive_force(square_distance_attractive_force()).

     cooling(linear_cooling<double>(50)));

  std::cout << "Disconnected layout (Fruchterman-Reingold).\n";

  print_graph_layout(g, get(vertex_position, g));

  dump_graph_layout("disconnected-fr", g, get(vertex_position, g));

}

int test_main(int, char*[])

{

  typedef adjacency_list<listS, listS, undirectedS, 

                         // Vertex properties

                         property<vertex_index_t, int,

                         property<vertex_position_t, point> >,

                         // Edge properties

                         property<edge_weight_t, double> > Graph;

  test_circle_layout((Graph*)0, 5);

  test_cube((Graph*)0);

  test_triangular((Graph*)0);

  test_disconnected((Graph*)0);

#ifdef __SYMBIAN32__

std_log(LOG_FILENAME_LINE,"[End Test Case ]");

	testResultXml("layout_test");

	close_log_file();

#endif

  return 0;

}