[ceph.git] / ceph / src / boost / boost / graph / matrix_as_graph.hpp

//
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// 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_GRAPH_MATRIX2GRAPH_HPP
#define BOOST_GRAPH_MATRIX2GRAPH_HPP

#include <utility>
#include <cstddef>
#include <iterator>
#include <boost/config.hpp>
#include <boost/operators.hpp>
#include <boost/pending/detail/int_iterator.hpp>
#include <boost/graph/graph_traits.hpp>

namespace boost
{

template < class Iter, class Vertex > class matrix_adj_iterator;

template < class Iter, class Vertex > class matrix_incidence_iterator;

}

#define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix)                             \
    namespace boost                                                           \
    {                                                                         \
        template <> struct graph_traits< Matrix >                             \
        {                                                                     \
            typedef Matrix::OneD::const_iterator Iter;                        \
            typedef Matrix::size_type V;                                      \
            typedef V vertex_descriptor;                                      \
            typedef Iter E;                                                   \
            typedef E edge_descriptor;                                        \
            typedef boost::matrix_incidence_iterator< Iter, V >               \
                out_edge_iterator;                                            \
            typedef boost::matrix_adj_iterator< Iter, V > adjacency_iterator; \
            typedef Matrix::size_type size_type;                              \
            typedef boost::int_iterator< size_type > vertex_iterator;         \
                                                                              \
            friend std::pair< vertex_iterator, vertex_iterator > vertices(    \
                const Matrix& g)                                              \
            {                                                                 \
                typedef vertex_iterator VIter;                                \
                return std::make_pair(VIter(0), VIter(g.nrows()));            \
            }                                                                 \
                                                                              \
            friend std::pair< out_edge_iterator, out_edge_iterator >          \
            out_edges(V v, const Matrix& g)                                   \
            {                                                                 \
                typedef out_edge_iterator IncIter;                            \
                return std::make_pair(                                        \
                    IncIter(g[v].begin()), IncIter(g[v].end()));              \
            }                                                                 \
            friend std::pair< adjacency_iterator, adjacency_iterator >        \
            adjacent_vertices(V v, const Matrix& g)                           \
            {                                                                 \
                typedef adjacency_iterator AdjIter;                           \
                return std::make_pair(                                        \
                    AdjIter(g[v].begin()), AdjIter(g[v].end()));              \
            }                                                                 \
            friend vertex_descriptor source(E e, const Matrix& g)             \
            {                                                                 \
                return e.row();                                               \
            }                                                                 \
            friend vertex_descriptor target(E e, const Matrix& g)             \
            {                                                                 \
                return e.column();                                            \
            }                                                                 \
            friend size_type num_vertices(const Matrix& g)                    \
            {                                                                 \
                return g.nrows();                                             \
            }                                                                 \
            friend size_type num_edges(const Matrix& g) { return g.nnz(); }   \
            friend size_type out_degree(V i, const Matrix& g)                 \
            {                                                                 \
                return g[i].nnz();                                            \
            }                                                                 \
        };                                                                    \
    }

