/*=========================================================================

  Program:   Visualization Toolkit
  Module:    TestBoostAdapter.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
/*-------------------------------------------------------------------------
  Copyright 2008 Sandia Corporation.
  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
  the U.S. Government retains certain rights in this software.
-------------------------------------------------------------------------*/

#include "vtkGraph.h"
#include "vtkBoostGraphAdapter.h"
#include "vtkIntArray.h"
#include "vtkIdTypeArray.h"
#include "vtkMath.h"
#include "vtkSmartPointer.h"
#include "vtkTimerLog.h"

#include <vtksys/stl/vector>
#include <vtksys/stl/map>
#include <vtksys/stl/utility>

// In Boost 1.34.1, boost/pending/relaxed_heap.hpp does not include <climits>
// but uses CHAR_BIT. gcc>=4.3 has stricter and cleaner header files
// and fails with this version of Boost.
#include <boost/version.hpp>
#if BOOST_VERSION < 103500
#include <climits> // defines CHAR_BIT
#endif

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/transitive_closure.hpp>

#define VTK_CREATE(type, name) \
  vtkSmartPointer<type> name = vtkSmartPointer<type>::New()

using namespace boost;
using namespace vtksys_stl;

template <typename Graph>
void TestTraversal(Graph g, int repeat, int& vtkNotUsed(errors))
{
  typedef typename graph_traits<Graph>::edge_descriptor Edge;
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  
  VTK_CREATE(vtkTimerLog, timer);
  typename graph_traits<Graph>::vertex_iterator vi, viEnd;

  // Traverse the edge list of each vertex
  timer->StartTimer();
  int count = 0;
  for (int r = 0; r < repeat; r++)
    {
    for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
      {
      typename graph_traits<Graph>::out_edge_iterator oi, oiEnd;
      tie(oi, oiEnd) = out_edges(*vi, g);
      count++;
      }
    }
  timer->StopTimer();
  double time_out_edges = timer->GetElapsedTime();
  cerr << "getting out edges: " << time_out_edges / count << " sec." << endl;

  Edge e = *(edges(g).first);
  Vertex v = *(vertices(g).first);
  vector<Edge> edge_vec;
  vector<Vertex> vert_vec;

  timer->StartTimer();
  count = 0;
  for (int r = 0; r < repeat; r++)
    {
    for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
      {
      typename graph_traits<Graph>::out_edge_iterator oi, oiEnd;
      for (tie(oi, oiEnd) = out_edges(*vi, g); oi != oiEnd; ++oi)
        {
        count++;
        }
      }
    }
  timer->StopTimer();
  double time_inc = timer->GetElapsedTime();
  cerr << "+increment: " << time_inc / count << " sec." << endl;
  cerr << "  just increment: " << (time_inc - time_out_edges) / count << " sec." << endl;

  timer->StartTimer();
  count = 0;
  for (int r = 0; r < repeat; r++)
    {
    edge_vec.clear();
    vert_vec.clear();
    for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
      {
      typename graph_traits<Graph>::out_edge_iterator oi, oiEnd;
      for (tie(oi, oiEnd) = out_edges(*vi, g); oi != oiEnd; ++oi)
        {
        edge_vec.push_back(e);
        vert_vec.push_back(v);
        count++;
        }
      }
    }
  timer->StopTimer();
  double time_push_back = timer->GetElapsedTime();
  cerr << "+push_back: " << time_push_back / count << " sec." << endl;
  cerr << "  just push_back: " << (time_push_back - time_inc) / count << " sec." << endl;

  timer->StartTimer();
  count = 0;
  for (int r = 0; r < repeat; r++)
    {
    edge_vec.clear();
    vert_vec.clear();
    for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
      {
      typename graph_traits<Graph>::out_edge_iterator oi, oiEnd;
      for (tie(oi, oiEnd) = out_edges(*vi, g); oi != oiEnd; ++oi)
        {
        Edge e1 = *oi;
        edge_vec.push_back(e1);
        vert_vec.push_back(v);
        count++;
        }
      }
    }
  timer->StopTimer();
  double time_deref = timer->GetElapsedTime();
  cerr << "+dereference: " << time_deref / count << " sec." << endl;
  cerr << "  just dereference: " << (time_deref - time_push_back) / count << " sec." << endl;

  timer->StartTimer();
  count = 0;
  for (int r = 0; r < repeat; r++)
    {
    edge_vec.clear();
    vert_vec.clear();
    for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
      {
      typename graph_traits<Graph>::out_edge_iterator oi, oiEnd;
      for (tie(oi, oiEnd) = out_edges(*vi, g); oi != oiEnd; ++oi)
        {
        Edge e1 = *oi;
        edge_vec.push_back(e1);
        Vertex v1 = target(e1, g);
        vert_vec.push_back(v1);
        count++;
        }
      }
    }
  timer->StopTimer();
  double time_target = timer->GetElapsedTime();
  cerr << "+target: " << time_target / count << " sec." << endl;
  cerr << "  just target: " << (time_target - time_deref) / count << " sec." << endl;
}

