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

  Program:   Visualization Toolkit
  Module:    vtkBoostGraphAdapter.h

  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.
-------------------------------------------------------------------------*/
/**
 * @class   vtkDirectedGraph
 *
 *
 * Including this header allows you to use a vtkDirectedGraph* in boost algorithms.
 * To do this, first wrap the class in a vtkDirectedGraph* or
 * vtkUndirectedGraph* depending on whether your graph is directed or undirected.
 * You may then use these objects directly in boost graph algorithms.
 */

#ifndef vtkBoostGraphAdapter_h
#define vtkBoostGraphAdapter_h

#include "vtkAbstractArray.h"
#include "vtkDataArray.h"
#include "vtkDataObject.h"
#include "vtkDirectedGraph.h"
#include "vtkDistributedGraphHelper.h"
#include "vtkDoubleArray.h"
#include "vtkFloatArray.h"
#include "vtkIdTypeArray.h"
#include "vtkInformation.h"
#include "vtkIntArray.h"
#include "vtkMutableDirectedGraph.h"
#include "vtkMutableUndirectedGraph.h"
#include "vtkTree.h"
#include "vtkUndirectedGraph.h"
#include "vtkVariant.h"

#include <boost/version.hpp>

namespace boost
{
//===========================================================================
// VTK arrays as property maps
// These need to be defined before including other boost stuff

// Forward declarations are required here, so that we aren't forced
// to include boost/property_map.hpp.
template <typename>
struct property_traits;
struct read_write_property_map_tag;

#define vtkPropertyMapMacro(T, V)                                                                  \
  template <>                                                                                      \
  struct property_traits<T*>                                                                       \
  {                                                                                                \
    typedef V value_type;                                                                          \
    typedef V reference;                                                                           \
    typedef vtkIdType key_type;                                                                    \
    typedef read_write_property_map_tag category;                                                  \
  };                                                                                               \
                                                                                                   \
  inline property_traits<T*>::reference get(T* const& arr, property_traits<T*>::key_type key)      \
  {                                                                                                \
    return arr->GetValue(key);                                                                     \
  }                                                                                                \
                                                                                                   \
  inline void put(                                                                                 \
    T* arr, property_traits<T*>::key_type key, const property_traits<T*>::value_type& value)       \
  {                                                                                                \
    arr->InsertValue(key, value);                                                                  \
  }

vtkPropertyMapMacro(vtkIntArray, int);
vtkPropertyMapMacro(vtkIdTypeArray, vtkIdType);
vtkPropertyMapMacro(vtkDoubleArray, double);
vtkPropertyMapMacro(vtkFloatArray, float);

// vtkDataArray
template <>
struct property_traits<vtkDataArray*>
{
  typedef double value_type;
  typedef double reference;
  typedef vtkIdType key_type;
  typedef read_write_property_map_tag category;
};

inline double get(vtkDataArray* const& arr, vtkIdType key)
{
  return arr->GetTuple1(key);
}

inline void put(vtkDataArray* arr, vtkIdType key, const double& value)
{
  arr->SetTuple1(key, value);
}

// vtkAbstractArray as a property map of vtkVariants
template <>
struct property_traits<vtkAbstractArray*>
{
  typedef vtkVariant value_type;
  typedef vtkVariant reference;
  typedef vtkIdType key_type;
  typedef read_write_property_map_tag category;
};

inline vtkVariant get(vtkAbstractArray* const& arr, vtkIdType key)
{
  return arr->GetVariantValue(key);
}

inline void put(vtkAbstractArray* arr, vtkIdType key, const vtkVariant& value)
{
  arr->InsertVariantValue(key, value);
}
#if defined(_MSC_VER)
namespace detail
{
using ::boost::get;
using ::boost::put;
}
#endif
}

#include <utility> // STL Header

#include <boost/config.hpp>
#include <boost/version.hpp>

#if BOOST_VERSION > 107300 && BOOST_VERSION < 107600
#define BOOST_ALLOW_DEPRECATED_HEADERS
#define BOOST_BIND_GLOBAL_PLACEHOLDERS
#endif

