1 /* Copyright 2017-2021 PaGMO development team
2
3 This file is part of the PaGMO library.
4
5 The PaGMO library is free software; you can redistribute it and/or modify
6 it under the terms of either:
7
8 * the GNU Lesser General Public License as published by the Free
9 Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 or
13
14 * the GNU General Public License as published by the Free Software
15 Foundation; either version 3 of the License, or (at your option) any
16 later version.
17
18 or both in parallel, as here.
19
20 The PaGMO library is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
22 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
23 for more details.
24
25 You should have received copies of the GNU General Public License and the
26 GNU Lesser General Public License along with the PaGMO library. If not,
27 see https://www.gnu.org/licenses/. */
28
29 #include <algorithm>
30 #include <cassert>
31 #include <cstddef>
32 #include <mutex>
33 #include <sstream>
34 #include <stdexcept>
35 #include <string>
36 #include <utility>
37 #include <vector>
38
39 #include <boost/graph/adjacency_list.hpp>
40 #include <boost/iterator/transform_iterator.hpp>
41 #include <boost/iterator/zip_iterator.hpp>
42 #include <boost/numeric/conversion/cast.hpp>
43 #include <boost/tuple/tuple.hpp>
44 #include <boost/tuple/tuple_io.hpp>
45
46 #include <pagmo/exceptions.hpp>
47 #include <pagmo/io.hpp>
48 #include <pagmo/topologies/base_bgl_topology.hpp>
49 #include <pagmo/topology.hpp>
50 #include <pagmo/types.hpp>
51
52 namespace pagmo
53 {
54
55 namespace detail
56 {
57
58 namespace
59 {
60
61 // Small helpers to reduce typing when converting to/from std::size_t.
62 template <typename I>
scast(I n)63 std::size_t scast(I n)
64 {
65 return boost::numeric_cast<std::size_t>(n);
66 }
67
vcast(std::size_t n)68 bgl_graph_t::vertices_size_type vcast(std::size_t n)
69 {
70 return boost::numeric_cast<bgl_graph_t::vertices_size_type>(n);
71 }
72
73 } // namespace
74
75 } // namespace detail
76
77 // Small helper function that checks that the input vertices are in the graph.
78 // It will throw otherwise.
unsafe_check_vertex_indices() const79 void base_bgl_topology::unsafe_check_vertex_indices() const {}
80
81 template <typename... Args>
unsafe_check_vertex_indices(std::size_t idx,Args...others) const82 void base_bgl_topology::unsafe_check_vertex_indices(std::size_t idx, Args... others) const
83 {
84 const auto nv = boost::num_vertices(m_graph);
85 if (idx >= nv) {
86 pagmo_throw(std::invalid_argument, "invalid vertex index in a BGL topology: the index is " + std::to_string(idx)
87 + ", but the number of vertices is only " + std::to_string(nv));
88 }
89 unsafe_check_vertex_indices(others...);
90 }
91
get_graph() const92 bgl_graph_t base_bgl_topology::get_graph() const
93 {
94 std::lock_guard<std::mutex> lock(m_mutex);
95 return m_graph;
96 }
97
move_graph()98 bgl_graph_t base_bgl_topology::move_graph()
99 {
100 std::lock_guard<std::mutex> lock(m_mutex);
101 return std::move(m_graph);
102 }
103
set_graph(bgl_graph_t && g)104 void base_bgl_topology::set_graph(bgl_graph_t &&g)
105 {
106 std::lock_guard<std::mutex> lock(m_mutex);
107 m_graph = std::move(g);
108 }
109
base_bgl_topology(const base_bgl_topology & other)110 base_bgl_topology::base_bgl_topology(const base_bgl_topology &other) : m_graph(other.get_graph()) {}
111
base_bgl_topology(base_bgl_topology && other)112 base_bgl_topology::base_bgl_topology(base_bgl_topology &&other) noexcept : m_graph(other.move_graph()) {}
113
operator =(const base_bgl_topology & other)114 base_bgl_topology &base_bgl_topology::operator=(const base_bgl_topology &other)
115 {
116 if (this != &other) {
117 set_graph(other.get_graph());
118 }
119 return *this;
120 }
121
operator =(base_bgl_topology && other)122 base_bgl_topology &base_bgl_topology::operator=(base_bgl_topology &&other) noexcept
123 {
124 if (this != &other) {
125 set_graph(other.move_graph());
126 }
127 return *this;
128 }
129
add_vertex()130 void base_bgl_topology::add_vertex()
131 {
132 std::lock_guard<std::mutex> lock(m_mutex);
133 boost::add_vertex(m_graph);
134 }
135
num_vertices() const136 std::size_t base_bgl_topology::num_vertices() const
137 {
138 std::lock_guard<std::mutex> lock(m_mutex);
139 return detail::scast(boost::num_vertices(m_graph));
140 }
141
unsafe_are_adjacent(std::size_t i,std::size_t j) const142 bool base_bgl_topology::unsafe_are_adjacent(std::size_t i, std::size_t j) const
143 {
144 unsafe_check_vertex_indices(i, j);
145 const auto a_vertices = boost::adjacent_vertices(boost::vertex(detail::vcast(i), m_graph), m_graph);
146 return std::find(a_vertices.first, a_vertices.second, boost::vertex(detail::vcast(j), m_graph))
147 != a_vertices.second;
148 }
149
are_adjacent(std::size_t i,std::size_t j) const150 bool base_bgl_topology::are_adjacent(std::size_t i, std::size_t j) const
151 {
152 std::lock_guard<std::mutex> lock(m_mutex);
153 return unsafe_are_adjacent(i, j);
154 }
155
add_edge(std::size_t i,std::size_t j,double w)156 void base_bgl_topology::add_edge(std::size_t i, std::size_t j, double w)
157 {
158 detail::topology_check_edge_weight(w);
159
160 std::lock_guard<std::mutex> lock(m_mutex);
161
162 if (unsafe_are_adjacent(i, j)) {
163 pagmo_throw(std::invalid_argument, "cannot add an edge in a BGL topology: there is already an edge connecting "
164 + std::to_string(i) + " to " + std::to_string(j));
165 }
166
167 const auto result
168 = boost::add_edge(boost::vertex(detail::vcast(i), m_graph), boost::vertex(detail::vcast(j), m_graph), m_graph);
169 assert(result.second);
170 m_graph[result.first] = w;
171 }
172
remove_edge(std::size_t i,std::size_t j)173 void base_bgl_topology::remove_edge(std::size_t i, std::size_t j)
174 {
175 std::lock_guard<std::mutex> lock(m_mutex);
176
177 if (!unsafe_are_adjacent(i, j)) {
178 pagmo_throw(std::invalid_argument, "cannot remove an edge in a BGL topology: there is no edge connecting "
179 + std::to_string(i) + " to " + std::to_string(j));
180 }
181 boost::remove_edge(boost::vertex(detail::vcast(i), m_graph), boost::vertex(detail::vcast(j), m_graph), m_graph);
182 }
183
set_all_weights(double w)184 void base_bgl_topology::set_all_weights(double w)
185 {
186 detail::topology_check_edge_weight(w);
187
188 std::lock_guard<std::mutex> lock(m_mutex);
189
190 for (auto e_range = boost::edges(m_graph); e_range.first != e_range.second; ++e_range.first) {
191 m_graph[*e_range.first] = w;
192 }
193 }
194
set_weight(std::size_t i,std::size_t j,double w)195 void base_bgl_topology::set_weight(std::size_t i, std::size_t j, double w)
196 {
197 detail::topology_check_edge_weight(w);
198
199 std::lock_guard<std::mutex> lock(m_mutex);
200
201 unsafe_check_vertex_indices(i, j);
202
203 const auto ret
204 = boost::edge(boost::vertex(detail::vcast(i), m_graph), boost::vertex(detail::vcast(j), m_graph), m_graph);
205 if (ret.second) {
206 m_graph[ret.first] = w;
207 } else {
208 pagmo_throw(std::invalid_argument, "cannot set the weight of an edge in a BGL topology: the vertex "
209 + std::to_string(i) + " is not connected to vertex "
210 + std::to_string(j));
211 }
212 }
213
get_connections(std::size_t i) const214 std::pair<std::vector<std::size_t>, vector_double> base_bgl_topology::get_connections(std::size_t i) const
215 {
216 std::lock_guard<std::mutex> lock(m_mutex);
217
218 unsafe_check_vertex_indices(i);
219
220 std::pair<std::vector<std::size_t>, vector_double> retval;
221
222 const auto vi = boost::vertex(detail::vcast(i), m_graph);
223 for (auto iav = boost::inv_adjacent_vertices(vi, m_graph); iav.first != iav.second; ++iav.first) {
224 const auto e = boost::edge(boost::vertex(*iav.first, m_graph), vi, m_graph);
225 assert(e.second);
226 retval.first.emplace_back(detail::scast(*iav.first));
227 retval.second.emplace_back(m_graph[e.first]);
228 }
229 return retval;
230 }
231
get_edge_weight(std::size_t i,std::size_t j) const232 double base_bgl_topology::get_edge_weight(std::size_t i, std::size_t j) const
233 {
234 std::lock_guard<std::mutex> lock(m_mutex);
235
236 unsafe_check_vertex_indices(i, j);
237
238 const auto ret
239 = boost::edge(boost::vertex(detail::vcast(i), m_graph), boost::vertex(detail::vcast(j), m_graph), m_graph);
240 if (ret.second) {
241 return m_graph[ret.first];
242 } else {
243 pagmo_throw(std::invalid_argument, "cannot get the weight of an edge in a BGL topology: the vertex "
244 + std::to_string(i) + " is not connected to vertex "
245 + std::to_string(j));
246 }
247 }
248
get_extra_info() const249 std::string base_bgl_topology::get_extra_info() const
250 {
251 std::ostringstream oss;
252
253 {
254 std::lock_guard<std::mutex> lock(m_mutex);
255
256 oss << "\tNumber of vertices: " << boost::num_vertices(m_graph) << '\n';
257 oss << "\tNumber of edges: " << boost::num_edges(m_graph) << '\n';
258 oss << "\tAdjacency list:\n\n";
259
260 for (auto vs = boost::vertices(m_graph); vs.first != vs.second; ++vs.first) {
261 // Get the list of outgoing edges from the current vertex.
262 const auto erange = boost::out_edges(*vs.first, m_graph);
263
264 // Helper to extract the target vertex from an edge descriptor (that is,
265 // the vertex a directed edge points to).
266 auto target_getter = [this](decltype(*erange.first) ed) { return boost::target(ed, m_graph); };
267
268 // Helper to extract the edge weight from an edge descriptor.
269 auto weight_getter = [this](decltype(*erange.first) ed) { return m_graph[ed]; };
270
271 // Make zip iterators for bundling together the target of an edge
272 // and its weight.
273 auto z_begin = boost::make_zip_iterator(
274 boost::make_tuple(boost::make_transform_iterator(erange.first, target_getter),
275 boost::make_transform_iterator(erange.first, weight_getter)));
276 auto z_end = boost::make_zip_iterator(
277 boost::make_tuple(boost::make_transform_iterator(erange.second, target_getter),
278 boost::make_transform_iterator(erange.second, weight_getter)));
279
280 // Print the vertex, and its adjacent vertices together with the edges' weights.
281 oss << "\t\t" << *vs.first << ": ";
282 detail::stream_range(oss, z_begin, z_end);
283 oss << '\n';
284 }
285 }
286
287 return oss.str();
288 }
289
to_bgl() const290 bgl_graph_t base_bgl_topology::to_bgl() const
291 {
292 return get_graph();
293 }
294
295 } // namespace pagmo
296