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 <boost/config.hpp> 16 #include <boost/operators.hpp> 17 #include <boost/pending/detail/int_iterator.hpp> 18 #include <boost/graph/graph_traits.hpp> 19 20 namespace boost { 21 22 template <class Iter, class Vertex> 23 class matrix_adj_iterator; 24 25 template <class Iter, class Vertex> 26 class matrix_incidence_iterator; 27 28 } 29 30 #define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix) \ 31 namespace boost { \ 32 template <> \ 33 struct graph_traits< Matrix > { \ 34 typedef Matrix::OneD::const_iterator Iter; \ 35 typedef Matrix::size_type V; \ 36 typedef V vertex_descriptor; \ 37 typedef Iter E; \ 38 typedef E edge_descriptor; \ 39 typedef boost::matrix_incidence_iterator<Iter, V> out_edge_iterator; \ 40 typedef boost::matrix_adj_iterator<Iter, V> adjacency_iterator; \ 41 typedef Matrix::size_type size_type; \ 42 typedef boost::int_iterator<size_type> vertex_iterator; \ 43 \ 44 friend std::pair<vertex_iterator, vertex_iterator> \ 45 vertices(const Matrix& g) { \ 46 typedef vertex_iterator VIter; \ 47 return std::make_pair(VIter(0), VIter(g.nrows())); \ 48 } \ 49 \ 50 friend std::pair<out_edge_iterator, out_edge_iterator> \ 51 out_edges(V v, const Matrix& g) { \ 52 typedef out_edge_iterator IncIter; \ 53 return std::make_pair(IncIter(g[v].begin()), \ 54 IncIter(g[v].end())); \ 55 } \ 56 friend std::pair<adjacency_iterator, adjacency_iterator> \ 57 adjacent_vertices(V v, const Matrix& g) { \ 58 typedef adjacency_iterator AdjIter; \ 59 return std::make_pair(AdjIter(g[v].begin()), \ 60 AdjIter(g[v].end())); \ 61 } \ 62 friend vertex_descriptor \ 63 source(E e, const Matrix& g) { \ 64 return e.row(); \ 65 } \ 66 friend vertex_descriptor \ 67 target(E e, const Matrix& g) { \ 68 return e.column(); \ 69 } \ 70 friend size_type \ 71 num_vertices(const Matrix& g) { \ 72 return g.nrows(); \ 73 } \ 74 friend size_type \ 75 num_edges(const Matrix& g) { \ 76 return g.nnz(); \ 77 } \ 78 friend size_type \ 79 out_degree(V i, const Matrix& g) { \ 80 return g[i].nnz(); \ 81 } \ 82 }; \ 83 } 84 85 namespace boost { 86 87 template <class Iter, class Vertex> 88 class matrix_adj_iterator 89 : public std::iterator<std::input_iterator_tag, Vertex > 90 { 91 typedef matrix_adj_iterator self; 92 public: matrix_adj_iterator()93 matrix_adj_iterator() { } matrix_adj_iterator(Iter i)94 matrix_adj_iterator(Iter i) : _iter(i) { } matrix_adj_iterator(const self & x)95 matrix_adj_iterator(const self& x) : _iter(x._iter) { } operator =(const self & x)96 self& operator=(const self& x) { _iter = x._iter; return *this; } operator *()97 Vertex operator*() { return _iter.column(); } operator ++()98 self& operator++() { ++_iter; return *this; } operator ++(int)99 self operator++(int) { self t = *this; ++_iter; return t; } operator ==(const self & x) const100 bool operator==(const self& x) const { return _iter == x._iter; } operator !=(const self & x) const101 bool operator!=(const self& x) const { return _iter != x._iter; } 102 protected: 103 Iter _iter; 104 }; 105 106 template <class Iter, class Vertex> 107 class matrix_incidence_iterator 108 : public std::iterator<std::input_iterator_tag, Iter > 109 { 110 typedef matrix_incidence_iterator self; 111 public: matrix_incidence_iterator()112 matrix_incidence_iterator() { } matrix_incidence_iterator(Iter i)113 matrix_incidence_iterator(Iter i) : _iter(i) { } matrix_incidence_iterator(const self & x)114 matrix_incidence_iterator(const self& x) : _iter(x._iter) { } operator =(const self & x)115 self& operator=(const self& x) { _iter = x._iter; return *this; } operator *()116 Iter operator*() { return _iter; } operator ++()117 self& operator++() { ++_iter; return *this; } operator ++(int)118 self operator++(int) { self t = *this; ++_iter; return t; } operator ==(const self & x) const119 bool operator==(const self& x) const { return _iter == x._iter; } operator !=(const self & x) const120 bool operator!=(const self& x) const { return _iter != x._iter; } 121 protected: 122 Iter _iter; 123 }; 124 125 } /* namespace boost */ 126 127 #endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/ 128