]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Copyright 2006 The Trustees of Indiana University. | |
4 | // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su> | |
5 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor | |
6 | // | |
7 | // Distributed under the Boost Software License, Version 1.0. (See | |
8 | // accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | //======================================================================= | |
11 | ||
12 | // The mutating functions (add_edge, etc.) were added by Vladimir Prus. | |
13 | ||
14 | #ifndef BOOST_VECTOR_AS_GRAPH_HPP | |
15 | #define BOOST_VECTOR_AS_GRAPH_HPP | |
16 | ||
17 | #include <cassert> | |
18 | #include <utility> | |
19 | #include <vector> | |
20 | #include <cstddef> | |
21 | #include <boost/iterator.hpp> | |
22 | #include <boost/iterator/counting_iterator.hpp> | |
23 | #include <boost/range/irange.hpp> | |
24 | #include <boost/graph/graph_traits.hpp> | |
25 | #include <boost/property_map/property_map.hpp> | |
26 | #include <boost/graph/properties.hpp> | |
27 | #include <algorithm> | |
28 | ||
29 | /* | |
30 | This module implements the VertexListGraph concept using a | |
31 | std::vector as the "back-bone" of the graph (the vector *is* the | |
32 | graph object). The edge-lists type of the graph is templated, so the | |
33 | user can choose any STL container, so long as the value_type of the | |
34 | container is convertible to the size_type of the vector. For now any | |
35 | graph properties must be stored seperately. | |
36 | ||
37 | This module requires the C++ compiler to support partial | |
38 | specialization for the graph_traits class, so this is not portable | |
39 | to VC++. | |
40 | ||
41 | */ | |
42 | ||
43 | ||
44 | ||
45 | namespace boost { | |
46 | namespace detail { | |
47 | template <class EdgeList> struct val_out_edge_ret; | |
48 | template <class EdgeList> struct val_out_edge_iter; | |
49 | template <class EdgeList> struct val_edge; | |
50 | } | |
51 | } | |
52 | ||
53 | namespace boost { | |
54 | ||
55 | struct vector_as_graph_traversal_tag | |
56 | : public vertex_list_graph_tag, | |
57 | public adjacency_graph_tag, | |
58 | public incidence_graph_tag { }; | |
59 | ||
60 | template <class EdgeList> | |
61 | struct graph_traits< std::vector<EdgeList> > | |
62 | { | |
63 | typedef typename EdgeList::value_type V; | |
64 | typedef V vertex_descriptor; | |
65 | typedef typename detail::val_edge<EdgeList>::type edge_descriptor; | |
66 | typedef typename EdgeList::const_iterator adjacency_iterator; | |
67 | typedef typename detail::val_out_edge_iter<EdgeList>::type | |
68 | out_edge_iterator; | |
69 | typedef void in_edge_iterator; | |
70 | typedef void edge_iterator; | |
71 | typedef counting_iterator<V> vertex_iterator; | |
72 | typedef directed_tag directed_category; | |
73 | typedef allow_parallel_edge_tag edge_parallel_category; | |
74 | typedef vector_as_graph_traversal_tag traversal_category; | |
75 | typedef typename std::vector<EdgeList>::size_type vertices_size_type; | |
76 | typedef void edges_size_type; | |
77 | typedef typename EdgeList::size_type degree_size_type; | |
78 | static V null_vertex() {return V(-1);} | |
79 | }; | |
80 | template <class EdgeList> | |
81 | struct edge_property_type< std::vector<EdgeList> > | |
82 | { | |
83 | typedef void type; | |
84 | }; | |
85 | template <class EdgeList> | |
86 | struct vertex_property_type< std::vector<EdgeList> > | |
87 | { | |
88 | typedef void type; | |
89 | }; | |
90 | template <class EdgeList> | |
91 | struct graph_property_type< std::vector<EdgeList> > | |
92 | { | |
93 | typedef void type; | |
94 | }; | |
95 | } | |
96 | ||
97 | namespace boost { | |
98 | ||
99 | namespace detail { | |
100 | ||
101 | // "val" is short for Vector Adjacency List | |
102 | ||
103 | template <class EdgeList> | |
104 | struct val_edge | |
105 | { | |
106 | typedef typename EdgeList::value_type V; | |
107 | typedef std::pair<V,V> type; | |
108 | }; | |
109 | ||
110 | // need rewrite this using boost::iterator_adaptor | |
111 | template <class V, class Iter> | |
112 | class val_out_edge_iterator | |
113 | : public boost::iterator<std::input_iterator_tag, std::pair<V,V>, | |
114 | std::ptrdiff_t, std::pair<V,V>*, const std::pair<V,V> > | |
115 | { | |
116 | typedef val_out_edge_iterator self; | |
117 | typedef std::pair<V,V> Edge; | |
118 | public: | |
119 | val_out_edge_iterator() { } | |
120 | val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { } | |
121 | Edge operator*() const { return Edge(_source, *_iter); } | |
122 | self& operator++() { ++_iter; return *this; } | |
123 | self operator++(int) { self t = *this; ++_iter; return t; } | |
124 | bool operator==(const self& x) const { return _iter == x._iter; } | |
125 | bool operator!=(const self& x) const { return _iter != x._iter; } | |
126 | protected: | |
127 | V _source; | |
128 | Iter _iter; | |
129 | }; | |
130 | ||
131 | template <class EdgeList> | |
132 | struct val_out_edge_iter | |
133 | { | |
134 | typedef typename EdgeList::value_type V; | |
135 | typedef typename EdgeList::const_iterator Iter; | |
136 | typedef val_out_edge_iterator<V,Iter> type; | |
137 | }; | |
138 | ||
139 | template <class EdgeList> | |
140 | struct val_out_edge_ret | |
141 | { | |
142 | typedef typename val_out_edge_iter<EdgeList>::type IncIter; | |
143 | typedef std::pair<IncIter,IncIter> type; | |
144 | }; | |
145 | ||
146 | } // namesapce detail | |
147 | ||
148 | template <class EdgeList, class Alloc> | |
149 | typename detail::val_out_edge_ret<EdgeList>::type | |
150 | out_edges(typename EdgeList::value_type v, | |
151 | const std::vector<EdgeList, Alloc>& g) | |
152 | { | |
153 | typedef typename detail::val_out_edge_iter<EdgeList>::type Iter; | |
154 | typedef typename detail::val_out_edge_ret<EdgeList>::type return_type; | |
155 | return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end())); | |
156 | } | |
157 | ||
158 | template <class EdgeList, class Alloc> | |
159 | typename EdgeList::size_type | |
160 | out_degree(typename EdgeList::value_type v, | |
161 | const std::vector<EdgeList, Alloc>& g) | |
162 | { | |
163 | return g[v].size(); | |
164 | } | |
165 | ||
166 | template <class EdgeList, class Alloc> | |
167 | std::pair<typename EdgeList::const_iterator, | |
168 | typename EdgeList::const_iterator> | |
169 | adjacent_vertices(typename EdgeList::value_type v, | |
170 | const std::vector<EdgeList, Alloc>& g) | |
171 | { | |
172 | return std::make_pair(g[v].begin(), g[v].end()); | |
173 | } | |
174 | ||
175 | // source() and target() already provided for pairs in graph_traits.hpp | |
176 | ||
177 | template <class EdgeList, class Alloc> | |
178 | std::pair<boost::counting_iterator<typename EdgeList::value_type>, | |
179 | boost::counting_iterator<typename EdgeList::value_type> > | |
180 | vertices(const std::vector<EdgeList, Alloc>& v) | |
181 | { | |
182 | typedef boost::counting_iterator<typename EdgeList::value_type> Iter; | |
183 | return std::make_pair(Iter(0), Iter(v.size())); | |
184 | } | |
185 | ||
186 | template <class EdgeList, class Alloc> | |
187 | typename std::vector<EdgeList, Alloc>::size_type | |
188 | num_vertices(const std::vector<EdgeList, Alloc>& v) | |
189 | { | |
190 | return v.size(); | |
191 | } | |
192 | ||
193 | template<class EdgeList, class Allocator> | |
194 | typename std::pair<typename detail::val_edge<EdgeList>::type, bool> | |
195 | add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, | |
196 | std::vector<EdgeList, Allocator>& g) | |
197 | { | |
198 | typedef typename detail::val_edge<EdgeList>::type edge_type; | |
199 | g[u].insert(g[u].end(), v); | |
200 | return std::make_pair(edge_type(u, v), true); | |
201 | } | |
202 | ||
203 | template<class EdgeList, class Allocator> | |
204 | typename std::pair<typename detail::val_edge<EdgeList>::type, bool> | |
205 | edge(typename EdgeList::value_type u, typename EdgeList::value_type v, | |
206 | std::vector<EdgeList, Allocator>& g) | |
207 | { | |
208 | typedef typename detail::val_edge<EdgeList>::type edge_type; | |
209 | typename EdgeList::iterator i = g[u].begin(), end = g[u].end(); | |
210 | for (; i != end; ++i) | |
211 | if (*i == v) | |
212 | return std::make_pair(edge_type(u, v), true); | |
213 | return std::make_pair(edge_type(), false); | |
214 | } | |
215 | ||
216 | template<class EdgeList, class Allocator> | |
217 | void | |
218 | remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, | |
219 | std::vector<EdgeList, Allocator>& g) | |
220 | { | |
221 | typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); | |
222 | if (i != g[u].end()) | |
223 | g[u].erase(i, g[u].end()); | |
224 | } | |
225 | ||
226 | template<class EdgeList, class Allocator> | |
227 | void | |
228 | remove_edge(typename detail::val_edge<EdgeList>::type e, | |
229 | std::vector<EdgeList, Allocator>& g) | |
230 | { | |
231 | typename EdgeList::value_type u, v; | |
232 | u = e.first; | |
233 | v = e.second; | |
234 | // FIXME: edge type does not fully specify the edge to be deleted | |
235 | typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); | |
236 | if (i != g[u].end()) | |
237 | g[u].erase(i, g[u].end()); | |
238 | } | |
239 | ||
240 | template<class EdgeList, class Allocator, class Predicate> | |
241 | void | |
242 | remove_edge_if(Predicate p, | |
243 | std::vector<EdgeList, Allocator>& g) | |
244 | { | |
245 | for (std::size_t u = 0; u < g.size(); ++u) { | |
246 | // Oops! gcc gets internal compiler error on compose_....... | |
247 | ||
248 | typedef typename EdgeList::iterator iterator; | |
249 | iterator b = g[u].begin(), e = g[u].end(); | |
250 | ||
251 | if (!g[u].empty()) { | |
252 | ||
253 | for(; b != e;) { | |
254 | if (p(std::make_pair(u, *b))) { | |
255 | --e; | |
256 | if (b == e) | |
257 | break; | |
258 | else | |
259 | iter_swap(b, e); | |
260 | } else { | |
261 | ++b; | |
262 | } | |
263 | } | |
264 | } | |
265 | ||
266 | if (e != g[u].end()) | |
267 | g[u].erase(e, g[u].end()); | |
268 | } | |
269 | } | |
270 | ||
271 | template<class EdgeList, class Allocator> | |
272 | typename EdgeList::value_type | |
273 | add_vertex(std::vector<EdgeList, Allocator>& g) | |
274 | { | |
275 | g.resize(g.size()+1); | |
276 | return g.size()-1; | |
277 | } | |
278 | ||
279 | template<class EdgeList, class Allocator> | |
280 | void | |
281 | clear_vertex(typename EdgeList::value_type u, | |
282 | std::vector<EdgeList, Allocator>& g) | |
283 | { | |
284 | g[u].clear(); | |
285 | for (std::size_t i = 0; i < g.size(); ++i) | |
286 | remove_edge(i, u, g); | |
287 | } | |
288 | ||
289 | template<class EdgeList, class Allocator> | |
290 | void | |
291 | remove_vertex(typename EdgeList::value_type u, | |
292 | std::vector<EdgeList, Allocator>& g) | |
293 | { | |
294 | typedef typename EdgeList::iterator iterator; | |
295 | clear_vertex(u, g); | |
296 | g.erase(g.begin() + u); | |
297 | for (std::size_t i = 0; i < g.size(); ++i) | |
298 | for ( iterator it = g[i].begin(); it != g[i].end(); ++it ) | |
299 | // after clear_vertex *it is never equal to u | |
300 | if ( *it > u ) | |
301 | --*it; | |
302 | } | |
303 | ||
304 | template<typename EdgeList, typename Allocator> | |
305 | struct property_map<std::vector<EdgeList, Allocator>, vertex_index_t> | |
306 | { | |
307 | typedef identity_property_map type; | |
308 | typedef type const_type; | |
309 | }; | |
310 | ||
311 | template<typename EdgeList, typename Allocator> | |
312 | identity_property_map | |
313 | get(vertex_index_t, const std::vector<EdgeList, Allocator>&) | |
314 | { | |
315 | return identity_property_map(); | |
316 | } | |
317 | ||
318 | template<typename EdgeList, typename Allocator> | |
319 | identity_property_map | |
320 | get(vertex_index_t, std::vector<EdgeList, Allocator>&) | |
321 | { | |
322 | return identity_property_map(); | |
323 | } | |
324 | } // namespace boost | |
325 | ||
326 | #endif // BOOST_VECTOR_AS_GRAPH_HPP |