namespace boost
{

template < class Iter, class Vertex > class matrix_adj_iterator
{
    typedef matrix_adj_iterator self;

public:
    typedef std::input_iterator_tag iterator_category;
    typedef Vertex value_type;
    typedef std::ptrdiff_t difference_type;
    typedef Vertex* pointer;
    typedef Vertex& reference;
    matrix_adj_iterator() {}
    matrix_adj_iterator(Iter i) : _iter(i) {}
    matrix_adj_iterator(const self& x) : _iter(x._iter) {}
    self& operator=(const self& x)
    {
        _iter = x._iter;
        return *this;
    }
    Vertex operator*() { return _iter.column(); }
    self& operator++()
    {
        ++_iter;
        return *this;
    }
    self operator++(int)
    {
        self t = *this;
        ++_iter;
        return t;
    }
    bool operator==(const self& x) const { return _iter == x._iter; }
    bool operator!=(const self& x) const { return _iter != x._iter; }

protected:
    Iter _iter;
};

template < class Iter, class Vertex > class matrix_incidence_iterator
{
    typedef matrix_incidence_iterator self;

public:
    typedef std::input_iterator_tag iterator_category;
    typedef Iter value_type;
    typedef std::ptrdiff_t difference_type;
    typedef Iter* pointer;
    typedef Iter& reference;
    matrix_incidence_iterator() {}
    matrix_incidence_iterator(Iter i) : _iter(i) {}
    matrix_incidence_iterator(const self& x) : _iter(x._iter) {}
    self& operator=(const self& x)
    {
        _iter = x._iter;
        return *this;
    }
    Iter operator*() { return _iter; }
    self& operator++()
    {
        ++_iter;
        return *this;
    }
    self operator++(int)
    {
        self t = *this;
        ++_iter;
        return t;
    }
    bool operator==(const self& x) const { return _iter == x._iter; }
    bool operator!=(const self& x) const { return _iter != x._iter; }

protected:
    Iter _iter;
};

} /* namespace boost */

#endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/
Commit	Line	Data
7c673cae FG	1	//
	2	//=======================================================================
	3	// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
	4	// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
	5	//
	6	// Distributed under the Boost Software License, Version 1.0. (See
	7	// accompanying file LICENSE_1_0.txt or copy at
	8	// http://www.boost.org/LICENSE_1_0.txt)
	9	//=======================================================================
	10	//
	11	#ifndef BOOST_GRAPH_MATRIX2GRAPH_HPP
	12	#define BOOST_GRAPH_MATRIX2GRAPH_HPP
	13
	14	#include <utility>
92f5a8d4 TL	15	#include <cstddef>
92f5a8d4 TL	16	#include <iterator>
7c673cae FG	17	#include <boost/config.hpp>
	18	#include <boost/operators.hpp>
	19	#include <boost/pending/detail/int_iterator.hpp>
	20	#include <boost/graph/graph_traits.hpp>
	21
f67539c2 TL	22	namespace boost
f67539c2 TL	23	{
7c673cae	24
f67539c2	25	template < class Iter, class Vertex > class matrix_adj_iterator;
7c673cae	26
f67539c2	27	template < class Iter, class Vertex > class matrix_incidence_iterator;
7c673cae FG	28
	29	}
	30
f67539c2 TL	31	#define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix) \
	32	namespace boost \
	33	{ \
	34	template <> struct graph_traits< Matrix > \
	35	{ \
	36	typedef Matrix::OneD::const_iterator Iter; \
	37	typedef Matrix::size_type V; \
	38	typedef V vertex_descriptor; \
	39	typedef Iter E; \
	40	typedef E edge_descriptor; \
	41	typedef boost::matrix_incidence_iterator< Iter, V > \
	42	out_edge_iterator; \
	43	typedef boost::matrix_adj_iterator< Iter, V > adjacency_iterator; \
	44	typedef Matrix::size_type size_type; \
	45	typedef boost::int_iterator< size_type > vertex_iterator; \
	46	\
	47	friend std::pair< vertex_iterator, vertex_iterator > vertices( \
	48	const Matrix& g) \
	49	{ \
	50	typedef vertex_iterator VIter; \
	51	return std::make_pair(VIter(0), VIter(g.nrows())); \
	52	} \
	53	\
	54	friend std::pair< out_edge_iterator, out_edge_iterator > \
	55	out_edges(V v, const Matrix& g) \
	56	{ \
	57	typedef out_edge_iterator IncIter; \
	58	return std::make_pair( \
	59	IncIter(g[v].begin()), IncIter(g[v].end())); \
	60	} \
	61	friend std::pair< adjacency_iterator, adjacency_iterator > \
	62	adjacent_vertices(V v, const Matrix& g) \
	63	{ \
	64	typedef adjacency_iterator AdjIter; \
	65	return std::make_pair( \
	66	AdjIter(g[v].begin()), AdjIter(g[v].end())); \
	67	} \
	68	friend vertex_descriptor source(E e, const Matrix& g) \
	69	{ \
	70	return e.row(); \
	71	} \
	72	friend vertex_descriptor target(E e, const Matrix& g) \
	73	{ \
	74	return e.column(); \
	75	} \
	76	friend size_type num_vertices(const Matrix& g) \
	77	{ \
	78	return g.nrows(); \
	79	} \
	80	friend size_type num_edges(const Matrix& g) { return g.nnz(); } \
	81	friend size_type out_degree(V i, const Matrix& g) \
	82	{ \
	83	return g[i].nnz(); \
	84	} \
	85	}; \
	86	}
