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 #ifndef BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
10 #define BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
11
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
14 #endif
15
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/graph/filtered_graph.hpp>
18 #include <boost/type_traits/is_same.hpp>
19 #include <boost/type_traits/is_base_and_derived.hpp>
20 #include <boost/graph/parallel/container_traits.hpp>
21
22 namespace boost {
23
24 namespace graph { namespace detail {
25 // Optionally, virtually derive from a base class
26 template<bool Derive, typename Base> struct derive_from_if;
27 template<typename Base> struct derive_from_if<true, Base> : virtual Base {};
28 template<typename Base> struct derive_from_if<false, Base> {};
29
30 template<typename NewBase, typename Tag, typename OldBase = NewBase>
31 struct derive_from_if_tag_is :
32 derive_from_if<(is_base_and_derived<OldBase, Tag>::value
33 || is_same<OldBase, Tag>::value),
34 NewBase>
35 {
36 };
37 } } // end namespace graph::detail
38
39 template<typename DistributedGraph>
40 class is_local_edge
41 {
42 public:
43 typedef bool result_type;
44 typedef typename graph_traits<DistributedGraph>::edge_descriptor
45 argument_type;
46
is_local_edge()47 is_local_edge() : g(0) {}
is_local_edge(DistributedGraph & g)48 is_local_edge(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) {}
49
50 // Since either the source or target vertex must be local, the
51 // equivalence of their owners indicates a local edge.
operator ()(const argument_type & e) const52 result_type operator()(const argument_type& e) const
53 { return get(owner, source(e, *g)) == get(owner, target(e, *g)); }
54
55 private:
56 DistributedGraph* g;
57 typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
58 };
59
60 template<typename DistributedGraph>
61 class is_local_vertex
62 {
63 public:
64 typedef bool result_type;
65 typedef typename graph_traits<DistributedGraph>::vertex_descriptor
66 argument_type;
67
is_local_vertex()68 is_local_vertex() : g(0) {}
is_local_vertex(DistributedGraph & g)69 is_local_vertex(DistributedGraph& g) : g(&g), owner(get(vertex_owner, g)) { }
70
71 // Since either the source or target vertex must be local, the
72 // equivalence of their owners indicates a local edge.
operator ()(const argument_type & v) const73 result_type operator()(const argument_type& v) const
74 {
75 return get(owner, v) == process_id(process_group(*g));
76 }
77
78 private:
79 DistributedGraph* g;
80 typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
81 };
82
83 template<typename DistributedGraph>
84 class local_subgraph
85 : public filtered_graph<DistributedGraph,
86 is_local_edge<DistributedGraph>,
87 is_local_vertex<DistributedGraph> >
88 {
89 typedef filtered_graph<DistributedGraph,
90 is_local_edge<DistributedGraph>,
91 is_local_vertex<DistributedGraph> >
92 inherited;
93 typedef typename graph_traits<DistributedGraph>::traversal_category
94 inherited_category;
95
96 public:
97 struct traversal_category :
98 graph::detail::derive_from_if_tag_is<incidence_graph_tag,
99 inherited_category>,
100 graph::detail::derive_from_if_tag_is<adjacency_graph_tag,
101 inherited_category>,
102 graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
103 inherited_category>,
104 graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
105 inherited_category>,
106 graph::detail::derive_from_if_tag_is<vertex_list_graph_tag,
107 inherited_category,
108 distributed_vertex_list_graph_tag>,
109 graph::detail::derive_from_if_tag_is<edge_list_graph_tag,
110 inherited_category,
111 distributed_edge_list_graph_tag>
112 { };
113
local_subgraph(DistributedGraph & g)114 local_subgraph(DistributedGraph& g)
115 : inherited(g,
116 is_local_edge<DistributedGraph>(g),
117 is_local_vertex<DistributedGraph>(g)),
118 g(g)
119 {
120 }
121
122 // Distributed Container
123 typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
124 process_group_type;
125
process_group()126 process_group_type& process_group()
127 {
128 using boost::graph::parallel::process_group;
129 return process_group(g);
130 }
process_group() const131 const process_group_type& process_group() const
132 {
133 using boost::graph::parallel::process_group;
134 return boost::graph::parallel::process_group(g);
135 }
136
base()137 DistributedGraph& base() { return g; }
base() const138 const DistributedGraph& base() const { return g; }
139
140 private:
141 DistributedGraph& g;
142 };
143
144 template<typename DistributedGraph, typename PropertyTag>
145 class property_map<local_subgraph<DistributedGraph>, PropertyTag>
146 : public property_map<DistributedGraph, PropertyTag> { };
147
148 template<typename DistributedGraph, typename PropertyTag>
149 class property_map<local_subgraph<const DistributedGraph>, PropertyTag>
150 {
151 public:
152 typedef typename property_map<DistributedGraph, PropertyTag>::const_type
153 type;
154 typedef type const_type;
155 };
156
157 template<typename PropertyTag, typename DistributedGraph>
158 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>::type
get(PropertyTag p,local_subgraph<DistributedGraph> & g)159 get(PropertyTag p, local_subgraph<DistributedGraph>& g)
160 { return get(p, g.base()); }
161
162 template<typename PropertyTag, typename DistributedGraph>
163 inline typename property_map<local_subgraph<DistributedGraph>, PropertyTag>
164 ::const_type
get(PropertyTag p,const local_subgraph<DistributedGraph> & g)165 get(PropertyTag p, const local_subgraph<DistributedGraph>& g)
166 { return get(p, g.base()); }
167
168 template<typename DistributedGraph>
169 inline local_subgraph<DistributedGraph>
make_local_subgraph(DistributedGraph & g)170 make_local_subgraph(DistributedGraph& g)
171 { return local_subgraph<DistributedGraph>(g); }
172
173 } // end namespace boost
174
175 #endif // BOOST_GRAPH_LOCAL_SUBGRAPH_HPP
176