boost/graph/matrix_as_graph.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_MATRIX2GRAPH_HPP
0012 #define BOOST_GRAPH_MATRIX2GRAPH_HPP
0013
0014 #include <utility>
0015 #include <cstddef>
0016 #include <iterator>
0017 #include <boost/config.hpp>
0018 #include <boost/operators.hpp>
0019 #include <boost/pending/detail/int_iterator.hpp>
0020 #include <boost/graph/graph_traits.hpp>
0021
0022 namespace boost
0023 {
0024
0025 template < class Iter, class Vertex > class matrix_adj_iterator;
0026
0027 template < class Iter, class Vertex > class matrix_incidence_iterator;
0028
0029 }
0030
0031 #define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix)                             \
0032     namespace boost                                                           \
0033     {                                                                         \
0034         template <> struct graph_traits< Matrix >                             \
0035         {                                                                     \
0036             typedef Matrix::OneD::const_iterator Iter;                        \
0037             typedef Matrix::size_type V;                                      \
0038             typedef V vertex_descriptor;                                      \
0039             typedef Iter E;                                                   \
0040             typedef E edge_descriptor;                                        \
0041             typedef boost::matrix_incidence_iterator< Iter, V >               \
0042                 out_edge_iterator;                                            \
0043             typedef boost::matrix_adj_iterator< Iter, V > adjacency_iterator; \
0044             typedef Matrix::size_type size_type;                              \
0045             typedef boost::int_iterator< size_type > vertex_iterator;         \
0046                                                                               \
0047             friend std::pair< vertex_iterator, vertex_iterator > vertices(    \
0048                 const Matrix& g)                                              \
0049             {                                                                 \
0050                 typedef vertex_iterator VIter;                                \
0051                 return std::make_pair(VIter(0), VIter(g.nrows()));            \
0052             }                                                                 \
0053                                                                               \
0054             friend std::pair< out_edge_iterator, out_edge_iterator >          \
0055             out_edges(V v, const Matrix& g)                                   \
0056             {                                                                 \
0057                 typedef out_edge_iterator IncIter;                            \
0058                 return std::make_pair(                                        \
0059                     IncIter(g[v].begin()), IncIter(g[v].end()));              \
0060             }                                                                 \
0061             friend std::pair< adjacency_iterator, adjacency_iterator >        \
0062             adjacent_vertices(V v, const Matrix& g)                           \
0063             {                                                                 \
0064                 typedef adjacency_iterator AdjIter;                           \
0065                 return std::make_pair(                                        \
0066                     AdjIter(g[v].begin()), AdjIter(g[v].end()));              \
0067             }                                                                 \
0068             friend vertex_descriptor source(E e, const Matrix& g)             \
0069             {                                                                 \
0070                 return e.row();                                               \
0071             }                                                                 \
0072             friend vertex_descriptor target(E e, const Matrix& g)             \
0073             {                                                                 \
0074                 return e.column();                                            \
0075             }                                                                 \
0076             friend size_type num_vertices(const Matrix& g)                    \
0077             {                                                                 \
0078                 return g.nrows();                                             \
0079             }                                                                 \
0080             friend size_type num_edges(const Matrix& g) { return g.nnz(); }   \
0081             friend size_type out_degree(V i, const Matrix& g)                 \
0082             {                                                                 \
0083                 return g[i].nnz();                                            \
0084             }                                                                 \
0085         };                                                                    \
0086     }
0087
0088 namespace boost
0089 {
0090
0091 template < class Iter, class Vertex > class matrix_adj_iterator
0092 {
0093     typedef matrix_adj_iterator self;
0094
0095 public:
0096     typedef std::input_iterator_tag iterator_category;
0097     typedef Vertex value_type;
0098     typedef std::ptrdiff_t difference_type;
0099     typedef Vertex* pointer;
0100     typedef Vertex& reference;
0101     matrix_adj_iterator() {}
0102     matrix_adj_iterator(Iter i) : _iter(i) {}
0103     matrix_adj_iterator(const self& x) : _iter(x._iter) {}
0104     self& operator=(const self& x)
0105     {
0106         _iter = x._iter;
0107         return *this;
0108     }
0109     Vertex operator*() { return _iter.column(); }
0110     self& operator++()
0111     {
0112         ++_iter;
0113         return *this;
0114     }
0115     self operator++(int)
0116     {
0117         self t = *this;
0118         ++_iter;
0119         return t;
0120     }
0121     bool operator==(const self& x) const { return _iter == x._iter; }
0122     bool operator!=(const self& x) const { return _iter != x._iter; }
0123
0124 protected:
0125     Iter _iter;
0126 };
0127
0128 template < class Iter, class Vertex > class matrix_incidence_iterator
0129 {
0130     typedef matrix_incidence_iterator self;
0131
0132 public:
0133     typedef std::input_iterator_tag iterator_category;
0134     typedef Iter value_type;
0135     typedef std::ptrdiff_t difference_type;
0136     typedef Iter* pointer;
0137     typedef Iter& reference;
0138     matrix_incidence_iterator() {}
0139     matrix_incidence_iterator(Iter i) : _iter(i) {}
0140     matrix_incidence_iterator(const self& x) : _iter(x._iter) {}
0141     self& operator=(const self& x)
0142     {
0143         _iter = x._iter;
0144         return *this;
0145     }
0146     Iter operator*() { return _iter; }
0147     self& operator++()
0148     {
0149         ++_iter;
0150         return *this;
0151     }
0152     self operator++(int)
0153     {
0154         self t = *this;
0155         ++_iter;
0156         return t;
0157     }
0158     bool operator==(const self& x) const { return _iter == x._iter; }
0159     bool operator!=(const self& x) const { return _iter != x._iter; }
0160
0161 protected:
0162     Iter _iter;
0163 };
0164
0165 } /* namespace boost */
0166
0167 #endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/