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