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