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