//=======================================================================

// Copyright 2001 University of Notre Dame.

// Copyright 2006 Trustees of Indiana University

// Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu>

//

// Distributed under 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)

//=======================================================================

#ifndef BOOST_ADJACENCY_MATRIX_HPP

#define BOOST_ADJACENCY_MATRIX_HPP

#include <boost/config.hpp>

#include <vector>

#include <memory>

#include <cassert>

#include <boost/limits.hpp>

#include <boost/iterator.hpp>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/graph_selectors.hpp>

#include <boost/pending/ct_if.hpp>

#include <boost/graph/adjacency_iterator.hpp>

#include <boost/graph/detail/edge.hpp>

#include <boost/iterator/iterator_adaptor.hpp>

#include <boost/iterator/filter_iterator.hpp>

#include <boost/pending/integer_range.hpp>

#include <boost/graph/properties.hpp>

#include <boost/tuple/tuple.hpp>

#include <boost/static_assert.hpp>

#include <boost/type_traits/ice.hpp>

namespace boost {

  namespace detail {

    template <class Directed, class Vertex>

    class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>

    {

      typedef edge_desc_impl<Directed,Vertex> Base;

    public:

      matrix_edge_desc_impl() { }

      matrix_edge_desc_impl(bool exists, Vertex s, Vertex d, 

                            const void* ep = 0)

        : Base(s, d, ep), m_exists(exists) { }

      bool exists() const { return m_exists; }

    private:

      bool m_exists;

    };

    struct does_edge_exist {

      template <class Edge>

      bool operator()(const Edge& e) const { return e.exists(); }

    };

    template <typename EdgeProperty>

    bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {

      return stored_edge.first;

    }

    template <typename EdgeProperty>

    void set_edge_exists(

        std::pair<bool, EdgeProperty>& stored_edge, 

        bool flag,

        int

        ) {

      stored_edge.first = flag;

    }

    template <typename EdgeProxy>

    bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {

      return edge_proxy;

    }

    template <typename EdgeProxy>

    EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {

      edge_proxy = flag;

      return edge_proxy; // just to avoid never used warning

    }

    template <typename EdgeProperty>

    const EdgeProperty&

    get_property(const std::pair<bool, EdgeProperty>& stored_edge) {

      return stored_edge.second;

    }

    template <typename EdgeProperty>

    EdgeProperty&

    get_property(std::pair<bool, EdgeProperty>& stored_edge) {

      return stored_edge.second;

    }

    template <typename StoredEdgeProperty, typename EdgeProperty>

    inline void

    set_property(std::pair<bool, StoredEdgeProperty>& stored_edge, 

                 const EdgeProperty& ep, int) {

      stored_edge.second = ep;

    }

    inline const no_property& get_property(const char&) {

      static no_property s_prop;

      return s_prop;

    }

    inline no_property& get_property(char&) {

      static no_property s_prop;

      return s_prop;

    }

    template <typename EdgeProxy, typename EdgeProperty>

    inline void

    set_property(EdgeProxy, const EdgeProperty&, ...) {}

    //=======================================================================

    // Directed Out Edge Iterator

    template <

        typename VertexDescriptor, typename MatrixIter

      , typename VerticesSizeType, typename EdgeDescriptor

    >

    struct dir_adj_matrix_out_edge_iter

      : iterator_adaptor<

            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        >

    {

        typedef iterator_adaptor<

            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        > super_t;

        dir_adj_matrix_out_edge_iter() { }

        dir_adj_matrix_out_edge_iter(

            const MatrixIter& i

          , const VertexDescriptor& src

          , const VerticesSizeType& n

           )

            : super_t(i), m_src(src), m_targ(0), m_n(n)

        { }

        void increment() {

            ++this->base_reference();

            ++m_targ;

        }

        inline EdgeDescriptor

        dereference() const 

        {

            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 

                                  &get_property(*this->base()));

        }

        VertexDescriptor m_src, m_targ;

        VerticesSizeType m_n;

    };

