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/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:

    93     matrix_adj_iterator() { }

    94     matrix_adj_iterator(Iter i) : _iter(i) { }

    95     matrix_adj_iterator(const self& x) : _iter(x._iter) { }

    96     self& operator=(const self& x) { _iter = x._iter; return *this; }

    97     Vertex operator*() { return _iter.column(); }

    98     self& operator++() { ++_iter; return *this; }

    99     self operator++(int) { self t = *this; ++_iter; return t; }

   100     bool operator==(const self& x) const { return _iter == x._iter; }

   101     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:

   112     matrix_incidence_iterator() { }

   113     matrix_incidence_iterator(Iter i) : _iter(i) { }

   114     matrix_incidence_iterator(const self& x) : _iter(x._iter) { }

   115     self& operator=(const self& x) { _iter = x._iter; return *this; }

   116     Iter operator*() { return _iter; }

   117     self& operator++() { ++_iter; return *this; }

   118     self operator++(int) { self t = *this; ++_iter; return t; }

   119     bool operator==(const self& x) const { return _iter == x._iter; }

   120     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*/