#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/iterator/iterator_facade.hpp>

// The functions and classes in this file allows the user to
// treat a vtkDirectedGraph or vtkUndirectedGraph object
// as a boost graph "as is".

namespace boost
{

class vtk_vertex_iterator
  : public iterator_facade<vtk_vertex_iterator, vtkIdType, bidirectional_traversal_tag,
      const vtkIdType&, vtkIdType>
{
public:
  explicit vtk_vertex_iterator(vtkIdType i = 0)
    : index(i)
  {
  }

private:
  const vtkIdType& dereference() const { return index; }

  bool equal(const vtk_vertex_iterator& other) const { return index == other.index; }

  void increment() { index++; }
  void decrement() { index--; }

  vtkIdType index;

  friend class iterator_core_access;
};

class vtk_edge_iterator
  : public iterator_facade<vtk_edge_iterator, vtkEdgeType, forward_traversal_tag,
      const vtkEdgeType&, vtkIdType>
{
public:
  explicit vtk_edge_iterator(vtkGraph* g = 0, vtkIdType v = 0)
    : directed(false)
    , vertex(v)
    , lastVertex(v)
    , iter(nullptr)
    , end(nullptr)
    , graph(g)
  {
    if (graph)
    {
      lastVertex = graph->GetNumberOfVertices();
    }

    vtkIdType myRank = -1;
    vtkDistributedGraphHelper* helper = this->graph ? this->graph->GetDistributedGraphHelper() : 0;
    if (helper)
    {
      myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER());
      vertex = helper->MakeDistributedId(myRank, vertex);
      lastVertex = helper->MakeDistributedId(myRank, lastVertex);
    }

    if (graph != 0)
    {
      directed = (vtkDirectedGraph::SafeDownCast(graph) != 0);
      while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0)
      {
        ++vertex;
      }

      if (vertex < lastVertex)
      {
        // Get the outgoing edges of the first vertex that has outgoing
        // edges
        vtkIdType nedges;
        graph->GetOutEdges(vertex, iter, nedges);
        if (iter)
        {
          end = iter + nedges;

          if (!directed)
          {
            while ( // Skip non-local edges
              (helper && helper->GetEdgeOwner(iter->Id) != myRank)
              // Skip entirely-local edges where Source > Target
              || (((helper && myRank == helper->GetVertexOwner(iter->Target)) || !helper) &&
                   vertex > iter->Target))
            {
              this->inc();
            }
          }
        }
      }
      else
      {
        iter = nullptr;
      }
    }

    RecalculateEdge();
  }

private:
  const vtkEdgeType& dereference() const
  {
    assert(iter);
    return edge;
  }

  bool equal(const vtk_edge_iterator& other) const
  {
    return vertex == other.vertex && iter == other.iter;
  }

  void increment()
  {
    inc();
    if (!directed)
    {
      vtkIdType myRank = -1;
      vtkDistributedGraphHelper* helper =
        this->graph ? this->graph->GetDistributedGraphHelper() : 0;
      if (helper)
      {
        myRank = this->graph->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER());
      }

      while (iter != 0 &&
        ( // Skip non-local edges
          (helper && helper->GetEdgeOwner(iter->Id) != myRank)
          // Skip entirely-local edges where Source > Target
          || (((helper && myRank == helper->GetVertexOwner(iter->Target)) || !helper) &&
               vertex > iter->Target)))
      {
        inc();
      }
    }
    RecalculateEdge();
  }

  void inc()
  {
    ++iter;
    if (iter == end)
    {
      // Find a vertex with nonzero out degree.
      ++vertex;
      while (vertex < lastVertex && this->graph->GetOutDegree(vertex) == 0)
      {
        ++vertex;
      }

      if (vertex < lastVertex)
      {
        vtkIdType nedges;
        graph->GetOutEdges(vertex, iter, nedges);
        end = iter + nedges;
      }
      else
      {
        iter = nullptr;
      }
    }
  }

  void RecalculateEdge()
  {
    if (iter)
    {
      edge = vtkEdgeType(vertex, iter->Target, iter->Id);
    }
  }

  bool directed;
  vtkIdType vertex;
  vtkIdType lastVertex;
  const vtkOutEdgeType* iter;
  const vtkOutEdgeType* end;
  vtkGraph* graph;
  vtkEdgeType edge;

  friend class iterator_core_access;
};