    //=======================================================================

    // Directed In Edge Iterator

    template <

        typename VertexDescriptor, typename MatrixIter

      , typename VerticesSizeType, typename EdgeDescriptor

    >

    struct dir_adj_matrix_in_edge_iter

      : iterator_adaptor<

            dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        >

    {

        typedef iterator_adaptor<

            dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        > super_t;

        dir_adj_matrix_in_edge_iter() { }

        dir_adj_matrix_in_edge_iter(

            const MatrixIter& i

          , const MatrixIter& last

          , const VertexDescriptor& tgt

          , const VerticesSizeType& n

           )

          : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n)

        { }

        void increment() {

          if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {

            this->base_reference() += m_n;

            ++m_src;

          } else {

            this->base_reference() = m_last;

          }

        }

        inline EdgeDescriptor

        dereference() const 

        {

            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ, 

                                  &get_property(*this->base()));

        }

        MatrixIter m_last;

        VertexDescriptor m_src, m_targ;

        VerticesSizeType m_n;

    };

    //=======================================================================

    // Undirected Out Edge Iterator

    template <

        typename VertexDescriptor, typename MatrixIter

      , typename VerticesSizeType, typename EdgeDescriptor

    >

    struct undir_adj_matrix_out_edge_iter 

      : iterator_adaptor<

            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        >

    {

        typedef iterator_adaptor<

            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        > super_t;

        undir_adj_matrix_out_edge_iter() { }

        undir_adj_matrix_out_edge_iter(

            const MatrixIter& i

          , const VertexDescriptor& src

          , const VerticesSizeType& n

        )

          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)

        {}

        void increment()

        {

            if (m_targ < m_src)     // first half

            {

                ++this->base_reference();

            }

            else if (m_targ < m_n - 1)

            {                  // second half

                ++m_inc;

                this->base_reference() += m_inc;

            }

            else

            {                  // past-the-end

                this->base_reference() += m_n - m_src;

            }

            ++m_targ;

        }

        inline EdgeDescriptor

        dereference() const 

        {

            return EdgeDescriptor(

                get_edge_exists(*this->base(), 0), m_src, m_targ

              , &get_property(*this->base())

            );

        }

        VertexDescriptor m_src, m_inc, m_targ;

        VerticesSizeType m_n;

    };

    //=======================================================================

    // Undirected In Edge Iterator

    template <

        typename VertexDescriptor, typename MatrixIter

      , typename VerticesSizeType, typename EdgeDescriptor

    >

    struct undir_adj_matrix_in_edge_iter 

      : iterator_adaptor<

            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        >

    {

        typedef iterator_adaptor<

            undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        > super_t;

        undir_adj_matrix_in_edge_iter() { }

        undir_adj_matrix_in_edge_iter(

            const MatrixIter& i

          , const VertexDescriptor& src

          , const VerticesSizeType& n

        )

          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)

        {}

        void increment()

        {

            if (m_targ < m_src)     // first half

            {

                ++this->base_reference();

            }

            else if (m_targ < m_n - 1)

            {                  // second half

                ++m_inc;

                this->base_reference() += m_inc;

            }

            else

            {                  // past-the-end

                this->base_reference() += m_n - m_src;

            }

            ++m_targ;

        }

        inline EdgeDescriptor

        dereference() const 

        {

            return EdgeDescriptor(

                     get_edge_exists(*this->base(), 0), m_targ, m_src

              , &get_property(*this->base())

            );

        }

        VertexDescriptor m_src, m_inc, m_targ;

        VerticesSizeType m_n;

    };

    //=======================================================================

    // Edge Iterator

    template <typename Directed, typename MatrixIter, 

              typename VerticesSizeType, typename EdgeDescriptor>

    struct adj_matrix_edge_iter

      : iterator_adaptor<

            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        >

    {

        typedef iterator_adaptor<

            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>

          , MatrixIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , std::ptrdiff_t

        > super_t;

        adj_matrix_edge_iter() { }

        adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n) 

            : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }

        void increment()

        {

            increment_dispatch(this->base_reference(), Directed());

        }

        void increment_dispatch(MatrixIter& i, directedS)

        {

            ++i;

            if (m_targ == m_n - 1)

            {

                m_targ = 0;

                ++m_src;

            }

            else

            {

                ++m_targ;

            }

        }

        void increment_dispatch(MatrixIter& i, undirectedS)

        {

            ++i;

            if (m_targ == m_src)

            {

                m_targ = 0;

                ++m_src;

            }

            else

            {

                ++m_targ;

            }

        }

        inline EdgeDescriptor

        dereference() const 

        {

            return EdgeDescriptor(

                get_edge_exists(

                    *this->base(), 0), m_src, m_targ, &get_property(*this->base())

            );

        }

        MatrixIter m_start;

        VerticesSizeType m_src, m_targ, m_n;

    };

  } // namespace detail

  //=========================================================================

  // Adjacency Matrix Traits

  template <typename Directed = directedS>

  class adjacency_matrix_traits {

    typedef typename Directed::is_directed_t is_directed;

  public:

    // The bidirectionalS tag is not allowed with the adjacency_matrix

    // graph type. Instead, use directedS, which also provides the

    // functionality required for a Bidirectional Graph (in_edges,

    // in_degree, etc.).

#if !defined(_MSC_VER) || _MSC_VER > 1300

    BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);

