]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/vertex_list_adaptor.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / graph_parallel / include / boost / graph / distributed / vertex_list_adaptor.hpp
CommitLineData
7c673cae
FG		 1// Copyright (C) 2004-2006 The Trustees of Indiana University.
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// Authors: Douglas Gregor
8// Andrew Lumsdaine
9
10#ifndef BOOST_VERTEX_LIST_ADAPTOR_HPP
11#define BOOST_VERTEX_LIST_ADAPTOR_HPP
12
13#ifndef BOOST_GRAPH_USE_MPI
14#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
15#endif
16
17#include <boost/graph/graph_traits.hpp>
18#include <vector>
19#include <boost/shared_ptr.hpp>
20#include <boost/property_map/property_map.hpp>
21#include <boost/graph/parallel/algorithm.hpp>
22#include <boost/graph/parallel/container_traits.hpp>
23#include <boost/property_map/vector_property_map.hpp>
24
25namespace boost { namespace graph {
26
27// --------------------------------------------------------------------------
28// Global index map built from a distribution
29// --------------------------------------------------------------------------
30template<typename Distribution, typename OwnerPropertyMap,
31 typename LocalPropertyMap>
32class distribution_global_index_map
33{
34 public:
35 typedef std::size_t value_type;
36 typedef value_type reference;
37 typedef typename property_traits<OwnerPropertyMap>::key_type key_type;
38 typedef readable_property_map_tag category;
39
40 distribution_global_index_map(const Distribution& distribution,
41 const OwnerPropertyMap& owner,
42 const LocalPropertyMap& local)
43 : distribution_(distribution), owner(owner), local(local) { }
44
45 Distribution distribution_;
46 OwnerPropertyMap owner;
47 LocalPropertyMap local;
48};
49
50template<typename Distribution, typename OwnerPropertyMap,
51 typename LocalPropertyMap>
52inline
53typename distribution_global_index_map<Distribution, OwnerPropertyMap,
54 LocalPropertyMap>::value_type
55get(const distribution_global_index_map<Distribution, OwnerPropertyMap,
56 LocalPropertyMap>& p,
57 typename distribution_global_index_map<Distribution, OwnerPropertyMap,
58 LocalPropertyMap>::key_type x)
59{
60 using boost::get;
61 return p.distribution_.global(get(p.owner, x), get(p.local, x));
62}
63
64template<typename Graph, typename Distribution>
65inline
66distribution_global_index_map<
67 Distribution,
68 typename property_map<Graph, vertex_owner_t>::const_type,
69 typename property_map<Graph, vertex_local_t>::const_type>
70make_distribution_global_index_map(const Graph& g, const Distribution& d)
71{
72 typedef distribution_global_index_map<
73 Distribution,
74 typename property_map<Graph, vertex_owner_t>::const_type,
75 typename property_map<Graph, vertex_local_t>::const_type>
76 result_type;
77 return result_type(d, get(vertex_owner, g), get(vertex_local, g));
78}
79
80// --------------------------------------------------------------------------
81// Global index map built from a distributed index map and list of vertices
82// --------------------------------------------------------------------------
83template<typename IndexMap>
84class stored_global_index_map : public IndexMap
85{
86 public:
87 typedef readable_property_map_tag category;
88
89 stored_global_index_map(const IndexMap& index_map) : IndexMap(index_map) {
90 // When we have a global index, we need to always have the indices
91 // of every key we've seen
92 this->set_max_ghost_cells(0);
93 }
94};
95
96// --------------------------------------------------------------------------
97// Global index map support code
98// --------------------------------------------------------------------------
99namespace detail {
100 template<typename PropertyMap, typename ForwardIterator>
101 inline void
102 initialize_global_index_map(const PropertyMap&,
103 ForwardIterator, ForwardIterator)
104 { }
105
106 template<typename IndexMap, typename ForwardIterator>
107 void
108 initialize_global_index_map(stored_global_index_map<IndexMap>& p,
109 ForwardIterator first, ForwardIterator last)
110 {
111 using std::distance;
112
113 typedef typename property_traits<IndexMap>::value_type size_t;
114
115 size_t n = distance(first, last);
116 for (size_t i = 0; i < n; ++i, ++first) local_put(p, *first, i);
117 }
118}
119
120// --------------------------------------------------------------------------
121// Adapts a Distributed Vertex List Graph to a Vertex List Graph
122// --------------------------------------------------------------------------
123template<typename Graph, typename GlobalIndexMap>
124class vertex_list_adaptor : public graph_traits<Graph>
125{
126 typedef graph_traits<Graph> inherited;
127
128 typedef typename inherited::traversal_category base_traversal_category;
129
130 public:
131 typedef typename inherited::vertex_descriptor vertex_descriptor;
132 typedef typename std::vector<vertex_descriptor>::iterator vertex_iterator;
133 typedef typename std::vector<vertex_descriptor>::size_type
134 vertices_size_type;
135
136 struct traversal_category
137 : public virtual base_traversal_category,
138 public virtual vertex_list_graph_tag {};
139
140 vertex_list_adaptor(const Graph& g,
141 const GlobalIndexMap& index_map = GlobalIndexMap())
142 : g(&g), index_map(index_map)
143 {
144 using boost::vertices;
145
146 all_vertices_.reset(new std::vector<vertex_descriptor>());
147 all_gather(process_group(), vertices(g).first, vertices(g).second,
148 *all_vertices_);
149 detail::initialize_global_index_map(this->index_map,
150 all_vertices_->begin(),
151 all_vertices_->end());
152 }
153
154 const Graph& base() const { return *g; }
155
156 // --------------------------------------------------------------------------
157 // Distributed Container
158 // --------------------------------------------------------------------------
159 typedef typename boost::graph::parallel::process_group_type<Graph>::type
160 process_group_type;
161
162 process_group_type process_group() const
163 {
164 using boost::graph::parallel::process_group;
165 return process_group(*g);
166 }
167
168 std::pair<vertex_iterator, vertex_iterator> vertices() const
169 { return std::make_pair(all_vertices_->begin(), all_vertices_->end()); }
170
171 vertices_size_type num_vertices() const { return all_vertices_->size(); }
172
173 GlobalIndexMap get_index_map() const { return index_map; }
174
175 private:
176 const Graph* g;
177 GlobalIndexMap index_map;
178 shared_ptr<std::vector<vertex_descriptor> > all_vertices_;
179};
180
181template<typename Graph, typename GlobalIndexMap>
182inline vertex_list_adaptor<Graph, GlobalIndexMap>
183make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map)
184{ return vertex_list_adaptor<Graph, GlobalIndexMap>(g, index_map); }
185
186namespace detail {
187 template<typename Graph>
188 class default_global_index_map
189 {
190 typedef typename graph_traits<Graph>::vertices_size_type value_type;
191 typedef typename property_map<Graph, vertex_index_t>::const_type local_map;
192
193 public:
194 typedef vector_property_map<value_type, local_map> distributed_map;
195 typedef stored_global_index_map<distributed_map> type;
196 };
197}
198
199template<typename Graph>
200inline
201vertex_list_adaptor<Graph,
202 typename detail::default_global_index_map<Graph>::type>
203make_vertex_list_adaptor(const Graph& g)
204{
205 typedef typename detail::default_global_index_map<Graph>::type
206 GlobalIndexMap;
207 typedef typename detail::default_global_index_map<Graph>::distributed_map
208 DistributedMap;
209 typedef vertex_list_adaptor<Graph, GlobalIndexMap> result_type;
210 return result_type(g,
211 GlobalIndexMap(DistributedMap(num_vertices(g),
212 get(vertex_index, g))));
213}
214
215// --------------------------------------------------------------------------
216// Incidence Graph
217// --------------------------------------------------------------------------
218template<typename Graph, typename GlobalIndexMap>
219inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
220source(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
221 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
222{ return source(e, g.base()); }
223
224template<typename Graph, typename GlobalIndexMap>
225inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
226target(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
227 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
228{ return target(e, g.base()); }
229
230template<typename Graph, typename GlobalIndexMap>
231inline
232std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator,
233 typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator>
234out_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
235 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
236{ return out_edges(v, g.base()); }
237
238template<typename Graph, typename GlobalIndexMap>
239inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
240out_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
241 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
242{ return out_degree(v, g.base()); }
243
244// --------------------------------------------------------------------------
245// Bidirectional Graph
246// --------------------------------------------------------------------------
247template<typename Graph, typename GlobalIndexMap>
248inline
249std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator,
250 typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator>
251in_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
252 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
253{ return in_edges(v, g.base()); }
254
255template<typename Graph, typename GlobalIndexMap>
256inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
257in_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
258 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
259{ return in_degree(v, g.base()); }
260
261template<typename Graph, typename GlobalIndexMap>
262inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
263degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
264 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
265{ return degree(v, g.base()); }
266
267// --------------------------------------------------------------------------
268// Adjacency Graph
269// --------------------------------------------------------------------------
270template<typename Graph, typename GlobalIndexMap>
271inline
272std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator,
273 typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator>
274adjacent_vertices(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
275 const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
276{ return adjacent_vertices(v, g.base()); }
277
278
279// --------------------------------------------------------------------------
280// Vertex List Graph
281// --------------------------------------------------------------------------
282template<typename Graph, typename GlobalIndexMap>
283inline
284std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator,
285 typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator>
286vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
287{ return g.vertices(); }
288
289template<typename Graph, typename GlobalIndexMap>
290inline
291typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
292num_vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
293{ return g.num_vertices(); }
294
295// --------------------------------------------------------------------------
296// Edge List Graph
297// --------------------------------------------------------------------------
298template<typename Graph, typename GlobalIndexMap>
299inline
300std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator,
301 typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator>
302edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
303{ return edges(g.base()); }
304
305template<typename Graph, typename GlobalIndexMap>
306inline
307typename vertex_list_adaptor<Graph, GlobalIndexMap>::edges_size_type
308num_edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
309{ return num_edges(g.base()); }
310
311// --------------------------------------------------------------------------
312// Property Graph
313// --------------------------------------------------------------------------
314template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
315inline typename property_map<Graph, PropertyTag>::type
316get(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g)
317{ return get(p, g.base()); }
318
319template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
320inline typename property_map<Graph, PropertyTag>::const_type
321get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
322{ return get(p, g.base()); }
323
324template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
325inline typename property_traits<
326 typename property_map<Graph, PropertyTag>::type
327 >::value_type
328get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
329 typename property_traits<
330 typename property_map<Graph, PropertyTag>::type
331 >::key_type const& x)
332{ return get(p, g.base(), x); }
333
334template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
335inline void
336put(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g,
337 typename property_traits<
338 typename property_map<Graph, PropertyTag>::type
339 >::key_type const& x,
340 typename property_traits<
341 typename property_map<Graph, PropertyTag>::type
342 >::value_type const& v)
343{ return put(p, g.base(), x, v); }
344
345// --------------------------------------------------------------------------
346// Property Graph: vertex_index property
347// --------------------------------------------------------------------------
348template<typename Graph, typename GlobalIndexMap>
349inline GlobalIndexMap
350get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
351{ return g.get_index_map(); }
352
353template<typename Graph, typename GlobalIndexMap>
354inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
355get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
356 typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor x)
357{ return get(g.get_index_map(), x); }
358
359// --------------------------------------------------------------------------
360// Adjacency Matrix Graph
361// --------------------------------------------------------------------------
362template<typename Graph, typename GlobalIndexMap>
363std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor,
364 bool>
365edge(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor u,
366 typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
367 vertex_list_adaptor<Graph, GlobalIndexMap>& g)
368{ return edge(u, v, g.base()); }
369
370} } // end namespace boost::graph
371
372namespace boost {
373
374// --------------------------------------------------------------------------
375// Property Graph: vertex_index property
376// --------------------------------------------------------------------------
377template<typename Graph, typename GlobalIndexMap>
378class property_map<vertex_index_t,
379 graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
380{
381public:
382 typedef GlobalIndexMap type;
383 typedef type const_type;
384};
385
386template<typename Graph, typename GlobalIndexMap>
387class property_map<vertex_index_t,
388 const graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
389{
390public:
391 typedef GlobalIndexMap type;
392 typedef type const_type;
393};
394
395using graph::distribution_global_index_map;
396using graph::make_distribution_global_index_map;
397using graph::stored_global_index_map;
398using graph::make_vertex_list_adaptor;
399using graph::vertex_list_adaptor;
400
401} // end namespace boost
402
403#endif // BOOST_VERTEX_LIST_ADAPTOR_HPP
Ceph