class vtk_out_edge_pointer_iterator
  : public iterator_facade<vtk_out_edge_pointer_iterator, vtkEdgeType, bidirectional_traversal_tag,
      const vtkEdgeType&, ptrdiff_t>
{
public:
  explicit vtk_out_edge_pointer_iterator(vtkGraph* g = 0, vtkIdType v = 0, bool end = false)
    : vertex(v)
    , iter(nullptr)
  {
    if (g)
    {
      vtkIdType nedges;
      g->GetOutEdges(vertex, iter, nedges);
      if (end)
      {
        iter += nedges;
      }
    }
    RecalculateEdge();
  }

private:
  const vtkEdgeType& dereference() const
  {
    assert(iter);
    return edge;
  }

  bool equal(const vtk_out_edge_pointer_iterator& other) const { return iter == other.iter; }

  void increment()
  {
    iter++;
    RecalculateEdge();
  }

  void decrement()
  {
    iter--;
    RecalculateEdge();
  }

  void RecalculateEdge()
  {
    if (iter)
    {
      edge = vtkEdgeType(vertex, iter->Target, iter->Id);
    }
  }

  vtkIdType vertex;
  const vtkOutEdgeType* iter;
  vtkEdgeType edge;

  friend class iterator_core_access;
};

class vtk_in_edge_pointer_iterator
  : public iterator_facade<vtk_in_edge_pointer_iterator, vtkEdgeType, bidirectional_traversal_tag,
      const vtkEdgeType&, ptrdiff_t>
{
public:
  explicit vtk_in_edge_pointer_iterator(vtkGraph* g = 0, vtkIdType v = 0, bool end = false)
    : vertex(v)
    , iter(nullptr)
  {
    if (g)
    {
      vtkIdType nedges;
      g->GetInEdges(vertex, iter, nedges);
      if (end)
      {
        iter += nedges;
      }
    }
    RecalculateEdge();
  }

private:
  const vtkEdgeType& dereference() const
  {
    assert(iter);
    return edge;
  }

  bool equal(const vtk_in_edge_pointer_iterator& other) const { return iter == other.iter; }

  void increment()
  {
    iter++;
    RecalculateEdge();
  }

  void decrement()
  {
    iter--;
    RecalculateEdge();
  }

  void RecalculateEdge()
  {
    if (iter)
    {
      edge = vtkEdgeType(iter->Source, vertex, iter->Id);
    }
  }

  vtkIdType vertex;
  const vtkInEdgeType* iter;
  vtkEdgeType edge;

  friend class iterator_core_access;
};

//===========================================================================
// vtkGraph
// VertexAndEdgeListGraphConcept
// BidirectionalGraphConcept
// AdjacencyGraphConcept

struct vtkGraph_traversal_category
  : public virtual bidirectional_graph_tag
  , public virtual edge_list_graph_tag
  , public virtual vertex_list_graph_tag
  , public virtual adjacency_graph_tag
{
};

template <>
struct graph_traits<vtkGraph*>
{
  typedef vtkIdType vertex_descriptor;
  static vertex_descriptor null_vertex() { return -1; }
  typedef vtkEdgeType edge_descriptor;
  static edge_descriptor null_edge() { return vtkEdgeType(-1, -1, -1); }
  typedef vtk_out_edge_pointer_iterator out_edge_iterator;
  typedef vtk_in_edge_pointer_iterator in_edge_iterator;

  typedef vtk_vertex_iterator vertex_iterator;
  typedef vtk_edge_iterator edge_iterator;

