Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / vector_as_graph.hpp
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