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
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 //=======================================================================
12 // The mutating functions (add_edge, etc.) were added by Vladimir Prus.
14 #ifndef BOOST_VECTOR_AS_GRAPH_HPP
15 #define BOOST_VECTOR_AS_GRAPH_HPP
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>
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.
37 This module requires the C++ compiler to support partial
38 specialization for the graph_traits class, so this is not portable
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;
55 struct vector_as_graph_traversal_tag
56 : public vertex_list_graph_tag,
57 public adjacency_graph_tag,
58 public incidence_graph_tag { };
60 template <class EdgeList>
61 struct graph_traits< std::vector<EdgeList> >
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
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);}
80 template <class EdgeList>
81 struct edge_property_type< std::vector<EdgeList> >
85 template <class EdgeList>
86 struct vertex_property_type< std::vector<EdgeList> >
90 template <class EdgeList>
91 struct graph_property_type< std::vector<EdgeList> >
101 // "val" is short for Vector Adjacency List
103 template <class EdgeList>
106 typedef typename EdgeList::value_type V;
107 typedef std::pair<V,V> type;
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> >
116 typedef val_out_edge_iterator self;
117 typedef std::pair<V,V> Edge;
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; }
131 template <class EdgeList>
132 struct val_out_edge_iter
134 typedef typename EdgeList::value_type V;
135 typedef typename EdgeList::const_iterator Iter;
136 typedef val_out_edge_iterator<V,Iter> type;
139 template <class EdgeList>
140 struct val_out_edge_ret
142 typedef typename val_out_edge_iter<EdgeList>::type IncIter;
143 typedef std::pair<IncIter,IncIter> type;
146 } // namesapce detail
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)
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()));
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)
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)
172 return std::make_pair(g[v].begin(), g[v].end());
175 // source() and target() already provided for pairs in graph_traits.hpp
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)
182 typedef boost::counting_iterator<typename EdgeList::value_type> Iter;
183 return std::make_pair(Iter(0), Iter(v.size()));
186 template <class EdgeList, class Alloc>
187 typename std::vector<EdgeList, Alloc>::size_type
188 num_vertices(const std::vector<EdgeList, Alloc>& v)
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)
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);
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)
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)
212 return std::make_pair(edge_type(u, v), true);
213 return std::make_pair(edge_type(), false);
216 template<class EdgeList, class Allocator>
218 remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
219 std::vector<EdgeList, Allocator>& g)
221 typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
223 g[u].erase(i, g[u].end());
226 template<class EdgeList, class Allocator>
228 remove_edge(typename detail::val_edge<EdgeList>::type e,
229 std::vector<EdgeList, Allocator>& g)
231 typename EdgeList::value_type u, v;
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);
237 g[u].erase(i, g[u].end());
240 template<class EdgeList, class Allocator, class Predicate>
242 remove_edge_if(Predicate p,
243 std::vector<EdgeList, Allocator>& g)
245 for (std::size_t u = 0; u < g.size(); ++u) {
246 // Oops! gcc gets internal compiler error on compose_.......
248 typedef typename EdgeList::iterator iterator;
249 iterator b = g[u].begin(), e = g[u].end();
254 if (p(std::make_pair(u, *b))) {
267 g[u].erase(e, g[u].end());
271 template<class EdgeList, class Allocator>
272 typename EdgeList::value_type
273 add_vertex(std::vector<EdgeList, Allocator>& g)
275 g.resize(g.size()+1);
279 template<class EdgeList, class Allocator>
281 clear_vertex(typename EdgeList::value_type u,
282 std::vector<EdgeList, Allocator>& g)
285 for (std::size_t i = 0; i < g.size(); ++i)
286 remove_edge(i, u, g);
289 template<class EdgeList, class Allocator>
291 remove_vertex(typename EdgeList::value_type u,
292 std::vector<EdgeList, Allocator>& g)
294 typedef typename EdgeList::iterator iterator;
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
304 template<typename EdgeList, typename Allocator>
305 struct property_map<std::vector<EdgeList, Allocator>, vertex_index_t>
307 typedef identity_property_map type;
308 typedef type const_type;
311 template<typename EdgeList, typename Allocator>
312 identity_property_map
313 get(vertex_index_t, const std::vector<EdgeList, Allocator>&)
315 return identity_property_map();
318 template<typename EdgeList, typename Allocator>
319 identity_property_map
320 get(vertex_index_t, std::vector<EdgeList, Allocator>&)
322 return identity_property_map();
326 #endif // BOOST_VECTOR_AS_GRAPH_HPP