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 <iterator>
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 namespace boost
44 {
45 namespace detail
46 {
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
56 struct vector_as_graph_traversal_tag : public vertex_list_graph_tag,
57 public adjacency_graph_tag,
58 public incidence_graph_tag
59 {
60 };
61
62 template < class EdgeList > struct graph_traits< std::vector< EdgeList > >
63 {
64 typedef typename EdgeList::value_type V;
65 typedef V vertex_descriptor;
66 typedef typename detail::val_edge< EdgeList >::type edge_descriptor;
67 typedef typename EdgeList::const_iterator adjacency_iterator;
68 typedef
69 typename detail::val_out_edge_iter< EdgeList >::type out_edge_iterator;
70 typedef void in_edge_iterator;
71 typedef void edge_iterator;
72 typedef counting_iterator< V > vertex_iterator;
73 typedef directed_tag directed_category;
74 typedef allow_parallel_edge_tag edge_parallel_category;
75 typedef vector_as_graph_traversal_tag traversal_category;
76 typedef typename std::vector< EdgeList >::size_type vertices_size_type;
77 typedef void edges_size_type;
78 typedef typename EdgeList::size_type degree_size_type;
null_vertexboost::graph_traits79 static V null_vertex() { return V(-1); }
80 };
81 template < class EdgeList > 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
100 namespace detail
101 {
102
103 // "val" is short for Vector Adjacency List
104
105 template < class EdgeList > struct val_edge
106 {
107 typedef typename EdgeList::value_type V;
108 typedef std::pair< V, V > type;
109 };
110
111 // need rewrite this using boost::iterator_adaptor
112 template < class V, class Iter > class val_out_edge_iterator
113 {
114 typedef val_out_edge_iterator self;
115 typedef std::pair< V, V > Edge;
116
117 public:
118 typedef std::input_iterator_tag iterator_category;
119 typedef std::pair< V, V > value_type;
120 typedef std::ptrdiff_t difference_type;
121 typedef std::pair< V, V >* pointer;
122 typedef const std::pair< V, V > reference;
val_out_edge_iterator()123 val_out_edge_iterator() {}
val_out_edge_iterator(V s,Iter i)124 val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) {}
operator *() const125 Edge operator*() const { return Edge(_source, *_iter); }
operator ++()126 self& operator++()
127 {
128 ++_iter;
129 return *this;
130 }
operator ++(int)131 self operator++(int)
132 {
133 self t = *this;
134 ++_iter;
135 return t;
136 }
operator ==(const self & x) const137 bool operator==(const self& x) const { return _iter == x._iter; }
operator !=(const self & x) const138 bool operator!=(const self& x) const { return _iter != x._iter; }
139
140 protected:
141 V _source;
142 Iter _iter;
143 };
144
145 template < class EdgeList > struct val_out_edge_iter
146 {
147 typedef typename EdgeList::value_type V;
148 typedef typename EdgeList::const_iterator Iter;
149 typedef val_out_edge_iterator< V, Iter > type;
150 };
151
152 template < class EdgeList > struct val_out_edge_ret
153 {
154 typedef typename val_out_edge_iter< EdgeList >::type IncIter;
155 typedef std::pair< IncIter, IncIter > type;
156 };
157
158 } // namesapce detail
159
160 template < class EdgeList, class Alloc >
out_edges(typename EdgeList::value_type v,const std::vector<EdgeList,Alloc> & g)161 typename detail::val_out_edge_ret< EdgeList >::type out_edges(
162 typename EdgeList::value_type v, const std::vector< EdgeList, Alloc >& g)
163 {
164 typedef typename detail::val_out_edge_iter< EdgeList >::type Iter;
165 typedef typename detail::val_out_edge_ret< EdgeList >::type return_type;
166 return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end()));
167 }
168
169 template < class EdgeList, class Alloc >
out_degree(typename EdgeList::value_type v,const std::vector<EdgeList,Alloc> & g)170 typename EdgeList::size_type out_degree(
171 typename EdgeList::value_type v, const std::vector< EdgeList, Alloc >& g)
172 {
173 return g[v].size();
174 }
175
176 template < class EdgeList, class Alloc >
177 std::pair< typename EdgeList::const_iterator,
178 typename EdgeList::const_iterator >
adjacent_vertices(typename EdgeList::value_type v,const std::vector<EdgeList,Alloc> & g)179 adjacent_vertices(
180 typename EdgeList::value_type v, const std::vector< EdgeList, Alloc >& g)
181 {
182 return std::make_pair(g[v].begin(), g[v].end());
183 }
184
185 // source() and target() already provided for pairs in graph_traits.hpp
186
187 template < class EdgeList, class Alloc >
188 std::pair< boost::counting_iterator< typename EdgeList::value_type >,
189 boost::counting_iterator< typename EdgeList::value_type > >
vertices(const std::vector<EdgeList,Alloc> & v)190 vertices(const std::vector< EdgeList, Alloc >& v)
191 {
192 typedef boost::counting_iterator< typename EdgeList::value_type > Iter;
193 return std::make_pair(Iter(0), Iter(v.size()));
194 }
195
196 template < class EdgeList, class Alloc >
num_vertices(const std::vector<EdgeList,Alloc> & v)197 typename std::vector< EdgeList, Alloc >::size_type num_vertices(
198 const std::vector< EdgeList, Alloc >& v)
199 {
200 return v.size();
201 }
202
203 template < class EdgeList, class Allocator >
204 typename std::pair< typename detail::val_edge< EdgeList >::type, bool >
add_edge(typename EdgeList::value_type u,typename EdgeList::value_type v,std::vector<EdgeList,Allocator> & g)205 add_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 g[u].insert(g[u].end(), v);
210 return std::make_pair(edge_type(u, v), true);
211 }
212
213 template < class EdgeList, class Allocator >
edge(typename EdgeList::value_type u,typename EdgeList::value_type v,std::vector<EdgeList,Allocator> & g)214 typename std::pair< typename detail::val_edge< EdgeList >::type, bool > edge(
215 typename EdgeList::value_type u, typename EdgeList::value_type v,
216 std::vector< EdgeList, Allocator >& g)
217 {
218 typedef typename detail::val_edge< EdgeList >::type edge_type;
219 typename EdgeList::iterator i = g[u].begin(), end = g[u].end();
220 for (; i != end; ++i)
221 if (*i == v)
222 return std::make_pair(edge_type(u, v), true);
223 return std::make_pair(edge_type(), false);
224 }
225
226 template < class EdgeList, class Allocator >
remove_edge(typename EdgeList::value_type u,typename EdgeList::value_type v,std::vector<EdgeList,Allocator> & g)227 void remove_edge(typename EdgeList::value_type u,
228 typename EdgeList::value_type v, std::vector< EdgeList, Allocator >& g)
229 {
230 typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
231 if (i != g[u].end())
232 g[u].erase(i, g[u].end());
233 }
234
235 template < class EdgeList, class Allocator >
remove_edge(typename detail::val_edge<EdgeList>::type e,std::vector<EdgeList,Allocator> & g)236 void remove_edge(typename detail::val_edge< EdgeList >::type e,
237 std::vector< EdgeList, Allocator >& g)
238 {
239 typename EdgeList::value_type u, v;
240 u = e.first;
241 v = e.second;
242 // FIXME: edge type does not fully specify the edge to be deleted
243 typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
244 if (i != g[u].end())
245 g[u].erase(i, g[u].end());
246 }
247
248 template < class EdgeList, class Allocator, class Predicate >
remove_edge_if(Predicate p,std::vector<EdgeList,Allocator> & g)249 void remove_edge_if(Predicate p, std::vector< EdgeList, Allocator >& g)
250 {
251 for (std::size_t u = 0; u < g.size(); ++u)
252 {
253 // Oops! gcc gets internal compiler error on compose_.......
254
255 typedef typename EdgeList::iterator iterator;
256 iterator b = g[u].begin(), e = g[u].end();
257
258 if (!g[u].empty())
259 {
260
261 for (; b != e;)
262 {
263 if (p(std::make_pair(u, *b)))
264 {
265 --e;
266 if (b == e)
267 break;
268 else
269 iter_swap(b, e);
270 }
271 else
272 {
273 ++b;
274 }
275 }
276 }
277
278 if (e != g[u].end())
279 g[u].erase(e, g[u].end());
280 }
281 }
282
283 template < class EdgeList, class Allocator >
add_vertex(std::vector<EdgeList,Allocator> & g)284 typename EdgeList::value_type add_vertex(std::vector< EdgeList, Allocator >& g)
285 {
286 g.resize(g.size() + 1);
287 return g.size() - 1;
288 }
289
290 template < class EdgeList, class Allocator >
clear_vertex(typename EdgeList::value_type u,std::vector<EdgeList,Allocator> & g)291 void clear_vertex(
292 typename EdgeList::value_type u, std::vector< EdgeList, Allocator >& g)
293 {
294 g[u].clear();
295 for (std::size_t i = 0; i < g.size(); ++i)
296 remove_edge(i, u, g);
297 }
298
299 template < class EdgeList, class Allocator >
remove_vertex(typename EdgeList::value_type u,std::vector<EdgeList,Allocator> & g)300 void remove_vertex(
301 typename EdgeList::value_type u, std::vector< EdgeList, Allocator >& g)
302 {
303 typedef typename EdgeList::iterator iterator;
304 clear_vertex(u, g);
305 g.erase(g.begin() + u);
306 for (std::size_t i = 0; i < g.size(); ++i)
307 for (iterator it = g[i].begin(); it != g[i].end(); ++it)
308 // after clear_vertex *it is never equal to u
309 if (*it > u)
310 --*it;
311 }
312
313 template < typename EdgeList, typename Allocator >
314 struct property_map< std::vector< EdgeList, Allocator >, vertex_index_t >
315 {
316 typedef identity_property_map type;
317 typedef type const_type;
318 };
319
320 template < typename EdgeList, typename Allocator >
get(vertex_index_t,const std::vector<EdgeList,Allocator> &)321 identity_property_map get(
322 vertex_index_t, const std::vector< EdgeList, Allocator >&)
323 {
324 return identity_property_map();
325 }
326
327 template < typename EdgeList, typename Allocator >
get(vertex_index_t,std::vector<EdgeList,Allocator> &)328 identity_property_map get(vertex_index_t, std::vector< EdgeList, Allocator >&)
329 {
330 return identity_property_map();
331 }
332 } // namespace boost
333
334 #endif // BOOST_VECTOR_AS_GRAPH_HPP
335