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 25 template < class Iter, class Vertex > class matrix_adj_iterator; 26 27 template < class Iter, class Vertex > class matrix_incidence_iterator; 28 29 } 30 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 } 87 88 namespace boost 89 { 90 91 template < class Iter, class Vertex > class matrix_adj_iterator 92 { 93 typedef matrix_adj_iterator self; 94 95 public: 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; matrix_adj_iterator()101 matrix_adj_iterator() {} matrix_adj_iterator(Iter i)102 matrix_adj_iterator(Iter i) : _iter(i) {} matrix_adj_iterator(const self & x)103 matrix_adj_iterator(const self& x) : _iter(x._iter) {} operator =(const self & x)104 self& operator=(const self& x) 105 { 106 _iter = x._iter; 107 return *this; 108 } operator *()109 Vertex operator*() { return _iter.column(); } operator ++()110 self& operator++() 111 { 112 ++_iter; 113 return *this; 114 } operator ++(int)115 self operator++(int) 116 { 117 self t = *this; 118 ++_iter; 119 return t; 120 } operator ==(const self & x) const121 bool operator==(const self& x) const { return _iter == x._iter; } operator !=(const self & x) const122 bool operator!=(const self& x) const { return _iter != x._iter; } 123 124 protected: 125 Iter _iter; 126 }; 127 128 template < class Iter, class Vertex > class matrix_incidence_iterator 129 { 130 typedef matrix_incidence_iterator self; 131 132 public: 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; matrix_incidence_iterator()138 matrix_incidence_iterator() {} matrix_incidence_iterator(Iter i)139 matrix_incidence_iterator(Iter i) : _iter(i) {} matrix_incidence_iterator(const self & x)140 matrix_incidence_iterator(const self& x) : _iter(x._iter) {} operator =(const self & x)141 self& operator=(const self& x) 142 { 143 _iter = x._iter; 144 return *this; 145 } operator *()146 Iter operator*() { return _iter; } operator ++()147 self& operator++() 148 { 149 ++_iter; 150 return *this; 151 } operator ++(int)152 self operator++(int) 153 { 154 self t = *this; 155 ++_iter; 156 return t; 157 } operator ==(const self & x) const158 bool operator==(const self& x) const { return _iter == x._iter; } operator !=(const self & x) const159 bool operator!=(const self& x) const { return _iter != x._iter; } 160 161 protected: 162 Iter _iter; 163 }; 164 165 } /* namespace boost */ 166 167 #endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/ 168