7c673cae	87
f67539c2 TL	88	namespace boost
f67539c2 TL	89	{
7c673cae	90
f67539c2 TL	91	template < class Iter, class Vertex > class matrix_adj_iterator
f67539c2 TL	92	{
7c673cae	93	typedef matrix_adj_iterator self;
f67539c2 TL	94
f67539c2 TL	95	public:
92f5a8d4 TL	96	typedef std::input_iterator_tag iterator_category;
	97	typedef Vertex value_type;
	98	typedef std::ptrdiff_t difference_type;
	99	typedef Vertex* pointer;
	100	typedef Vertex& reference;
f67539c2 TL	101	matrix_adj_iterator() {}
	102	matrix_adj_iterator(Iter i) : _iter(i) {}
	103	matrix_adj_iterator(const self& x) : _iter(x._iter) {}
	104	self& operator=(const self& x)
	105	{
	106	_iter = x._iter;
	107	return *this;
	108	}
7c673cae	109	Vertex operator*() { return _iter.column(); }
f67539c2 TL	110	self& operator++()
	111	{
	112	++_iter;
	113	return *this;
	114	}
	115	self operator++(int)
	116	{
	117	self t = *this;
	118	++_iter;
	119	return t;
	120	}
7c673cae FG	121	bool operator==(const self& x) const { return _iter == x._iter; }
7c673cae FG	122	bool operator!=(const self& x) const { return _iter != x._iter; }
f67539c2 TL	123
f67539c2 TL	124	protected:
7c673cae	125	Iter _iter;
f67539c2	126	};
7c673cae	127
f67539c2 TL	128	template < class Iter, class Vertex > class matrix_incidence_iterator
f67539c2 TL	129	{
7c673cae	130	typedef matrix_incidence_iterator self;
f67539c2 TL	131
f67539c2 TL	132	public:
92f5a8d4 TL	133	typedef std::input_iterator_tag iterator_category;
	134	typedef Iter value_type;
	135	typedef std::ptrdiff_t difference_type;
	136	typedef Iter* pointer;
	137	typedef Iter& reference;
f67539c2 TL	138	matrix_incidence_iterator() {}
	139	matrix_incidence_iterator(Iter i) : _iter(i) {}
	140	matrix_incidence_iterator(const self& x) : _iter(x._iter) {}
	141	self& operator=(const self& x)
	142	{
	143	_iter = x._iter;
	144	return *this;
	145	}
7c673cae	146	Iter operator*() { return _iter; }
f67539c2 TL	147	self& operator++()
	148	{
	149	++_iter;
	150	return *this;
	151	}
	152	self operator++(int)
	153	{
	154	self t = *this;
	155	++_iter;
	156	return t;
	157	}
7c673cae FG	158	bool operator==(const self& x) const { return _iter == x._iter; }
7c673cae FG	159	bool operator!=(const self& x) const { return _iter != x._iter; }
f67539c2 TL	160
f67539c2 TL	161	protected:
7c673cae	162	Iter _iter;
f67539c2 TL	163	};
f67539c2 TL	164
7c673cae FG	165	} /* namespace boost */
	166
	167	#endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/