]>
Commit | Line | Data |
---|---|---|
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 | #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 | ||
47 | is_local_edge() : g(0) {} | |
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. | |
52 | 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 | ||
68 | is_local_vertex() : g(0) {} | |
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. | |
73 | 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 | ||
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 | ||
126 | process_group_type& process_group() | |
127 | { | |
128 | using boost::graph::parallel::process_group; | |
129 | return process_group(g); | |
130 | } | |
131 | 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 | ||
137 | DistributedGraph& base() { return g; } | |
138 | 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 | |
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 | |
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> | |
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 |