Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.

boost/graph/adjacency_matrix.hpp

//=======================================================================
// 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 <iterator>
#include <boost/assert.hpp>
#include <boost/limits.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_mutability_traits.hpp>
#include <boost/graph/graph_selectors.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/bool.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/range/irange.hpp>
#include <boost/graph/properties.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/property_map/function_property_map.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();
        }
    };

    // Note to self... The int for get_edge_exists and set_edge exist helps
    // make these calls unambiguous.
    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
    }

    // NOTE: These functions collide with the get_property function for
    // accessing bundled graph properties. Be excplicit when using them.
    template < typename EdgeProperty >
    const EdgeProperty& get_edge_property(
        const std::pair< bool, EdgeProperty >& stored_edge)
    {
        return stored_edge.second;
    }
    template < typename EdgeProperty >
    EdgeProperty& get_edge_property(
        std::pair< bool, EdgeProperty >& stored_edge)
    {
        return stored_edge.second;
    }

    template < typename StoredEdgeProperty, typename EdgeProperty >
    inline void set_edge_property(
        std::pair< bool, StoredEdgeProperty >& stored_edge,
        const EdgeProperty& ep, int)
    {
        stored_edge.second = ep;
    }

    inline const no_property& get_edge_property(const char&)
    {
        static no_property s_prop;
        return s_prop;
    }
    inline no_property& get_edge_property(char&)
    {
        static no_property s_prop;
        return s_prop;
    }
    template < typename EdgeProxy, typename EdgeProperty >
    inline void set_edge_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_edge_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_edge_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_edge_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_edge_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_edge_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.).
    BOOST_STATIC_ASSERT(!(is_same< Directed, bidirectionalS >::value));

    typedef typename mpl::if_< 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:
    // 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));

    typedef GraphProperty graph_property_type;
    typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type
        graph_bundled;

    typedef VertexProperty vertex_property_type;
    typedef
        typename lookup_one_property< VertexProperty, vertex_bundle_t >::type
            vertex_bundled;

    typedef EdgeProperty edge_property_type;
    typedef typename lookup_one_property< EdgeProperty, edge_bundle_t >::type
        edge_bundled;

public: // should be private
    typedef
        typename mpl::if_< typename has_property< edge_property_type >::type,
            std::pair< bool, edge_property_type >, char >::type StoredEdge;
#if defined(BOOST_NO_STD_ALLOCATOR)
    typedef std::vector< StoredEdge > Matrix;
#else
#if defined(BOOST_NO_CXX11_ALLOCATOR)
    typedef typename Allocator::template rebind< StoredEdge >::other Alloc;
#else
    typedef typename std::allocator_traits< Allocator >::template rebind_alloc<
        StoredEdge >
        Alloc;
#endif
    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 mpl::if_< 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 mpl::if_< 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, const GraphProperty& p = GraphProperty())
    : 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)
    , m_property(p)
    {
    }

    template < typename EdgeIterator >
    adjacency_matrix(EdgeIterator first, EdgeIterator last,
        vertices_size_type n_vertices, const GraphProperty& p = GraphProperty())
    : 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)
    , m_property(p)
    {
        for (; first != last; ++first)
        {
            add_edge(first->first, first->second, *this);
        }
    }

    template < typename EdgeIterator, typename EdgePropertyIterator >
    adjacency_matrix(EdgeIterator first, EdgeIterator last,
        EdgePropertyIterator ep_iter, vertices_size_type n_vertices,
        const GraphProperty& p = GraphProperty())
    : 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)
    , m_property(p)
    {
        for (; first != last; ++first, ++ep_iter)
        {
            add_edge(first->first, first->second, *ep_iter, *this);
        }
    }

#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);
    }

    graph_bundled& operator[](graph_bundle_t) { return get_property(*this); }

    const graph_bundled& operator[](graph_bundle_t) const
    {
        return get_property(*this);
    }
#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;
    graph_property_type m_property;
};

