PaGMO  1.1.5
clustered_ba.cpp
1 /*****************************************************************************
2  * Copyright (C) 2004-2015 The PaGMO development team, *
3  * Advanced Concepts Team (ACT), European Space Agency (ESA) *
4  * *
5  * https://github.com/esa/pagmo *
6  * *
7  * act@esa.int *
8  * *
9  * This program is free software; you can redistribute it and/or modify *
10  * it under the terms of the GNU General Public License as published by *
11  * the Free Software Foundation; either version 2 of the License, or *
12  * (at your option) any later version. *
13  * *
14  * This program is distributed in the hope that it will be useful, *
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
17  * GNU General Public License for more details. *
18  * *
19  * You should have received a copy of the GNU General Public License *
20  * along with this program; if not, write to the *
21  * Free Software Foundation, Inc., *
22  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
23  *****************************************************************************/
24 
25 #include <boost/numeric/conversion/cast.hpp>
26 #include <boost/random/uniform_int.hpp>
27 #include <cstddef>
28 #include <iterator>
29 #include <sstream>
30 #include <string>
31 #include <utility>
32 
33 
34 #include "../exceptions.h"
35 #include "../rng.h"
36 #include "clustered_ba.h"
37 #include "base.h"
38 
39 namespace pagmo { namespace topology {
40 
42 
52 clustered_ba::clustered_ba(int m0, int m, double p):
53  m_m0(boost::numeric_cast<std::size_t>(m0)),m_m(boost::numeric_cast<std::size_t>(m)), m_p(double(p)),
54  m_drng(rng_generator::get<rng_double>()),m_urng(rng_generator::get<rng_uint32>())
55 {
56  if (m0 < 2 || m < 1 || m > m0) {
57  pagmo_throw(value_error,"the value of m and m0 must be at least 1 and 2, and m must not be greater than m0");
58  }
59  if(p < 0 || p > 1) {
60  pagmo_throw(value_error,"the value of p must be between 0 and 1");
61  }
62 }
63 
65 {
66  return base_ptr(new clustered_ba(*this));
67 }
68 
70 {
71  pagmo_assert(get_number_of_vertices() > 0);
72  const vertices_size_type prev_size = get_number_of_vertices() - 1;
73  if (prev_size < m_m0) {
74  // If we had not built the initial m0 nodes, do it.
75  // We want to connect the newcomer island with high probability, and make sure that
76  // at least one connection exists (otherwise the island stays isolated).
77  // NOTE: is it worth to make it a user-tunable parameter?
78  const double prob = 0.0;
79  // Flag indicating if at least 1 connection was added.
80  bool connection_added = false;
81  // Main loop.
82  for (std::pair<v_iterator,v_iterator> vertices = get_vertices(); vertices.first != vertices.second; ++vertices.first) {
83  // Do not consider the new vertex itself.
84  if (*vertices.first != idx) {
85  if (m_drng() < prob) {
86  connection_added = true;
87  // Add the connections
88  add_edge(*vertices.first,idx);
89  add_edge(idx,*vertices.first);
90  }
91  }
92  }
93  // If no connections were established and this is not the first island being inserted,
94  // establish at least one connection with a random island other than n.
95  if ((!connection_added) && (prev_size != 0)) {
96  // Get a random vertex index between 0 and n_vertices - 1. Keep on repeating the procedure if by
97  // chance we end up on idx again.
98  boost::uniform_int<vertices_size_type> uni_int(0,get_number_of_vertices() - 1);
100  do {
101  rnd = uni_int(m_urng);
102  } while (rnd == idx);
103  // Add connections to the random vertex.
104  add_edge(rnd,idx);
105  add_edge(idx,rnd);
106  }
107  } else {
108  // Now we need to add j edges, choosing the nodes with a probability
109  // proportional to their number of connections. We keep track of the
110  // connection established in order to avoid connecting twice to the same
111  // node.
112  // j is a random integer in the range 1 to m.
113  boost::uniform_int<edges_size_type> uni_int2(1,m_m);
114  std::size_t i = 0;
115  std::size_t j = uni_int2(m_urng);
116  std::pair<v_iterator,v_iterator> vertices;
117  std::pair<a_iterator,a_iterator> adj_vertices;
118  while (i < j) {
119  // Let's find the current total number of edges.
120  const edges_size_type n_edges = get_number_of_edges();
121  pagmo_assert(n_edges > 0);
122  boost::uniform_int<edges_size_type> uni_int(0,n_edges - 1 - i);
123  // Here we choose a random number between 0 and n_edges - 1 - i.
124  const edges_size_type rn = uni_int(m_urng);
125  edges_size_type n = 0;
126  // Iterate over all vertices and accumulate the number of edges for each of them. Stop when the accumulated number of edges is greater
127  // than rn. This is equivalent to giving a chance of connection to vertex v directly proportional to the number of edges departing from v.
128  // You can think of this process as selecting a random edge among all the existing edges and connecting to the vertex from which the
129  // selected edge departs.
130  vertices = get_vertices();
131  for (; vertices.first != vertices.second; ++vertices.first) {
132  // Do not consider it_n.
133  if (*vertices.first != idx) {
134  adj_vertices = get_adjacent_vertices(*vertices.first);
135  n += boost::numeric_cast<edges_size_type>(std::distance(adj_vertices.first,adj_vertices.second));
136  if (n > rn) {
137  break;
138  }
139  }
140  }
141  pagmo_assert(vertices.first != vertices.second);
142  // If the candidate was not already connected, then add it.
143  if (!are_adjacent(idx,*vertices.first)) {
144  // Connect to nodes that are already adjacent to idx with probability p.
145  // This step increases clustering in the network.
146  adj_vertices = get_adjacent_vertices(idx);
147  for(;adj_vertices.first != adj_vertices.second; ++adj_vertices.first) {
148  if(m_drng() < m_p && *adj_vertices.first != *vertices.first && !are_adjacent(*adj_vertices.first,*vertices.first)) {
149  add_edge(*adj_vertices.first, *vertices.first);
150  add_edge(*vertices.first, *adj_vertices.first);
151  }
152  }
153  // Connect to idx
154  add_edge(*vertices.first,idx);
155  add_edge(idx,*vertices.first);
156  ++i;
157  }
158  }
159  }
160 }
161 
163 
170 {
171  std::ostringstream oss;
172  oss << "\tm0 = " << m_m0 << '\n';
173  oss << "\tm = " << m_m << '\n';
174  oss << "\tp = " << m_p << '\n';
175  return oss.str();
176 }
177 
178 std::string clustered_ba::get_name() const
179 {
180  return "Clustered Barabasi-Albert";
181 }
182 
183 }} //namespaces
184 
185 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::topology::clustered_ba)
Root PaGMO namespace.
Generic thread-safe generator of pseudo-random number generators.
Definition: rng.h:138
std::string get_name() const
Get name of the topology.
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base topology.
Definition: topology/base.h:47
base_ptr clone() const
Clone method.
This rng returns an unsigned integer in the [0,2**32-1] range.
Definition: rng.h:47
graph_type::edges_size_type edges_size_type
Edges size type.
clustered_ba(int m0=3, int m=2, double p=0.5)
Constructor from kernel size and number of edges.
STL namespace.
vertices_size_type get_number_of_vertices() const
Get number of vertices.
std::string human_readable_extra() const
Topology-specific human readable info.
Barabási-Albert graph topology.
Definition: clustered_ba.h:53
graph_type::vertices_size_type vertices_size_type
Vertices size type.
void add_edge(const vertices_size_type &, const vertices_size_type &)
Add an edge.
edges_size_type get_number_of_edges() const
Get number of edges.
std::pair< a_iterator, a_iterator > get_adjacent_vertices(const vertices_size_type &) const
Return iterator range to adjacent vertices.
This rng returns a double in the [0,1[ range.
Definition: rng.h:89
std::pair< v_iterator, v_iterator > get_vertices() const
Return iterator range to vertices.
void connect(const vertices_size_type &)
Establish connections between islands during a push_back() operation.
bool are_adjacent(const vertices_size_type &, const vertices_size_type &) const
Return true if two vertices are adjacent.