Topology

New in version 2.11.

#include <pagmo/topology.hpp>

class topology

In the jargon of pagmo, a topology is an object that represents connections among islands in an archipelago. In essence, a topology is a weighted directed graph in which

  • the vertices (or nodes) are islands,

  • the edges (or arcs) are directed connections between islands across which information flows during the optimisation process (via the migration of individuals),

  • the weights of the edges (whose numerical values are the \([0.,1.]\) range) represent the migration probability.

Following the same schema adopted for problem, algorithm, etc., topology exposes a type-erased generic interface to user-defined topologies (or UDT for short). UDTs are classes providing a certain set of member functions that describe the properties of (and allow to interact with) a topology. Once defined and instantiated, a UDT can then be used to construct an instance of this class, topology, which provides a generic interface to topologies for use by archipelago.

In a topology, vertices in the graph are identified by a zero-based unique integral index (represented by a std::size_t). This integral index corresponds to the index of an island in an archipelago.

Every UDT must implement at least the following member functions:

std::pair<std::vector<std::size_t>, vector_double> get_connections(std::size_t) const;
void push_back();

The get_connections() function takes as input a vertex index n, and it is expected to return a pair of vectors containing respectively:

  • the indices of the vertices which are connecting to n (that is, the list of vertices for which a directed edge towards n exists),

  • the weights (i.e., the migration probabilities) of the edges linking the connecting vertices to n.

The push_back() member function is expected to add a new vertex to the topology, assigning it the next available index and establishing connections to other vertices. The push_back() member function is invoked by pagmo::archipelago::push_back() upon the insertion of a new island into an archipelago, and it is meant to allow the incremental construction of a topology. That is, after N calls to push_back() on an initially-empty topology, the topology should contain N vertices and any number of edges (depending on the specifics of the topology).

In addition to providing the above member functions, a UDT must also be default, copy and move constructible.

Additional optional member functions can be implemented in a UDT:

std::string get_name() const;
std::string get_extra_info() const;
bgl_graph_t to_bgl() const;

See the documentation of the corresponding member functions in this class for details on how the optional member functions in the UDT are used by topology.

Topologies are used in asynchronous operations involving migration in archipelagos, and thus they need to provide a certain degree of thread safety. Specifically, the get_connections() member function of the UDT might be invoked concurrently with any other member function of the UDT interface (except for the destructor, the move constructor, and, if implemented, the deserialisation function). It is up to the authors of user-defined topologies to ensure that this safety requirement is satisfied.

Warning

The only operations allowed on a moved-from pagmo::topology are destruction, assignment, and the invocation of the is_valid() member function. Any other operation will result in undefined behaviour.

topology()

Default constructor.

The default constructor will initialize a topology containing an unconnected topology.

Throws

unspecified – any exception raised by the constructor from a generic UDT.

topology(const topology&)
topology(topology&&) noexcept
topology &operator=(const topology&)
topology &operator=(topology&&) noexcept

topology is copy/move constructible, and copy/move assignable. Copy construction/assignment will perform deep copies, move operations will leave the moved-from object in a state which is destructible and assignable.

Throws

unspecified – when performing copy operations, any exception raised by the UDT upon copying, or by memory allocation failures.

template<typename T>
explicit topology(T &&x)

Generic constructor from a UDT.

This constructor participates in overload resolution only if T, after the removal of reference and cv qualifiers, is not topology and if it satisfies pagmo::is_udt.

This constructor will construct a topology from the UDT (user-defined topology) x of type T. The input parameter x will be perfectly forwarded to construct the internal UDT instance.

Parameters

x – the input UDT.

Throws

unspecified – any exception thrown by the public API of the UDT, or by memory allocation failures.

template<typename T>
topology &operator=(T &&x)

Generic assignment operator from a UDT.

This operator participates in overload resolution only if T, after the removal of reference and cv qualifiers, is not topology and if it satisfies pagmo::is_udt.

This operator will set the internal UDT to x by constructing a topology from x, and then move-assigning the result to this.

Parameters

x – the input UDT.

Returns

a reference to this.

Throws

unspecified – any exception thrown by the generic constructor from a UDT.

template<typename T>
const T *extract() const noexcept
template<typename T>
T *extract() noexcept

Extract a (const) pointer to the internal UDT instance.

If T is the type of the UDT currently stored within this object, then this function will return a (const) pointer to the internal UDT instance. Otherwise, nullptr will be returned.

The returned value is a raw non-owning pointer: the lifetime of the pointee is tied to the lifetime of this, and delete must never be called on the pointer.

Warning

The non-const overload of this function is provided only in order to allow to call non-const member functions on the internal UDT instance. Assigning a new UDT via pointers obtained through this function is undefined behaviour.

Returns

a (const) pointer to the internal UDT instance, or nullptr.

template<typename T>
bool is() const noexcept

Check the type of the UDT.

Returns

true if T is the type of the UDT currently stored within this object, false otherwise.