//=========================================================================
// 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_edge_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 (boost::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 (boost::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,
    typename EP2 >
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 EP2& 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_edge_property(g.get_edge(u, v), EP(ep), 0);
        detail::set_edge_exists(g.get_edge(u, v), true, 0);
        return std::make_pair(edge_descriptor(true, u, v,
                                  &detail::get_edge_property(g.get_edge(u, v))),
            true);
    }
    else
        return std::make_pair(edge_descriptor(true, u, v,
                                  &detail::get_edge_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)
{
    // Don'remove the edge unless it already exists.
    if (detail::get_edge_exists(g.get_edge(u, v), 0))
    {
        --(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
    BOOST_ASSERT(false);
    return *vertices(g).first;
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename VP2 >
inline typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor
add_vertex(const VP2& /*vp*/, adjacency_matrix< D, VP, EP, GP, A >& g)
{
    // UNDER CONSTRUCTION
    BOOST_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
    BOOST_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 (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        remove_edge(u, *vi, g);
    for (boost::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 (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
        remove_edge(u, *vi, g);
}

//=========================================================================
// Functions required by the PropertyGraph concept

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Prop, typename Kind >
struct adj_mat_pm_helper;

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Prop >
struct adj_mat_pm_helper< D, VP, EP, GP, A, Prop, vertex_property_tag >
{
    typedef typename graph_traits<
        adjacency_matrix< D, VP, EP, GP, A > >::vertex_descriptor arg_type;
    typedef typed_identity_property_map< arg_type > vi_map_type;
    typedef iterator_property_map< typename std::vector< VP >::iterator,
        vi_map_type >
        all_map_type;
    typedef iterator_property_map< typename std::vector< VP >::const_iterator,
        vi_map_type >
        all_map_const_type;
    typedef transform_value_property_map<
        detail::lookup_one_property_f< VP, Prop >, all_map_type >
        type;
    typedef transform_value_property_map<
        detail::lookup_one_property_f< const VP, Prop >, all_map_const_type >
        const_type;
    typedef typename property_traits< type >::reference single_nonconst_type;
    typedef typename property_traits< const_type >::reference single_const_type;

    static type get_nonconst(adjacency_matrix< D, VP, EP, GP, A >& g, Prop prop)
    {
        return type(
            prop, all_map_type(g.m_vertex_properties.begin(), vi_map_type()));
    }

    static const_type get_const(
        const adjacency_matrix< D, VP, EP, GP, A >& g, Prop prop)
    {
        return const_type(prop,
            all_map_const_type(g.m_vertex_properties.begin(), vi_map_type()));
    }

    static single_nonconst_type get_nonconst_one(
        adjacency_matrix< D, VP, EP, GP, A >& g, Prop prop, arg_type v)
    {
        return lookup_one_property< VP, Prop >::lookup(
            g.m_vertex_properties[v], prop);
    }

    static single_const_type get_const_one(
        const adjacency_matrix< D, VP, EP, GP, A >& g, Prop prop, arg_type v)
    {
        return lookup_one_property< const VP, Prop >::lookup(
            g.m_vertex_properties[v], prop);
    }
};

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
struct adj_mat_pm_helper< D, VP, EP, GP, A, Tag, edge_property_tag >
{
    typedef typename graph_traits<
        adjacency_matrix< D, VP, EP, GP, A > >::edge_descriptor edge_descriptor;

    template < typename IsConst > struct lookup_property_from_edge
    {
        Tag tag;
        lookup_property_from_edge(Tag tag) : tag(tag) {}
        typedef typename boost::mpl::if_< IsConst, const EP, EP >::type
            ep_type_nonref;
        typedef ep_type_nonref& ep_type;
        typedef typename lookup_one_property< ep_type_nonref, Tag >::type&
            result_type;
        result_type operator()(edge_descriptor e) const
        {
            return lookup_one_property< ep_type_nonref, Tag >::lookup(
                *static_cast< ep_type_nonref* >(e.get_property()), tag);
        }
    };

    typedef function_property_map<
        lookup_property_from_edge< boost::mpl::false_ >,
        typename graph_traits<
            adjacency_matrix< D, VP, EP, GP, A > >::edge_descriptor >
        type;
    typedef function_property_map<
        lookup_property_from_edge< boost::mpl::true_ >,
        typename graph_traits<
            adjacency_matrix< D, VP, EP, GP, A > >::edge_descriptor >
        const_type;
    typedef edge_descriptor arg_type;
    typedef
        typename lookup_property_from_edge< boost::mpl::false_ >::result_type
            single_nonconst_type;
    typedef typename lookup_property_from_edge< boost::mpl::true_ >::result_type
        single_const_type;

    static type get_nonconst(adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag)
    {
        return type(tag);
    }

    static const_type get_const(
        const adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag)
    {
        return const_type(tag);
    }

    static single_nonconst_type get_nonconst_one(
        adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag, edge_descriptor e)
    {
        return lookup_one_property< EP, Tag >::lookup(
            *static_cast< EP* >(e.get_property()), tag);
    }

    static single_const_type get_const_one(
        const adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag,
        edge_descriptor e)
    {
        return lookup_one_property< const EP, Tag >::lookup(
            *static_cast< const EP* >(e.get_property()), tag);
    }
};

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
struct property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >
: adj_mat_pm_helper< D, VP, EP, GP, A, Tag,
      typename detail::property_kind_from_graph<
          adjacency_matrix< D, VP, EP, GP, A >, Tag >::type >
{
};

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::type get(
    Tag tag, adjacency_matrix< D, VP, EP, GP, A >& g)
{
    return property_map< adjacency_matrix< D, VP, EP, GP, A >,
        Tag >::get_nonconst(g, tag);
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::const_type
get(Tag tag, const adjacency_matrix< D, VP, EP, GP, A >& g)
{
    return property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::get_const(
        g, tag);
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
    Tag >::single_nonconst_type
get(Tag tag, adjacency_matrix< D, VP, EP, GP, A >& g,
    typename property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::arg_type
        a)
{
    return property_map< adjacency_matrix< D, VP, EP, GP, A >,
        Tag >::get_nonconst_one(g, tag, a);
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
    Tag >::single_const_type
get(Tag tag, const adjacency_matrix< D, VP, EP, GP, A >& g,
    typename property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::arg_type
        a)
{
    return property_map< adjacency_matrix< D, VP, EP, GP, A >,
        Tag >::get_const_one(g, tag, a);
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
void put(Tag tag, adjacency_matrix< D, VP, EP, GP, A >& g,
    typename property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::arg_type
        a,
    typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
        Tag >::single_const_type val)
{
    property_map< adjacency_matrix< D, VP, EP, GP, A >, Tag >::get_nonconst_one(
        g, tag, a)
        = val;
}

// O(1)
template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag, typename Value >
inline void set_property(
    adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag, const Value& value)
{
    get_property_value(g.m_property, tag) = value;
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
inline
    typename graph_property< adjacency_matrix< D, VP, EP, GP, A >, Tag >::type&
    get_property(adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag)
{
    return get_property_value(g.m_property, tag);
}

template < typename D, typename VP, typename EP, typename GP, typename A,
    typename Tag >
inline const typename graph_property< adjacency_matrix< D, VP, EP, GP, A >,
    Tag >::type&
get_property(const adjacency_matrix< D, VP, EP, GP, A >& g, Tag tag)
{
    return get_property_value(g.m_property, tag);
}

//=========================================================================
// Vertex Property Map

template < typename D, typename VP, typename EP, typename GP, typename A >
struct property_map< adjacency_matrix< D, VP, EP, GP, A >, vertex_index_t >
{
    typedef
        typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor Vertex;
    typedef typed_identity_property_map< Vertex > type;
    typedef type const_type;
};

template < typename D, typename VP, typename EP, typename GP, typename A >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
    vertex_index_t >::const_type
get(vertex_index_t, adjacency_matrix< D, VP, EP, GP, A >&)
{
    return typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
        vertex_index_t >::const_type();
}

template < typename D, typename VP, typename EP, typename GP, typename A >
typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor get(
    vertex_index_t, adjacency_matrix< D, VP, EP, GP, A >&,
    typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor v)
{
    return v;
}

template < typename D, typename VP, typename EP, typename GP, typename A >
typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
    vertex_index_t >::const_type
get(vertex_index_t, const adjacency_matrix< D, VP, EP, GP, A >&)
{
    return typename property_map< adjacency_matrix< D, VP, EP, GP, A >,
        vertex_index_t >::const_type();
}

template < typename D, typename VP, typename EP, typename GP, typename A >
typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor get(
    vertex_index_t, const adjacency_matrix< D, VP, EP, GP, A >&,
    typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor v)
{
    return v;
}

//=========================================================================
// Other Functions

template < typename D, typename VP, typename EP, typename GP, typename A >
typename adjacency_matrix< D, VP, EP, GP, A >::vertex_descriptor vertex(
    typename adjacency_matrix< D, VP, EP, GP, A >::vertices_size_type n,
    const adjacency_matrix< D, VP, EP, GP, A >&)
{
    return n;
}

template < typename D, typename VP, typename EP, typename GP, typename A >
struct graph_mutability_traits< adjacency_matrix< D, VP, EP, GP, A > >
{
    typedef mutable_edge_property_graph_tag category;
};

} // namespace boost

#endif // BOOST_ADJACENCY_MATRIX_HPP