  typedef allow_parallel_edge_tag edge_parallel_category;
  typedef vtkGraph_traversal_category traversal_category;
  typedef vtkIdType vertices_size_type;
  typedef vtkIdType edges_size_type;
  typedef vtkIdType degree_size_type;

  typedef adjacency_iterator_generator<vtkGraph*, vertex_descriptor, out_edge_iterator>::type
    adjacency_iterator;
};

#if BOOST_VERSION >= 104500
template <>
struct graph_property_type<vtkGraph*>
{
  typedef no_property type;
};
#endif

template <>
struct vertex_property_type<vtkGraph*>
{
  typedef no_property type;
};

template <>
struct edge_property_type<vtkGraph*>
{
  typedef no_property type;
};

#if BOOST_VERSION >= 104500
template <>
struct graph_bundle_type<vtkGraph*>
{
  typedef no_property type;
};
#endif

template <>
struct vertex_bundle_type<vtkGraph*>
{
  typedef no_property type;
};

template <>
struct edge_bundle_type<vtkGraph*>
{
  typedef no_property type;
};

inline bool has_no_edges(vtkGraph* g)
{
  return ((g->GetNumberOfEdges() > 0) ? false : true);
}

inline void remove_edge(graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph* g)
{
  if (vtkMutableDirectedGraph::SafeDownCast(g))
  {
    vtkMutableDirectedGraph::SafeDownCast(g)->RemoveEdge(e.Id);
  }
  else if (vtkMutableUndirectedGraph::SafeDownCast(g))
  {
    vtkMutableUndirectedGraph::SafeDownCast(g)->RemoveEdge(e.Id);
  }
}

//===========================================================================
// vtkDirectedGraph