std::pair<std::vector<std::size_t>, vector_double> get_connections(std::size_t n) const

Get the connections to a vertex.

This function will invoke the get_connections() member function of the UDT, which is expected to return a pair of vectors containing respectively:

  • the indices of the vertices which are connecting to n (that is, the list of vertices for which a directed edge towards n exists),

  • the weights (i.e., the migration probabilities) of the edges linking the connecting vertices to n.

This function will also run sanity checks on the output of the get_connections() member function of the UDT.

Parameters

n – the index of the vertex whose incoming connections’ details will be returned.

Returns

a pair of vectors describing n’s incoming connections.

Throws
  • std::invalid_argument – if the sizes of the returned vectors differ, or if any element of the second vector is not in the \([0.,1.]\) range.

  • unspecified – any exception thrown by the get_connections() member function of the UDT.

void push_back()

Add a vertex.

This member function will invoke the push_back() member function of the UDT, which is expected to add a new vertex to the topology, assigning it the next available index and establishing connections to other vertices.

Throws

unspecified – any exception thrown by the push_back() member function of the UDT.

void push_back(unsigned n)

Add multiple vertices.

This member function will call push_back() n times.

Parameters

n – the number of times push_back() will be called.

Throws

unspecified – any exception thrown by push_back().

bgl_graph_t to_bgl() const

New in version 2.15.

Convert to a Boost graph.

If the UDT satisfies pagmo::has_to_bgl, then this member function will return the output of its to_bgl() member function. Otherwise, an exception will be raised.

This function is meant to export a representation of the current state of the topology as a pagmo::bgl_graph_t object (that is, as a graph object from the Boost Graph Library).

Returns

a representation of this as a Boost graph object.

Throws
std::string get_name() const

Get the name of this topology.

If the UDT satisfies pagmo::has_name, then this member function will return the output of its get_name() member function. Otherwise, an implementation-defined name based on the type of the UDT will be returned.

Returns

the name of this topology.

Throws

unspecified – any exception thrown by copying an std::string object.

std::string get_extra_info() const

Extra info for this topology.

If the UDT satisfies pagmo::has_extra_info, then this member function will return the output of its get_extra_info() member function. Otherwise, an empty string will be returned.

Returns

extra info about the UDT.

Throws

unspecified – any exception thrown by the get_extra_info() member function of the UDT, or by copying an std::string object.

bool is_valid() const

Check if this topology is in a valid state.

Returns

false if this was moved from, true otherwise.

std::type_index get_type_index() const

New in version 2.15.

Get the type of the UDT.

This function will return the type of the UDT stored within this topology instance.

Returns

the type of the UDT.

const void *get_ptr() const
void *get_ptr()

New in version 2.15.

Get a pointer to the UDT.

These functions will return a raw (const) pointer to the internal UDT instance. Differently from the extract() overloads, these functions do not require to pass the correct type in input. It is however the user’s responsibility to cast the returned void pointer to the correct type.

Note

The returned value is a raw non-owning pointer: the lifetime of the pointee is tied to the lifetime of this, and delete must never be called on the pointer.

Note

The ability to extract a mutable pointer is provided only in order to allow to call non-const methods on the internal UDT instance. Assigning a new UDT via this pointer is undefined behaviour.

Returns

a pointer to the internal UDT.

Types

using bgl_graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, double, boost::no_property, boost::listS>

New in version 2.15.

This type is a boost::adjacency_list from the Boost Graph Library (BGL), and it is used as an export format for user-defined topologies (UDTs).

Specifically, UDTs can (optionally) implement a to_bgl() member function which will return an object of this type representing the internal state of the topology as a weighted directed graph.

Functions

std::ostream &operator<<(std::ostream &os, const topology &t)

Stream insertion operator.

This function will direct to os a human-readable representation of the input topology t.

Parameters
  • os – the input std::ostream.

  • t – the topology that will be directed to os.

Returns

a reference to os.

Throws

unspecified – any exception thrown by querying various properties of the topology and directing them to os.

Associated type traits

template<typename T>
class has_get_connections

The value of this type trait will be true if T provides a member function with signature:

std::pair<std::vector<std::size_t>, vector_double> get_connections(std::size_t) const;

The get_connections() member function is part of the interface for the definition of a topology.

static const bool value

The value of the type trait.

template<typename T>
class has_push_back

The value of this type trait will be true if T provides a member function with signature:

void push_back();

The push_back() member function is part of the interface for the definition of a topology.

static const bool value

The value of the type trait.

template<typename T>
class has_to_bgl

New in version 2.15.

The value of this type trait will be true if T provides a member function with signature:

bgl_graph_t to_bgl() const;

The to_bgl() member function is part of the optional interface for the definition of a topology.

static const bool value

The value of the type trait.

template<typename T>
class is_udt

This type trait detects if T is a user-defined topology (or UDT).

Specifically, the value of this type trait will be true if:

static const bool value

The value of the type trait.