template <typename Graph>
void TestGraph(Graph g, vtkIdType numVertices, vtkIdType numEdges, int repeat, int& errors)
{
  typedef typename graph_traits<Graph>::edge_descriptor Edge;
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

  VTK_CREATE(vtkTimerLog, timer);
  
  vector<Vertex> graphVerts;
  vector<Edge> graphEdges;
  typename graph_traits<Graph>::vertex_iterator vi, viEnd;

  // Create a graph
  timer->StartTimer();
  for (int i = 0; i < numVertices; ++i)
    {
    add_vertex(g);
    }
  timer->StopTimer();
  cerr << "vertex insertion: " << timer->GetElapsedTime() / numVertices  << " sec." << endl;
  
  if (static_cast<int>(num_vertices(g)) != numVertices)
    {
    cerr << "ERROR: Number of vertices (" << num_vertices(g) 
         << ") not as expected (" << numVertices << ")." << endl;
    errors++;
    }

  for (tie(vi, viEnd) = vertices(g); vi != viEnd; ++vi)
    {
    graphVerts.push_back(*vi);
    }

  timer->StartTimer();
  for (int i = 0; i < numEdges; ++i)
    {
    int u = static_cast<int>(vtkMath::Random(0, numVertices));
    int v = static_cast<int>(vtkMath::Random(0, numVertices));
    add_edge(graphVerts[u], graphVerts[v], g);
    }
  timer->StopTimer();
  cerr << "edge insertion: " << timer->GetElapsedTime() / numEdges  << " sec." << endl;

  if (static_cast<int>(num_edges(g)) != numEdges)
    {
    cerr << "ERROR: Number of edges (" << num_edges(g) 
         << ") not as expected (" << numEdges << ")." << endl;
    errors++;
    }

  typename graph_traits<Graph>::edge_iterator ei, eiEnd;
  for (tie(ei, eiEnd) = edges(g); ei != eiEnd; ++ei)
    {
    graphEdges.push_back(*ei);
    }
  
  TestTraversal(g, repeat, errors);
  
#if 0
  timer->StartTimer();
  while (num_edges(g) > 0)
    {
    remove_edge(*(edges(g).first), g);
    }
  timer->StopTimer();
  cerr << "edge deletion: " << timer->GetElapsedTime() / numEdges  << " sec." << endl;

  // Perform edge deletions followed by accesses
  timer->StartTimer();
  while (num_vertices(g) > 0)
    {
    remove_vertex(*(vertices(g).first), g);
    }
  timer->StopTimer();
  cerr << "vertex deletion: " << timer->GetElapsedTime() / numVertices  << " sec." << endl;
#endif
}

int TestBoostAdapter(int vtkNotUsed(argc), char* vtkNotUsed(argv)[])
{
  int errors = 0;
  int repeat = 100;
  vtkIdType numVertices = 1000;
  vtkIdType numEdges = 2000;

  cerr << "Testing boost list graph..." << endl;
  typedef adjacency_list<listS, listS, directedS, property<vertex_index_t, unsigned int>, property<edge_index_t, unsigned int>, no_property, listS> ListGraph;
  ListGraph listGraph;
  TestGraph(listGraph, numVertices, numEdges, repeat, errors);
  cerr << "...done." << endl << endl;
  
  cerr << "Testing boost vector graph..." << endl;
  typedef adjacency_list<vecS, vecS, directedS, property<vertex_index_t, unsigned int>, property<edge_index_t, unsigned int>, no_property, vecS> VectorGraph;
  VectorGraph vectorGraph;
  TestGraph(vectorGraph, numVertices, numEdges, repeat, errors);
  cerr << "...done." << endl << endl;

  cerr << "Testing undirected graph adapter..." << endl;
  vtkMutableUndirectedGraph* ug = vtkMutableUndirectedGraph::New();
  TestGraph(ug, numVertices, numEdges, repeat, errors);
  ug->Delete();
  cerr << "...done." << endl << endl;

  cerr << "Testing directed graph adapter..." << endl;
  vtkMutableDirectedGraph* dg = vtkMutableDirectedGraph::New();
  TestGraph(dg, numVertices, numEdges, repeat, errors);
  dg->Delete();
  cerr << "...done." << endl << endl;
  
  cerr << "Testing tree adapter..." << endl;
  vtkMutableDirectedGraph *builder = vtkMutableDirectedGraph::New();
  builder->AddVertex();
  for (vtkIdType i = 1; i < numVertices; i++)
    {
    builder->AddChild(static_cast<vtkIdType>(vtkMath::Random(0, i)));
    }
  vtkTree* t = vtkTree::New();
  if (!t->CheckedShallowCopy(builder))
    {
    cerr << "Invalid tree structure!" << endl;
    ++errors;
    }
  TestTraversal(t, repeat, errors);
  builder->Delete();
  t->Delete();
  cerr << "...done." << endl << endl;
  
  return errors;
}