source: NonGTP/Boost/boost/graph/matrix_as_graph.hpp @ 857

Revision 857, 4.2 KB checked in by igarcia, 19 years ago (diff)
Line 
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
20namespace 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)  \
31namespace 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
85namespace 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*/
Note: See TracBrowser for help on using the repository browser.