#endif

    typedef typename boost::ct_if_t<is_directed,

                                    bidirectional_tag, undirected_tag>::type

      directed_category;

    typedef disallow_parallel_edge_tag edge_parallel_category;

    typedef std::size_t vertex_descriptor;

    typedef detail::matrix_edge_desc_impl<directed_category,

      vertex_descriptor> edge_descriptor;

  };

  struct adjacency_matrix_class_tag { };

  struct adj_matrix_traversal_tag :

    public virtual adjacency_matrix_tag,

    public virtual vertex_list_graph_tag,

    public virtual incidence_graph_tag,

    public virtual adjacency_graph_tag,

    public virtual edge_list_graph_tag { };

  //=========================================================================

  // Adjacency Matrix Class

  template <typename Directed = directedS,

            typename VertexProperty = no_property,

            typename EdgeProperty = no_property,

            typename GraphProperty = no_property,

            typename Allocator = std::allocator<bool> >

  class adjacency_matrix {

    typedef adjacency_matrix self;

    typedef adjacency_matrix_traits<Directed> Traits;

  public:

#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300

    // The bidirectionalS tag is not allowed with the adjacency_matrix

    // graph type. Instead, use directedS, which also provides the

    // functionality required for a Bidirectional Graph (in_edges,

    // in_degree, etc.).

    BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));

#endif

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type

      vertex_property_type;

    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type

      edge_property_type;

  private:

    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged

      maybe_vertex_bundled;

    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged

      maybe_edge_bundled;

  public:

    // The types that are actually bundled

    typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),

                           no_vertex_bundle,

                           maybe_vertex_bundled>::type vertex_bundled;

    typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),

                           no_edge_bundle,

                           maybe_edge_bundled>::type edge_bundled;

#else

    typedef EdgeProperty     edge_property_type;

    typedef VertexProperty   vertex_property_type;

    typedef no_vertex_bundle vertex_bundled;

    typedef no_edge_bundle   edge_bundled;

#endif

  public: // should be private

    typedef typename ct_if_t<typename has_property<edge_property_type>::type,

      std::pair<bool, edge_property_type>, char>::type StoredEdge;

#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)

    typedef std::vector<StoredEdge> Matrix;

#else

    // This causes internal compiler error for MSVC

    typedef typename Allocator::template rebind<StoredEdge>::other Alloc;

    typedef std::vector<StoredEdge, Alloc> Matrix;

