Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_MATRIX2GRAPH_HPP
Chris@16: #define BOOST_GRAPH_MATRIX2GRAPH_HPP
Chris@16: 
Chris@16: #include <utility>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/operators.hpp>
Chris@16: #include <boost/pending/detail/int_iterator.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template <class Iter, class Vertex>
Chris@16:   class matrix_adj_iterator;
Chris@16: 
Chris@16:   template <class Iter, class Vertex>
Chris@16:   class matrix_incidence_iterator;
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: #define BOOST_GRAPH_ADAPT_MATRIX_TO_GRAPH(Matrix)  \
Chris@16: namespace boost { \
Chris@16:   template <> \
Chris@16:   struct graph_traits< Matrix > { \
Chris@16:     typedef Matrix::OneD::const_iterator Iter; \
Chris@16:     typedef Matrix::size_type V; \
Chris@16:     typedef V vertex_descriptor; \
Chris@16:     typedef Iter E; \
Chris@16:     typedef E edge_descriptor; \
Chris@16:     typedef boost::matrix_incidence_iterator<Iter, V> out_edge_iterator; \
Chris@16:     typedef boost::matrix_adj_iterator<Iter, V> adjacency_iterator; \
Chris@16:     typedef Matrix::size_type size_type; \
Chris@16:     typedef boost::int_iterator<size_type> vertex_iterator; \
Chris@16:     \
Chris@16:     friend std::pair<vertex_iterator, vertex_iterator> \
Chris@16:     vertices(const Matrix& g) { \
Chris@16:       typedef vertex_iterator VIter; \
Chris@16:       return std::make_pair(VIter(0), VIter(g.nrows())); \
Chris@16:     } \
Chris@16:     \
Chris@16:     friend std::pair<out_edge_iterator, out_edge_iterator> \
Chris@16:     out_edges(V v, const Matrix& g) { \
Chris@16:       typedef out_edge_iterator IncIter; \
Chris@16:       return std::make_pair(IncIter(g[v].begin()), \
Chris@16:                             IncIter(g[v].end())); \
Chris@16:     } \
Chris@16:     friend std::pair<adjacency_iterator, adjacency_iterator> \
Chris@16:     adjacent_vertices(V v, const Matrix& g) { \
Chris@16:       typedef adjacency_iterator AdjIter; \
Chris@16:       return std::make_pair(AdjIter(g[v].begin()), \
Chris@16:                             AdjIter(g[v].end())); \
Chris@16:     } \
Chris@16:     friend vertex_descriptor \
Chris@16:     source(E e, const Matrix& g) {  \
Chris@16:       return e.row();  \
Chris@16:     } \
Chris@16:     friend vertex_descriptor \
Chris@16:     target(E e, const Matrix& g) { \
Chris@16:       return e.column();  \
Chris@16:     } \
Chris@16:     friend size_type \
Chris@16:     num_vertices(const Matrix& g) { \
Chris@16:       return g.nrows();  \
Chris@16:     } \
Chris@16:     friend size_type \
Chris@16:     num_edges(const Matrix& g) { \
Chris@16:       return g.nnz(); \
Chris@16:     } \
Chris@16:     friend size_type \
Chris@16:     out_degree(V i, const Matrix& g) { \
Chris@16:       return g[i].nnz(); \
Chris@16:     } \
Chris@16:   }; \
Chris@16: }
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template <class Iter, class Vertex>
Chris@16:   class matrix_adj_iterator
Chris@16:     : public std::iterator<std::input_iterator_tag, Vertex >
Chris@16:   {
Chris@16:     typedef matrix_adj_iterator self;
Chris@16:   public:
Chris@16:     matrix_adj_iterator() { }
Chris@16:     matrix_adj_iterator(Iter i) : _iter(i) { }
Chris@16:     matrix_adj_iterator(const self& x) : _iter(x._iter) { }
Chris@16:     self& operator=(const self& x) { _iter = x._iter; return *this; }
Chris@16:     Vertex operator*() { return _iter.column(); }
Chris@16:     self& operator++() { ++_iter; return *this; }
Chris@16:     self operator++(int) { self t = *this; ++_iter; return t; }
Chris@16:     bool operator==(const self& x) const { return _iter == x._iter; }
Chris@16:     bool operator!=(const self& x) const { return _iter != x._iter; }
Chris@16:   protected:
Chris@16:     Iter _iter;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Iter, class Vertex>
Chris@16:   class matrix_incidence_iterator
Chris@16:     : public std::iterator<std::input_iterator_tag, Iter >
Chris@16:   {
Chris@16:     typedef matrix_incidence_iterator self;
Chris@16:   public:
Chris@16:     matrix_incidence_iterator() { }
Chris@16:     matrix_incidence_iterator(Iter i) : _iter(i) { }
Chris@16:     matrix_incidence_iterator(const self& x) : _iter(x._iter) { }
Chris@16:     self& operator=(const self& x) { _iter = x._iter; return *this; }
Chris@16:     Iter operator*() { return _iter; }
Chris@16:     self& operator++() { ++_iter; return *this; }
Chris@16:     self operator++(int) { self t = *this; ++_iter; return t; }
Chris@16:     bool operator==(const self& x) const { return _iter == x._iter; }
Chris@16:     bool operator!=(const self& x) const { return _iter != x._iter; }
Chris@16:   protected:
Chris@16:     Iter _iter;
Chris@16:   };
Chris@16:   
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_GRAPH_MATRIX2GRAPH_HPP*/