[857] | 1 | //=======================================================================
|
---|
| 2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
---|
| 3 | // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
|
---|
| 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 | // The mutating functions (add_edge, etc.) were added by Vladimir Prus.
|
---|
| 12 |
|
---|
| 13 | #ifndef BOOST_VECTOR_AS_GRAPH_HPP
|
---|
| 14 | #define BOOST_VECTOR_AS_GRAPH_HPP
|
---|
| 15 |
|
---|
| 16 | #include <cassert>
|
---|
| 17 | #include <utility>
|
---|
| 18 | #include <vector>
|
---|
| 19 | #include <cstddef>
|
---|
| 20 | #include <boost/iterator.hpp>
|
---|
| 21 | #include <boost/graph/graph_traits.hpp>
|
---|
| 22 | #include <boost/pending/integer_range.hpp>
|
---|
| 23 | #include <algorithm>
|
---|
| 24 |
|
---|
| 25 | /*
|
---|
| 26 | This module implements the VertexListGraph concept using a
|
---|
| 27 | std::vector as the "back-bone" of the graph (the vector *is* the
|
---|
| 28 | graph object). The edge-lists type of the graph is templated, so the
|
---|
| 29 | user can choose any STL container, so long as the value_type of the
|
---|
| 30 | container is convertible to the size_type of the vector. For now any
|
---|
| 31 | graph properties must be stored seperately.
|
---|
| 32 |
|
---|
| 33 | This module requires the C++ compiler to support partial
|
---|
| 34 | specialization for the graph_traits class, so this is not portable
|
---|
| 35 | to VC++.
|
---|
| 36 |
|
---|
| 37 | */
|
---|
| 38 |
|
---|
| 39 | #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
---|
| 40 | #error The vector-as-graph module requires a compiler that supports partial specialization
|
---|
| 41 | #endif
|
---|
| 42 |
|
---|
| 43 |
|
---|
| 44 | namespace boost {
|
---|
| 45 | namespace detail {
|
---|
| 46 | template <class EdgeList> struct val_out_edge_ret;
|
---|
| 47 | template <class EdgeList> struct val_out_edge_iter;
|
---|
| 48 | template <class EdgeList> struct val_edge;
|
---|
| 49 | }
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 | #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
---|
| 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 typename integer_range<V>::iterator 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 | };
|
---|
| 79 | template <class EdgeList>
|
---|
| 80 | struct edge_property_type< std::vector<EdgeList> >
|
---|
| 81 | {
|
---|
| 82 | typedef void type;
|
---|
| 83 | };
|
---|
| 84 | template <class EdgeList>
|
---|
| 85 | struct vertex_property_type< std::vector<EdgeList> >
|
---|
| 86 | {
|
---|
| 87 | typedef void type;
|
---|
| 88 | };
|
---|
| 89 | template <class EdgeList>
|
---|
| 90 | struct graph_property_type< std::vector<EdgeList> >
|
---|
| 91 | {
|
---|
| 92 | typedef void type;
|
---|
| 93 | };
|
---|
| 94 | }
|
---|
| 95 | #endif
|
---|
| 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<typename boost::integer_range<typename EdgeList::value_type>
|
---|
| 179 | ::iterator,
|
---|
| 180 | typename boost::integer_range<typename EdgeList::value_type>
|
---|
| 181 | ::iterator >
|
---|
| 182 | vertices(const std::vector<EdgeList, Alloc>& v)
|
---|
| 183 | {
|
---|
| 184 | typedef typename boost::integer_range<typename EdgeList::value_type>
|
---|
| 185 | ::iterator Iter;
|
---|
| 186 | return std::make_pair(Iter(0), Iter(v.size()));
|
---|
| 187 | }
|
---|
| 188 |
|
---|
| 189 | template <class EdgeList, class Alloc>
|
---|
| 190 | typename std::vector<EdgeList, Alloc>::size_type
|
---|
| 191 | num_vertices(const std::vector<EdgeList, Alloc>& v)
|
---|
| 192 | {
|
---|
| 193 | return v.size();
|
---|
| 194 | }
|
---|
| 195 |
|
---|
| 196 | template<class EdgeList, class Allocator>
|
---|
| 197 | typename std::pair<typename detail::val_edge<EdgeList>::type, bool>
|
---|
| 198 | add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
|
---|
| 199 | std::vector<EdgeList, Allocator>& g)
|
---|
| 200 | {
|
---|
| 201 | typedef typename detail::val_edge<EdgeList>::type edge_type;
|
---|
| 202 | g[u].insert(g[u].end(), v);
|
---|
| 203 | return std::make_pair(edge_type(u, v), true);
|
---|
| 204 | }
|
---|
| 205 |
|
---|
| 206 | template<class EdgeList, class Allocator>
|
---|
| 207 | typename std::pair<typename detail::val_edge<EdgeList>::type, bool>
|
---|
| 208 | edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
|
---|
| 209 | std::vector<EdgeList, Allocator>& g)
|
---|
| 210 | {
|
---|
| 211 | typedef typename detail::val_edge<EdgeList>::type edge_type;
|
---|
| 212 | typename EdgeList::iterator i = g[u].begin(), end = g[u].end();
|
---|
| 213 | for (; i != end; ++i)
|
---|
| 214 | if (*i == v)
|
---|
| 215 | return std::make_pair(edge_type(u, v), true);
|
---|
| 216 | return std::make_pair(edge_type(), false);
|
---|
| 217 | }
|
---|
| 218 |
|
---|
| 219 | template<class EdgeList, class Allocator>
|
---|
| 220 | void
|
---|
| 221 | remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
|
---|
| 222 | std::vector<EdgeList, Allocator>& g)
|
---|
| 223 | {
|
---|
| 224 | typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
|
---|
| 225 | if (i != g[u].end())
|
---|
| 226 | g[u].erase(i, g[u].end());
|
---|
| 227 | }
|
---|
| 228 |
|
---|
| 229 | template<class EdgeList, class Allocator>
|
---|
| 230 | void
|
---|
| 231 | remove_edge(typename detail::val_edge<EdgeList>::type e,
|
---|
| 232 | std::vector<EdgeList, Allocator>& g)
|
---|
| 233 | {
|
---|
| 234 | typename EdgeList::value_type u, v;
|
---|
| 235 | u = e.first;
|
---|
| 236 | v = e.second;
|
---|
| 237 | // FIXME: edge type does not fully specify the edge to be deleted
|
---|
| 238 | typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
|
---|
| 239 | if (i != g[u].end())
|
---|
| 240 | g[u].erase(i, g[u].end());
|
---|
| 241 | }
|
---|
| 242 |
|
---|
| 243 | template<class EdgeList, class Allocator, class Predicate>
|
---|
| 244 | void
|
---|
| 245 | remove_edge_if(Predicate p,
|
---|
| 246 | std::vector<EdgeList, Allocator>& g)
|
---|
| 247 | {
|
---|
| 248 | for (std::size_t u = 0; u < g.size(); ++u) {
|
---|
| 249 | // Oops! gcc gets internal compiler error on compose_.......
|
---|
| 250 |
|
---|
| 251 | typedef typename EdgeList::iterator iterator;
|
---|
| 252 | iterator b = g[u].begin(), e = g[u].end();
|
---|
| 253 |
|
---|
| 254 | if (!g[u].empty()) {
|
---|
| 255 |
|
---|
| 256 | for(; b != e;) {
|
---|
| 257 | if (p(std::make_pair(u, *b))) {
|
---|
| 258 | --e;
|
---|
| 259 | if (b == e)
|
---|
| 260 | break;
|
---|
| 261 | else
|
---|
| 262 | iter_swap(b, e);
|
---|
| 263 | } else {
|
---|
| 264 | ++b;
|
---|
| 265 | }
|
---|
| 266 | }
|
---|
| 267 | }
|
---|
| 268 |
|
---|
| 269 | if (e != g[u].end())
|
---|
| 270 | g[u].erase(e, g[u].end());
|
---|
| 271 | }
|
---|
| 272 | }
|
---|
| 273 |
|
---|
| 274 | template<class EdgeList, class Allocator>
|
---|
| 275 | typename EdgeList::value_type
|
---|
| 276 | add_vertex(std::vector<EdgeList, Allocator>& g)
|
---|
| 277 | {
|
---|
| 278 | g.resize(g.size()+1);
|
---|
| 279 | return g.size()-1;
|
---|
| 280 | }
|
---|
| 281 |
|
---|
| 282 | template<class EdgeList, class Allocator>
|
---|
| 283 | void
|
---|
| 284 | clear_vertex(typename EdgeList::value_type u,
|
---|
| 285 | std::vector<EdgeList, Allocator>& g)
|
---|
| 286 | {
|
---|
| 287 | g[u].clear();
|
---|
| 288 | for (std::size_t i = 0; i < g.size(); ++i)
|
---|
| 289 | remove_edge(i, u, g);
|
---|
| 290 | }
|
---|
| 291 |
|
---|
| 292 | template<class EdgeList, class Allocator>
|
---|
| 293 | void
|
---|
| 294 | remove_vertex(typename EdgeList::value_type u,
|
---|
| 295 | std::vector<EdgeList, Allocator>& g)
|
---|
| 296 | {
|
---|
| 297 | typedef typename EdgeList::iterator iterator;
|
---|
| 298 | clear_vertex(u, g);
|
---|
| 299 | g.erase(g.begin() + u);
|
---|
| 300 | for (std::size_t i = 0; i < g.size(); ++i)
|
---|
| 301 | for ( iterator it = g[i].begin(); it != g[i].end(); ++it )
|
---|
| 302 | // after clear_vertex *it is never equal to u
|
---|
| 303 | if ( *it > u )
|
---|
| 304 | --*it;
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | } // namespace boost
|
---|
| 308 |
|
---|
| 309 | #endif // BOOST_VECTOR_AS_GRAPH_HPP
|
---|