#endif

    typedef typename Matrix::iterator MatrixIter;

    typedef typename Matrix::size_type size_type;

  public:

    // Graph concept required types

    typedef typename Traits::vertex_descriptor vertex_descriptor;

    typedef typename Traits::edge_descriptor edge_descriptor;

    typedef typename Traits::directed_category directed_category;

    typedef typename Traits::edge_parallel_category edge_parallel_category;

    typedef adj_matrix_traversal_tag traversal_category;

    static vertex_descriptor null_vertex()

    {

      return (std::numeric_limits<vertex_descriptor>::max)();

    }

    //private: if friends worked, these would be private

    typedef detail::dir_adj_matrix_out_edge_iter<

        vertex_descriptor, MatrixIter, size_type, edge_descriptor

    > DirOutEdgeIter;

    typedef detail::undir_adj_matrix_out_edge_iter<

        vertex_descriptor, MatrixIter, size_type, edge_descriptor

    > UnDirOutEdgeIter;

    typedef typename ct_if_t<

        typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter

    >::type unfiltered_out_edge_iter;

    typedef detail::dir_adj_matrix_in_edge_iter<

        vertex_descriptor, MatrixIter, size_type, edge_descriptor

    > DirInEdgeIter;

    typedef detail::undir_adj_matrix_in_edge_iter<

        vertex_descriptor, MatrixIter, size_type, edge_descriptor

    > UnDirInEdgeIter;

    typedef typename ct_if_t<

        typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter

    >::type unfiltered_in_edge_iter;

    typedef detail::adj_matrix_edge_iter<

        Directed, MatrixIter, size_type, edge_descriptor

    > unfiltered_edge_iter;

  public:

    // IncidenceGraph concept required types

    typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>

      out_edge_iterator;

    typedef size_type degree_size_type;

    // BidirectionalGraph required types

    typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>

      in_edge_iterator;

    // AdjacencyGraph required types

     typedef typename adjacency_iterator_generator<self,

       vertex_descriptor, out_edge_iterator>::type adjacency_iterator;

    // VertexListGraph required types

    typedef size_type vertices_size_type;

    typedef integer_range<vertex_descriptor> VertexList;

    typedef typename VertexList::iterator vertex_iterator;

    // EdgeListGraph required types

    typedef size_type edges_size_type;

    typedef filter_iterator<

        detail::does_edge_exist, unfiltered_edge_iter

    > edge_iterator;

    // PropertyGraph required types

    typedef adjacency_matrix_class_tag graph_tag;

    // Constructor required by MutableGraph

    adjacency_matrix(vertices_size_type n_vertices) 

      : m_matrix(Directed::is_directed ? 

                 (n_vertices * n_vertices)

                 : (n_vertices * (n_vertices + 1) / 2)),

      m_vertex_set(0, n_vertices),

      m_vertex_properties(n_vertices),

      m_num_edges(0) { }

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    // Directly access a vertex or edge bundle

    vertex_bundled& operator[](vertex_descriptor v)

    { return get(vertex_bundle, *this)[v]; }

    const vertex_bundled& operator[](vertex_descriptor v) const

    { return get(vertex_bundle, *this)[v]; }

    edge_bundled& operator[](edge_descriptor e)

    { return get(edge_bundle, *this)[e]; }

    const edge_bundled& operator[](edge_descriptor e) const

    { return get(edge_bundle, *this)[e]; }

