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>
15 #include <cstddef>
16 #include <iterator>
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 
22 namespace boost {
23 
24   template <class Iter, class Vertex>
25   class matrix_adj_iterator;
26 
27   template <class Iter, class Vertex>
28   class matrix_incidence_iterator;
29 
30 }
31 
32 #define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix)  \
33 namespace boost { \
34   template <> \
35   struct graph_traits< Matrix > { \
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> out_edge_iterator; \
42     typedef boost::matrix_adj_iterator<Iter, V> adjacency_iterator; \
43     typedef Matrix::size_type size_type; \
44     typedef boost::int_iterator<size_type> vertex_iterator; \
45     \
46     friend std::pair<vertex_iterator, vertex_iterator> \
47     vertices(const Matrix& g) { \
48       typedef vertex_iterator VIter; \
49       return std::make_pair(VIter(0), VIter(g.nrows())); \
50     } \
51     \
52     friend std::pair<out_edge_iterator, out_edge_iterator> \
53     out_edges(V v, const Matrix& g) { \
54       typedef out_edge_iterator IncIter; \
55       return std::make_pair(IncIter(g[v].begin()), \
56                             IncIter(g[v].end())); \
57     } \
58     friend std::pair<adjacency_iterator, adjacency_iterator> \
59     adjacent_vertices(V v, const Matrix& g) { \
60       typedef adjacency_iterator AdjIter; \
61       return std::make_pair(AdjIter(g[v].begin()), \
62                             AdjIter(g[v].end())); \
63     } \
64     friend vertex_descriptor \
65     source(E e, const Matrix& g) {  \
66       return e.row();  \
67     } \
68     friend vertex_descriptor \
69     target(E e, const Matrix& g) { \
70       return e.column();  \
71     } \
72     friend size_type \
73     num_vertices(const Matrix& g) { \
74       return g.nrows();  \
75     } \
76     friend size_type \
77     num_edges(const Matrix& g) { \
78       return g.nnz(); \
79     } \
80     friend size_type \
81     out_degree(V i, const Matrix& g) { \
82       return g[i].nnz(); \
83     } \
84   }; \
85 }
86 
87 namespace boost {
88 
89   template <class Iter, class Vertex>
90   class matrix_adj_iterator
91   {
92     typedef matrix_adj_iterator self;
93   public:
94     typedef std::input_iterator_tag iterator_category;
95     typedef Vertex value_type;
96     typedef std::ptrdiff_t difference_type;
97     typedef Vertex* pointer;
98     typedef Vertex& reference;
matrix_adj_iterator()99     matrix_adj_iterator() { }
matrix_adj_iterator(Iter i)100     matrix_adj_iterator(Iter i) : _iter(i) { }
matrix_adj_iterator(const self & x)101     matrix_adj_iterator(const self& x) : _iter(x._iter) { }
operator =(const self & x)102     self& operator=(const self& x) { _iter = x._iter; return *this; }
operator *()103     Vertex operator*() { return _iter.column(); }
operator ++()104     self& operator++() { ++_iter; return *this; }
operator ++(int)105     self operator++(int) { self t = *this; ++_iter; return t; }
operator ==(const self & x) const106     bool operator==(const self& x) const { return _iter == x._iter; }
operator !=(const self & x) const107     bool operator!=(const self& x) const { return _iter != x._iter; }
108   protected:
109     Iter _iter;
110   };
111 
112   template <class Iter, class Vertex>
113   class matrix_incidence_iterator
114   {
115     typedef matrix_incidence_iterator self;
116   public:
117     typedef std::input_iterator_tag iterator_category;
118     typedef Iter value_type;
119     typedef std::ptrdiff_t difference_type;
120     typedef Iter* pointer;
121     typedef Iter& reference;
matrix_incidence_iterator()122     matrix_incidence_iterator() { }
matrix_incidence_iterator(Iter i)123     matrix_incidence_iterator(Iter i) : _iter(i) { }
matrix_incidence_iterator(const self & x)124     matrix_incidence_iterator(const self& x) : _iter(x._iter) { }
operator =(const self & x)125     self& operator=(const self& x) { _iter = x._iter; return *this; }
operator *()126     Iter operator*() { return _iter; }
operator ++()127     self& operator++() { ++_iter; return *this; }
operator ++(int)128     self operator++(int) { self t = *this; ++_iter; return t; }
operator ==(const self & x) const129     bool operator==(const self& x) const { return _iter == x._iter; }
operator !=(const self & x) const130     bool operator!=(const self& x) const { return _iter != x._iter; }
131   protected:
132     Iter _iter;
133   };
134 
135 } /* namespace boost */
136 
137 #endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/
138