PaGMO  1.1.5
ageing_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 "ageing_clustered_ba.h"
37 #include "base.h"
38 
39 namespace pagmo { namespace topology {
40 
42 
54 ageing_clustered_ba::ageing_clustered_ba(int m0, int m, double p, int a):
55  m_m0(boost::numeric_cast<std::size_t>(m0)),m_m(boost::numeric_cast<std::size_t>(m)), m_p(double(p)), m_a(int(a)),
56  m_drng(rng_generator::get<rng_double>()),m_urng(rng_generator::get<rng_uint32>())
57 {
58  if (m0 < 2 || m < 1 || m > m0) {
59  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");
60  }
61  if(a < m) {
62  pagmo_throw(value_error,"the value a must be greater than the value of m");
63  }
64  if(p < 0 || p > 1) {
65  pagmo_throw(value_error,"the value of p must be between 0 and 1");
66  }
67 }
68 
69 
71 {
72  return base_ptr(new ageing_clustered_ba(*this));
73 }
74 
76 {
77  pagmo_assert(get_number_of_vertices() > 0);
78  const vertices_size_type prev_size = get_number_of_vertices() - 1;
79  if (prev_size < m_m0) {
80  // If we had not built the initial m0 nodes, do it.
81  // We want to connect the newcomer island with high probability, and make sure that
82  // at least one connection exists (otherwise the island stays isolated).
83  // NOTE: is it worth to make it a user-tunable parameter?
84  const double prob = 0.0;
85  // Flag indicating if at least 1 connection was added.
86  bool connection_added = false;
87  // Main loop.
88  for (std::pair<v_iterator,v_iterator> vertices = get_vertices(); vertices.first != vertices.second; ++vertices.first) {
89  // Do not consider the new vertex itself.
90  if (*vertices.first != idx) {
91  if (m_drng() < prob) {
92  connection_added = true;
93  // Add the connections
94  add_edge(*vertices.first,idx);
95  add_edge(idx,*vertices.first);
96  }
97  }
98  }
99  // If no connections were established and this is not the first island being inserted,
100  // establish at least one connection with a random island other than n.
101  if ((!connection_added) && (prev_size != 0)) {
102  // Get a random vertex index between 0 and n_vertices - 1. Keep on repeating the procedure if by
103  // chance we end up on idx again.
104  boost::uniform_int<vertices_size_type> uni_int(0,get_number_of_vertices() - 1);
105  vertices_size_type rnd;
106  do {
107  rnd = uni_int(m_urng);
108  } while (rnd == idx);
109  // Add connections to the random vertex.
110  add_edge(rnd,idx);
111  add_edge(idx,rnd);
112  }
113  } else {
114  // Now we need to add j edges, choosing the nodes with a probability
115  // proportional to their number of connections. We keep track of the
116  // connection established in order to avoid connecting twice to the same
117  // node.
118  // j is a random integer in the range 1 to m.
119  boost::uniform_int<edges_size_type> uni_int2(1,m_m);
120  std::size_t i = 0;
121  std::size_t j = uni_int2(m_urng);
122  std::pair<v_iterator,v_iterator> vertices;
123  std::pair<a_iterator,a_iterator> adj_vertices;
124  // Determine the lower bound (used by ageing mechanism)
125  int min_n_edges = 0;
126  vertices = get_vertices();
127  for(; vertices.first != vertices.second; ++vertices.first) {
128  int a = *vertices.first;
129  int b = idx - m_a;
130  if(a < b) {
131  min_n_edges += get_num_adjacent_vertices(*vertices.first);
132  }
133  }
134  while (i < j) {
135  // Let's find the current total number of edges.
137  pagmo_assert(n_edges > 0);
138  boost::uniform_int<edges_size_type> uni_int(min_n_edges,n_edges - 1 - i);
139  // Here we choose a random number between min_n_edges and n_edges - 1 - i.
140  const edges_size_type rn = uni_int(m_urng);
141  edges_size_type n = 0;
142  // Iterate over all vertices and accumulate the number of edges for each of them. Stop when the accumulated number of edges is greater
143  // than rn. This is equivalent to giving a chance of connection to vertex v directly proportional to the number of edges departing from v.
144  // You can think of this process as selecting a random edge among all the existing edges and connecting to the vertex from which the
145  // selected edge departs.
146  vertices = get_vertices();
147  for (; vertices.first != vertices.second; ++vertices.first) {
148  // Do not consider it_n.
149  if (*vertices.first != idx) {
150  adj_vertices = get_adjacent_vertices(*vertices.first);
151  n += boost::numeric_cast<edges_size_type>(std::distance(adj_vertices.first,adj_vertices.second));
152  if (n > rn) {
153  break;
154  }
155  }
156  }
157  pagmo_assert(vertices.first != vertices.second);
158  // If the candidate was not already connected, then add it.
159  if (!are_adjacent(idx,*vertices.first)) {
160  // Connect to nodes that are already adjacent to idx with probability p.
161  // This step increases clustering in the network.
162  adj_vertices = get_adjacent_vertices(idx);
163  for(;adj_vertices.first != adj_vertices.second; ++adj_vertices.first) {
164  if(m_drng() < m_p && *adj_vertices.first != *vertices.first && !are_adjacent(*adj_vertices.first,*vertices.first)) {
165  add_edge(*adj_vertices.first, *vertices.first);
166  add_edge(*vertices.first, *adj_vertices.first);
167  }
168  }
169  // Connect to idx
170  add_edge(*vertices.first,idx);
171  add_edge(idx,*vertices.first);
172  ++i;
173  }
174  }
175  }
176 }
177 
179 
186 {
187  std::ostringstream oss;
188  oss << "\tm0 = " << m_m0 << '\n';
189  oss << "\tm = " << m_m << '\n';
190  oss << "\tp = " << m_p << '\n';
191  oss << "\ta = " << m_a << '\n';
192  return oss.str();
193 }
194 
195 std::string ageing_clustered_ba::get_name() const
196 {
197  return "Ageing Clustered Barabasi-Albert";
198 }
199 
200 }} //namespaces
201 
202 BOOST_CLASS_EXPORT_IMPLEMENT(pagmo::topology::ageing_clustered_ba)
Root PaGMO namespace.
Generic thread-safe generator of pseudo-random number generators.
Definition: rng.h:138
boost::shared_ptr< base > base_ptr
Alias for shared pointer to base topology.
Definition: topology/base.h:47
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 Barabási-Albert with Ageing vertices graph topology.
STL namespace.
void connect(const vertices_size_type &)
Establish connections between islands during a push_back() operation.
std::string human_readable_extra() const
Topology-specific human readable info.
vertices_size_type get_number_of_vertices() const
Get number of vertices.
base_ptr clone() const
Clone method.
graph_type::vertices_size_type vertices_size_type
Vertices size type.
ageing_clustered_ba(int m0=3, int m=2, double p=0.5, int a=1000)
Constructor from kernel size, maximum number of edges, connection probability and maximum node age...
edges_size_type get_num_adjacent_vertices(const vertices_size_type &) const
Return the number of adjacent vertices.
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.
std::string get_name() const
Get name of the topology.
bool are_adjacent(const vertices_size_type &, const vertices_size_type &) const
Return true if two vertices are adjacent.