#endif

    //private: if friends worked, these would be private

    typename Matrix::const_reference

    get_edge(vertex_descriptor u, vertex_descriptor v) const {

      if (Directed::is_directed)

        return m_matrix[u * m_vertex_set.size() + v];

      else {

        if (v > u)

          std::swap(u, v);

        return m_matrix[u * (u + 1)/2 + v];

      }

    }

    typename Matrix::reference

    get_edge(vertex_descriptor u, vertex_descriptor v) {

      if (Directed::is_directed)

        return m_matrix[u * m_vertex_set.size() + v];

      else {

        if (v > u)

          std::swap(u, v);

        return m_matrix[u * (u + 1)/2 + v];

      }

    }

    Matrix m_matrix;

    VertexList m_vertex_set;

    std::vector<vertex_property_type> m_vertex_properties;

    size_type m_num_edges;

  };

  //=========================================================================

  // Functions required by the AdjacencyMatrix concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,

            bool>

  edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

       typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

       const adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);

    typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor

      e(exists, u, v, &detail::get_property(g.get_edge(u,v)));

    return std::make_pair(e, exists);

  }

  //=========================================================================

  // Functions required by the IncidenceGraph concept 

  // O(1)

  template <typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,

            typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>

  out_edges

    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)

  {

    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();

    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

    typename Graph::MatrixIter l = f + g.m_vertex_set.size();

    typename Graph::unfiltered_out_edge_iter

          first(f, u, g.m_vertex_set.size())

        , last(l, u, g.m_vertex_set.size());

    detail::does_edge_exist pred;

    typedef typename Graph::out_edge_iterator out_edge_iterator;

    return std::make_pair(out_edge_iterator(pred, first, last), 

                          out_edge_iterator(pred, last, last));

  }

  // O(1)

  template <typename VP, typename EP, typename GP, typename A>

  std::pair<

    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,

    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>

  out_edges

    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)

  {

    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    typename Graph::vertices_size_type offset = u * (u + 1) / 2;

    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

    typename Graph::MatrixIter l = g.m_matrix.end();

    typename Graph::unfiltered_out_edge_iter

        first(f, u, g.m_vertex_set.size())

      , last(l, u, g.m_vertex_set.size());

    detail::does_edge_exist pred;

    typedef typename Graph::out_edge_iterator out_edge_iterator;

    return std::make_pair(out_edge_iterator(pred, first, last), 

                          out_edge_iterator(pred, last, last));

  }

  // O(N)

  template <typename D, typename VP, typename EP, typename GP, typename A>  

  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type

  out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

             const adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;

    typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;

    for (tie(f, l) = out_edges(u, g); f != l; ++f)

      ++n;

    return n;

  }

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A,

    typename Dir, typename Vertex>  

  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

  source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,

         const adjacency_matrix<D,VP,EP,GP,A>&)

  {

    return e.m_source;

  }

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A,

    typename Dir, typename Vertex>  

  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

  target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,

         const adjacency_matrix<D,VP,EP,GP,A>&)

  {

    return e.m_target;

  }

  //=========================================================================

  // Functions required by the BidirectionalGraph concept 

  // O(1)

  template <typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,

            typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>

  in_edges

    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)

  {

    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    typename Graph::MatrixIter f = g.m_matrix.begin() + u;

    typename Graph::MatrixIter l = g.m_matrix.end();

    typename Graph::unfiltered_in_edge_iter

        first(f, l, u, g.m_vertex_set.size())

      , last(l, l, u, g.m_vertex_set.size());

    detail::does_edge_exist pred;

    typedef typename Graph::in_edge_iterator in_edge_iterator;

    return std::make_pair(in_edge_iterator(pred, first, last), 

                          in_edge_iterator(pred, last, last));

  }

  // O(1)

  template <typename VP, typename EP, typename GP, typename A>

  std::pair<

    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,

    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>

  in_edges

    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)

  {

    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    typename Graph::vertices_size_type offset = u * (u + 1) / 2;

    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;

    typename Graph::MatrixIter l = g.m_matrix.end();

    typename Graph::unfiltered_in_edge_iter

        first(f, u, g.m_vertex_set.size())

      , last(l, u, g.m_vertex_set.size());

    detail::does_edge_exist pred;

    typedef typename Graph::in_edge_iterator in_edge_iterator;

    return std::make_pair(in_edge_iterator(pred, first, last), 

                          in_edge_iterator(pred, last, last));

  }

  // O(N)

  template <typename D, typename VP, typename EP, typename GP, typename A>  

  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type

  in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

             const adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;

    typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;

    for (tie(f, l) = in_edges(u, g); f != l; ++f)

      ++n;

    return n;

  }

  //=========================================================================

  // Functions required by the AdjacencyGraph concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,

            typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>

  adjacent_vertices

    (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

     const adjacency_matrix<D,VP,EP,GP,A>& g_)

  {

      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

      const Graph& cg = static_cast<const Graph&>(g_);

      Graph& g = const_cast<Graph&>(cg);

      typedef typename Graph::adjacency_iterator adjacency_iterator;

      typename Graph::out_edge_iterator first, last;

      boost::tie(first, last) = out_edges(u, g);

      return std::make_pair(adjacency_iterator(first, &g),

                            adjacency_iterator(last, &g));

  }

  //=========================================================================

  // Functions required by the VertexListGraph concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,

            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>

  vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {

    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());

  }

  template <typename D, typename VP, typename EP, typename GP, typename A>

  typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type

  num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {

    return g.m_vertex_set.size();

  }

  //=========================================================================

  // Functions required by the EdgeListGraph concept 

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,

            typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>

  edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)

  {

    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;

    Graph& g = const_cast<Graph&>(g_);

    typename Graph::unfiltered_edge_iter

      first(g.m_matrix.begin(), g.m_matrix.begin(), 

                                    g.m_vertex_set.size()),

      last(g.m_matrix.end(), g.m_matrix.begin(), 

                                    g.m_vertex_set.size());

    detail::does_edge_exist pred;

    typedef typename Graph::edge_iterator edge_iterator;

    return std::make_pair(edge_iterator(pred, first, last),

                          edge_iterator(pred, last, last));

  }

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A>

  typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type

  num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    return g.m_num_edges;

  }

  //=========================================================================

  // Functions required by the MutableGraph concept 

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>

  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

           const EP& ep,

           adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor 

      edge_descriptor;

    if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {

      ++(g.m_num_edges);

      detail::set_property(g.get_edge(u,v), ep, 0);

      detail::set_edge_exists(g.get_edge(u,v), true, 0);

      return std::make_pair

        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), 

         true);

    } else

      return std::make_pair

        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),

         false);

  }

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A>

  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>

  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

           adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    EP ep;

    return add_edge(u, v, ep, g);

  }

  // O(1)  

  template <typename D, typename VP, typename EP, typename GP, typename A>

  void

  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

              typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,

              adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    --(g.m_num_edges);

    detail::set_edge_exists(g.get_edge(u,v), false, 0);

  }

  // O(1)

  template <typename D, typename VP, typename EP, typename GP, typename A>

  void

  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,

              adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    remove_edge(source(e, g), target(e, g), g);

  }

  template <typename D, typename VP, typename EP, typename GP, typename A>

  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

  add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {

    // UNDER CONSTRUCTION

    assert(false);

    return *vertices(g).first;

  }

  template <typename D, typename VP, typename EP, typename GP, typename A>

  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor

  add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {

    // UNDER CONSTRUCTION

    assert(false);

    return *vertices(g).first;

  }

  template <typename D, typename VP, typename EP, typename GP, typename A>

  inline void

  remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,

                adjacency_matrix<D,VP,EP,GP,A>& g)

  {

    // UNDER CONSTRUCTION

    assert(false);

  }

  // O(V)

  template <typename VP, typename EP, typename GP, typename A>

  void

  clear_vertex

    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,

     adjacency_matrix<directedS,VP,EP,GP,A>& g)

  {

    typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator 

      vi, vi_end;

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

      remove_edge(u, *vi, g);

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

      remove_edge(*vi, u, g);

  }

  // O(V)

  template <typename VP, typename EP, typename GP, typename A>

  void

  clear_vertex

    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,

     adjacency_matrix<undirectedS,VP,EP,GP,A>& g)

  {

    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator

      vi, vi_end;

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

      remove_edge(u, *vi, g);

  }

  //=========================================================================

  // Vertex Property Map

  template <typename GraphPtr, typename Vertex, typename T, typename R, 

    typename Tag>