template <>
struct graph_traits<vtkDirectedGraph*> : graph_traits<vtkGraph*>
{
  typedef directed_tag directed_category;
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<const vtkDirectedGraph*> : graph_traits<vtkDirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<vtkDirectedGraph* const> : graph_traits<vtkDirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_property_type<vtkDirectedGraph*> : graph_property_type<vtkGraph*>
{
};

// Internal graph properties
template <>
struct graph_property_type<vtkDirectedGraph* const> : graph_property_type<vtkGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_property_type<vtkDirectedGraph*> : vertex_property_type<vtkGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_property_type<vtkDirectedGraph* const> : vertex_property_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkDirectedGraph*> : edge_property_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkDirectedGraph* const> : edge_property_type<vtkGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_bundle_type<vtkDirectedGraph*> : graph_bundle_type<vtkGraph*>
{
};

// Internal graph properties
template <>
struct graph_bundle_type<vtkDirectedGraph* const> : graph_bundle_type<vtkGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkDirectedGraph*> : vertex_bundle_type<vtkGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkDirectedGraph* const> : vertex_bundle_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkDirectedGraph*> : edge_bundle_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkDirectedGraph* const> : edge_bundle_type<vtkGraph*>
{
};

//===========================================================================
// vtkTree

template <>
struct graph_traits<vtkTree*> : graph_traits<vtkDirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<const vtkTree*> : graph_traits<vtkTree*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<vtkTree* const> : graph_traits<vtkTree*>
{
};

//===========================================================================
// vtkUndirectedGraph
template <>
struct graph_traits<vtkUndirectedGraph*> : graph_traits<vtkGraph*>
{
  typedef undirected_tag directed_category;
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<const vtkUndirectedGraph*> : graph_traits<vtkUndirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<vtkUndirectedGraph* const> : graph_traits<vtkUndirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_property_type<vtkUndirectedGraph*> : graph_property_type<vtkGraph*>
{
};

// Internal graph properties
template <>
struct graph_property_type<vtkUndirectedGraph* const> : graph_property_type<vtkGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_property_type<vtkUndirectedGraph*> : vertex_property_type<vtkGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_property_type<vtkUndirectedGraph* const> : vertex_property_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkUndirectedGraph*> : edge_property_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkUndirectedGraph* const> : edge_property_type<vtkGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_bundle_type<vtkUndirectedGraph*> : graph_bundle_type<vtkGraph*>
{
};

// Internal graph properties
template <>
struct graph_bundle_type<vtkUndirectedGraph* const> : graph_bundle_type<vtkGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkUndirectedGraph*> : vertex_bundle_type<vtkGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkUndirectedGraph* const> : vertex_bundle_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkUndirectedGraph*> : edge_bundle_type<vtkGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkUndirectedGraph* const> : edge_bundle_type<vtkGraph*>
{
};

//===========================================================================
// vtkMutableDirectedGraph

template <>
struct graph_traits<vtkMutableDirectedGraph*> : graph_traits<vtkDirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<const vtkMutableDirectedGraph*> : graph_traits<vtkMutableDirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<vtkMutableDirectedGraph* const> : graph_traits<vtkMutableDirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_property_type<vtkMutableDirectedGraph*> : graph_property_type<vtkDirectedGraph*>
{
};

// Internal graph properties
template <>
struct graph_property_type<vtkMutableDirectedGraph* const> : graph_property_type<vtkDirectedGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_property_type<vtkMutableDirectedGraph*> : vertex_property_type<vtkDirectedGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_property_type<vtkMutableDirectedGraph* const>
  : vertex_property_type<vtkDirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkMutableDirectedGraph*> : edge_property_type<vtkDirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkMutableDirectedGraph* const> : edge_property_type<vtkDirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_bundle_type<vtkMutableDirectedGraph*> : graph_bundle_type<vtkDirectedGraph*>
{
};

// Internal graph properties
template <>
struct graph_bundle_type<vtkMutableDirectedGraph* const> : graph_bundle_type<vtkDirectedGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkMutableDirectedGraph*> : vertex_bundle_type<vtkDirectedGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkMutableDirectedGraph* const> : vertex_bundle_type<vtkDirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkMutableDirectedGraph*> : edge_bundle_type<vtkDirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkMutableDirectedGraph* const> : edge_bundle_type<vtkDirectedGraph*>
{
};

//===========================================================================
// vtkMutableUndirectedGraph

template <>
struct graph_traits<vtkMutableUndirectedGraph*> : graph_traits<vtkUndirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<const vtkMutableUndirectedGraph*> : graph_traits<vtkMutableUndirectedGraph*>
{
};

// The graph_traits for a const graph are the same as a non-const graph.
template <>
struct graph_traits<vtkMutableUndirectedGraph* const> : graph_traits<vtkMutableUndirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_property_type<vtkMutableUndirectedGraph*> : graph_property_type<vtkUndirectedGraph*>
{
};

// Internal graph properties
template <>
struct graph_property_type<vtkMutableUndirectedGraph* const>
  : graph_property_type<vtkUndirectedGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_property_type<vtkMutableUndirectedGraph*> : vertex_property_type<vtkUndirectedGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_property_type<vtkMutableUndirectedGraph* const>
  : vertex_property_type<vtkUndirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkMutableUndirectedGraph*> : edge_property_type<vtkUndirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_property_type<vtkMutableUndirectedGraph* const>
  : edge_property_type<vtkUndirectedGraph*>
{
};

#if BOOST_VERSION >= 104500
// Internal graph properties
template <>
struct graph_bundle_type<vtkMutableUndirectedGraph*> : graph_bundle_type<vtkUndirectedGraph*>
{
};

// Internal graph properties
template <>
struct graph_bundle_type<vtkMutableUndirectedGraph* const> : graph_bundle_type<vtkUndirectedGraph*>
{
};
#endif

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkMutableUndirectedGraph*> : vertex_bundle_type<vtkUndirectedGraph*>
{
};

// Internal vertex properties
template <>
struct vertex_bundle_type<vtkMutableUndirectedGraph* const>
  : vertex_bundle_type<vtkUndirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkMutableUndirectedGraph*> : edge_bundle_type<vtkUndirectedGraph*>
{
};

// Internal edge properties
template <>
struct edge_bundle_type<vtkMutableUndirectedGraph* const> : edge_bundle_type<vtkUndirectedGraph*>
{
};

//===========================================================================
// API implementation
template <>
class vertex_property<vtkGraph*>
{
public:
  typedef vtkIdType type;
};

template <>
class edge_property<vtkGraph*>
{
public:
  typedef vtkIdType type;
};
} // end namespace boost

inline boost::graph_traits<vtkGraph*>::vertex_descriptor source(
  boost::graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph*)
{
  return e.Source;
}

inline boost::graph_traits<vtkGraph*>::vertex_descriptor target(
  boost::graph_traits<vtkGraph*>::edge_descriptor e, vtkGraph*)
{
  return e.Target;
}

inline std::pair<boost::graph_traits<vtkGraph*>::vertex_iterator,
  boost::graph_traits<vtkGraph*>::vertex_iterator>
vertices(vtkGraph* g)
{
  typedef boost::graph_traits<vtkGraph*>::vertex_iterator Iter;
  vtkIdType start = 0;
  if (vtkDistributedGraphHelper* helper = g->GetDistributedGraphHelper())
  {
    int rank = g->GetInformation()->Get(vtkDataObject::DATA_PIECE_NUMBER());
    start = helper->MakeDistributedId(rank, start);
  }

  return std::make_pair(Iter(start), Iter(start + g->GetNumberOfVertices()));
}

inline std::pair<boost::graph_traits<vtkGraph*>::edge_iterator,
  boost::graph_traits<vtkGraph*>::edge_iterator>
edges(vtkGraph* g)
{
  typedef boost::graph_traits<vtkGraph*>::edge_iterator Iter;
  return std::make_pair(Iter(g), Iter(g, g->GetNumberOfVertices()));
}

inline std::pair<boost::graph_traits<vtkGraph*>::out_edge_iterator,
  boost::graph_traits<vtkGraph*>::out_edge_iterator>
out_edges(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
{
  typedef boost::graph_traits<vtkGraph*>::out_edge_iterator Iter;
  std::pair<Iter, Iter> p = std::make_pair(Iter(g, u), Iter(g, u, true));
  return p;
}

inline std::pair<boost::graph_traits<vtkGraph*>::in_edge_iterator,
  boost::graph_traits<vtkGraph*>::in_edge_iterator>
in_edges(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
{
  typedef boost::graph_traits<vtkGraph*>::in_edge_iterator Iter;
  std::pair<Iter, Iter> p = std::make_pair(Iter(g, u), Iter(g, u, true));
  return p;
}

inline std::pair<boost::graph_traits<vtkGraph*>::adjacency_iterator,
  boost::graph_traits<vtkGraph*>::adjacency_iterator>
adjacent_vertices(boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
{
  typedef boost::graph_traits<vtkGraph*>::adjacency_iterator Iter;
  typedef boost::graph_traits<vtkGraph*>::out_edge_iterator OutEdgeIter;
  std::pair<OutEdgeIter, OutEdgeIter> out = out_edges(u, g);
  return std::make_pair(Iter(out.first, &g), Iter(out.second, &g));
}

inline boost::graph_traits<vtkGraph*>::vertices_size_type num_vertices(vtkGraph* g)
{
  return g->GetNumberOfVertices();
}

inline boost::graph_traits<vtkGraph*>::edges_size_type num_edges(vtkGraph* g)
{
  return g->GetNumberOfEdges();
}

inline boost::graph_traits<vtkGraph*>::degree_size_type out_degree(
  boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
{
  return g->GetOutDegree(u);
}

inline boost::graph_traits<vtkDirectedGraph*>::degree_size_type in_degree(
  boost::graph_traits<vtkDirectedGraph*>::vertex_descriptor u, vtkDirectedGraph* g)
{
  return g->GetInDegree(u);
}

inline boost::graph_traits<vtkGraph*>::degree_size_type degree(
  boost::graph_traits<vtkGraph*>::vertex_descriptor u, vtkGraph* g)
{
  return g->GetDegree(u);
}

inline boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor add_vertex(
  vtkMutableDirectedGraph* g)
{
  return g->AddVertex();
}

inline std::pair<boost::graph_traits<vtkMutableDirectedGraph*>::edge_descriptor, bool> add_edge(
  boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor u,
  boost::graph_traits<vtkMutableDirectedGraph*>::vertex_descriptor v, vtkMutableDirectedGraph* g)
{
  boost::graph_traits<vtkMutableDirectedGraph*>::edge_descriptor e = g->AddEdge(u, v);
  return std::make_pair(e, true);
}

inline boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor add_vertex(
  vtkMutableUndirectedGraph* g)
{
  return g->AddVertex();
}

inline std::pair<boost::graph_traits<vtkMutableUndirectedGraph*>::edge_descriptor, bool> add_edge(
  boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor u,
  boost::graph_traits<vtkMutableUndirectedGraph*>::vertex_descriptor v,
  vtkMutableUndirectedGraph* g)
{
  boost::graph_traits<vtkMutableUndirectedGraph*>::edge_descriptor e = g->AddEdge(u, v);
  return std::make_pair(e, true);
}

namespace boost
{
//===========================================================================
// An edge map for vtkGraph.
// This is a common input needed for algorithms.

struct vtkGraphEdgeMap
{
};

template <>
struct property_traits<vtkGraphEdgeMap>
{
  typedef vtkIdType value_type;
  typedef vtkIdType reference;
  typedef vtkEdgeType key_type;
  typedef readable_property_map_tag category;
};

inline property_traits<vtkGraphEdgeMap>::reference get(
  vtkGraphEdgeMap vtkNotUsed(arr), property_traits<vtkGraphEdgeMap>::key_type key)
{
  return key.Id;
}

//===========================================================================
// Helper for vtkGraph edge property maps
// Automatically converts boost edge ids to vtkGraph edge ids.

template <typename PMap>
class vtkGraphEdgePropertyMapHelper
{
public:
  vtkGraphEdgePropertyMapHelper(PMap m)
    : pmap(m)
  {
  }
  PMap pmap;
  typedef typename property_traits<PMap>::value_type value_type;
  typedef typename property_traits<PMap>::reference reference;
  typedef vtkEdgeType key_type;
  typedef typename property_traits<PMap>::category category;

  reference operator[](const key_type& key) const { return get(pmap, key.Id); }
};

template <typename PMap>
inline typename property_traits<PMap>::reference get(
  vtkGraphEdgePropertyMapHelper<PMap> helper, vtkEdgeType key)
{
  return get(helper.pmap, key.Id);
}

template <typename PMap>
inline void put(vtkGraphEdgePropertyMapHelper<PMap> helper, vtkEdgeType key,
  const typename property_traits<PMap>::value_type& value)
{
  put(helper.pmap, key.Id, value);
}

//===========================================================================
// Helper for vtkGraph vertex property maps
// Automatically converts boost vertex ids to vtkGraph vertex ids.

template <typename PMap>
class vtkGraphVertexPropertyMapHelper
{
public:
  vtkGraphVertexPropertyMapHelper(PMap m)
    : pmap(m)
  {
  }
  PMap pmap;
  typedef typename property_traits<PMap>::value_type value_type;
  typedef typename property_traits<PMap>::reference reference;
  typedef vtkIdType key_type;
  typedef typename property_traits<PMap>::category category;

  reference operator[](const key_type& key) const { return get(pmap, key); }
};

template <typename PMap>
inline typename property_traits<PMap>::reference get(
  vtkGraphVertexPropertyMapHelper<PMap> helper, vtkIdType key)
{
  return get(helper.pmap, key);
}

template <typename PMap>
inline void put(vtkGraphVertexPropertyMapHelper<PMap> helper, vtkIdType key,
  const typename property_traits<PMap>::value_type& value)
{
  put(helper.pmap, key, value);
}

//===========================================================================
// An index map for vtkGraph
// This is a common input needed for algorithms

struct vtkGraphIndexMap
{
};

template <>
struct property_traits<vtkGraphIndexMap>
{
  typedef vtkIdType value_type;
  typedef vtkIdType reference;
  typedef vtkIdType key_type;
  typedef readable_property_map_tag category;
};

inline property_traits<vtkGraphIndexMap>::reference get(
  vtkGraphIndexMap vtkNotUsed(arr), property_traits<vtkGraphIndexMap>::key_type key)
{
  return key;
}

//===========================================================================
// Helper for vtkGraph property maps
// Automatically multiplies the property value by some value (default 1)
template <typename PMap>
class vtkGraphPropertyMapMultiplier
{
public:
  vtkGraphPropertyMapMultiplier(PMap m, float multi = 1)
    : pmap(m)
    , multiplier(multi)
  {
  }
  PMap pmap;
  float multiplier;
  typedef typename property_traits<PMap>::value_type value_type;
  typedef typename property_traits<PMap>::reference reference;
  typedef typename property_traits<PMap>::key_type key_type;
  typedef typename property_traits<PMap>::category category;
};

template <typename PMap>
inline typename property_traits<PMap>::reference get(
  vtkGraphPropertyMapMultiplier<PMap> multi, const typename property_traits<PMap>::key_type& key)
{
  return multi.multiplier * get(multi.pmap, key);
}

template <typename PMap>
inline void put(vtkGraphPropertyMapMultiplier<PMap> multi,
  const typename property_traits<PMap>::key_type& key,
  const typename property_traits<PMap>::value_type& value)
{
  put(multi.pmap, key, value);
}

// Allow algorithms to automatically extract vtkGraphIndexMap from a
// VTK graph
template <>
struct property_map<vtkGraph*, vertex_index_t>
{
  typedef vtkGraphIndexMap type;
  typedef vtkGraphIndexMap const_type;
};

template <>
struct property_map<vtkDirectedGraph*, vertex_index_t> : property_map<vtkGraph*, vertex_index_t>
{
};

template <>
struct property_map<vtkUndirectedGraph*, vertex_index_t> : property_map<vtkGraph*, vertex_index_t>
{
};

inline vtkGraphIndexMap get(vertex_index_t, vtkGraph*)
{
  return vtkGraphIndexMap();
}

template <>
struct property_map<vtkGraph*, edge_index_t>
{
  typedef vtkGraphIndexMap type;
  typedef vtkGraphIndexMap const_type;
};

template <>
struct property_map<vtkDirectedGraph*, edge_index_t> : property_map<vtkGraph*, edge_index_t>
{
};

template <>
struct property_map<vtkUndirectedGraph*, edge_index_t> : property_map<vtkGraph*, edge_index_t>
{
};

inline vtkGraphIndexMap get(edge_index_t, vtkGraph*)
{
  return vtkGraphIndexMap();
}

// property_map specializations for const-qualified graphs
template <>
struct property_map<vtkDirectedGraph* const, vertex_index_t>
  : property_map<vtkDirectedGraph*, vertex_index_t>
{
};

template <>
struct property_map<vtkUndirectedGraph* const, vertex_index_t>
  : property_map<vtkUndirectedGraph*, vertex_index_t>
{
};

template <>
struct property_map<vtkDirectedGraph* const, edge_index_t>
  : property_map<vtkDirectedGraph*, edge_index_t>
{
};

template <>
struct property_map<vtkUndirectedGraph* const, edge_index_t>
  : property_map<vtkUndirectedGraph*, edge_index_t>
{
};
} // namespace boost

#if BOOST_VERSION > 104000
#include <boost/property_map/vector_property_map.hpp>
#else
#include <boost/vector_property_map.hpp>
#endif

#endif // vtkBoostGraphAdapter_h
// VTK-HeaderTest-Exclude: vtkBoostGraphAdapter.h