Base topology class. More...

#include <base.h>

Inheritance diagram for pagmo::topology::base:

Public Types
typedef graph_type::vertices_size_type	vertices_size_type
	Vertices size type.

typedef graph_type::edges_size_type	edges_size_type
	Edges size type.

Public Member Functions
	base ()
	Default constructor. More...

	base (const base &)
	Copy constructor. More...

base &	operator= (const base &)
	Assignment operator. More...

virtual base_ptr	clone () const =0
	Clone method. More...

virtual	~base ()
	Trivial destructor. More...

High-level graph access and manipulation methods.
vertices_size_type	get_number_of_vertices () const
	Get number of vertices. More...

edges_size_type	get_number_of_edges () const
	Get number of edges. More...

void	push_back ()
	Push back vertex. More...

double	get_average_shortest_path_length () const
	Calculate average path length. More...

double	get_clustering_coefficient () const
	Calculate clustering coefficient.

std::vector< double >	get_degree_distribution () const
	Constructs the Degree Distribution.

bool	are_adjacent (const vertices_size_type &, const vertices_size_type &) const
	Return true if two vertices are adjacent. More...

bool	are_inv_adjacent (const vertices_size_type &, const vertices_size_type &) const
	Return true if two vertices are inversely adjacent. More...

std::vector< vertices_size_type >	get_v_adjacent_vertices (const vertices_size_type &) const
	Return vector of adjacent vertices. More...

std::vector< vertices_size_type >	get_v_inv_adjacent_vertices (const vertices_size_type &) const
	Return vector of inversely adjacent vertices. More...

edges_size_type	get_num_adjacent_vertices (const vertices_size_type &) const
	Return the number of adjacent vertices. More...

edges_size_type	get_num_inv_adjacent_vertices (const vertices_size_type &) const
	Return the number of inversely adjacent vertices. More...

void	set_weight (double)
	Sets the migration probability. More...

void	set_weight (const vertices_size_type &, double)
	Sets the migration probability. More...

void	set_weight (const vertices_size_type &, const vertices_size_type &, double)
	Sets the migration probability. More...

double	get_weight (const vertices_size_type &, const vertices_size_type &) const
	Get the migration probability. More...

Protected Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, edge_properties, boost::no_property, boost::listS >	graph_type

typedef boost::graph_traits< graph_type >::vertex_iterator	v_iterator
	Iterator over the vertices.

typedef boost::graph_traits< graph_type >::edge_iterator	e_iterator
	Iterator over the edges.

typedef boost::graph_traits< graph_type >::adjacency_iterator	a_iterator
	Iterator over adjacent vertices.

typedef graph_type::inv_adjacency_iterator	ia_iterator
	Iterator over inversely adjacent vertices.

typedef boost::graph_traits< graph_type >::vertex_descriptor	v_descriptor
	Vertex descriptor.

typedef boost::graph_traits< graph_type >::edge_descriptor	e_descriptor
	Edge descriptor.

Protected Member Functions
Low-level graph access and manipulation methods.
void	add_vertex ()
	Add a vertex. More...

std::pair< a_iterator, a_iterator >	get_adjacent_vertices (const vertices_size_type &) const
	Return iterator range to adjacent vertices. More...

std::pair< ia_iterator, ia_iterator >	get_inv_adjacent_vertices (const vertices_size_type &) const
	Return iterator range to inversely adjacent vertices. More...

void	add_edge (const vertices_size_type &, const vertices_size_type &)
	Add an edge. More...

void	remove_edge (const vertices_size_type &, const vertices_size_type &)
	Remove an edge. More...

void	remove_all_edges ()
	Remove all edges. More...

std::pair< v_iterator, v_iterator >	get_vertices () const
	Return iterator range to vertices. More...

virtual void	connect (const vertices_size_type &idx)=0
	Establish connections between islands during a push_back() operation. More...

Friends
class	boost::serialization::access

Input/output.
virtual std::string	get_name () const
	Get name of the topology. More...

std::string	human_readable_terse () const
	Return terse human readable representation. More...

std::string	human_readable () const
	Return complete human readable representation. More...

virtual std::string	human_readable_extra () const
	Return extra information for human readable representation. More...

Detailed Description

Base topology class.

This class represents a topology connecting islands in an archipelago using a directed graph in which the vertices are uniquely identified by an integer index representing:

the order of creation of the vertex (i.e., the first vertex added has index 0, the second one has integer 1 and so on),
the positional index of the island in the archipelago (i.e., the first island added to the archipelago corresponds to vertex 0, the second one to vertex 1 and so on).

The internal implementation of the graph uses the Boost graph library, and most methods of this class are thin wrappers around the corresponding Boost graph functions.

The user is required to implement the connect() method, which will be called upon island insertion in an archipelago to establish the connection(s) between the newly-added island and the islands already present in the archipelago.

The re-implementable methods are:

get_name(), to give a user-friendly name to the derived topology (otherwise the mangled C++ name will be used),
human_readable_extra(), to provide extra, topology-specific information when printing the topology to a stream.

See also: http://www.boost.org/doc/libs/release/libs/graph/doc/

Author: Francesco Biscani (blues.nosp@m.carn.nosp@m.i@gma.nosp@m.il.c.nosp@m.om); Marek Ruciński (marek.nosp@m..ruc.nosp@m.inski.nosp@m.@gma.nosp@m.il.co.nosp@m.m)

Definition at line 75 of file topology/base.h.

Constructor & Destructor Documentation

pagmo::topology::base::base ( )

Default constructor.

Will build an empty topology.

Definition at line 46 of file topology/base.cpp.

pagmo::topology::base::base ( const base & t )

Copy constructor.

Will deep-copy all members.

Parameters

[in] t topology::base to be copied.

Definition at line 53 of file topology/base.cpp.

pagmo::topology::base::~base ( )

virtual

Trivial destructor.

No side effects.

Definition at line 75 of file topology/base.cpp.

Member Function Documentation

void pagmo::topology::base::add_edge	(	const vertices_size_type &	n,
		const vertices_size_type &	m
	)

protected

Add an edge.

Add an edge connecting n to m. Will fail if are_adjacent() returns true.

Parameters

[in]	n	index of the first vertex.
[in]	m	index of the second vertex.

Definition at line 298 of file topology/base.cpp.

void pagmo::topology::base::add_vertex ( )

protected

Add a vertex.

Add a new, unconnected vertex to the topology.

Definition at line 162 of file topology/base.cpp.

bool pagmo::topology::base::are_adjacent	(	const vertices_size_type &	n,
		const vertices_size_type &	m
	)		const

Return true if two vertices are adjacent.

The direction of the edge must be n -> m. Will fail if either n or m are not in the topology.

Parameters

[in]	n	first vertex.
[in]	m	second vertex.

Returns: true if the two vertices are connected, false otherwise.

Definition at line 212 of file topology/base.cpp.

bool pagmo::topology::base::are_inv_adjacent	(	const vertices_size_type &	n,
		const vertices_size_type &	m
	)		const

Return true if two vertices are inversely adjacent.

The direction must be m -> n. Will fail if either n or m are not in the topology.

Parameters

[in]	n	first vertex.
[in]	m	second vertex.

Returns: true if the two vertices are inversely connected, false otherwise.

Definition at line 244 of file topology/base.cpp.

virtual base_ptr pagmo::topology::base::clone ( ) const

pure virtual

Clone method.

Provided that the derived topology implements properly the copy constructor, virtually all implementations of this method will look like this:

return base_ptr(new derived_topology(*this));

Returns: topology::base_ptr to a copy of this.

Implemented in pagmo::topology::watts_strogatz, pagmo::topology::ageing_clustered_ba, pagmo::topology::barabasi_albert, pagmo::topology::erdos_renyi, pagmo::topology::clustered_ba, pagmo::topology::custom, pagmo::topology::pan, pagmo::topology::fully_connected, pagmo::topology::rim, pagmo::topology::unconnected, pagmo::topology::one_way_ring, pagmo::topology::ring, and pagmo::topology::hypercube.

virtual void pagmo::topology::base::connect ( const vertices_size_type & idx )

protectedpure virtual

Establish connections between islands during a push_back() operation.

This method will be called by push_back() after a vertex has been added to the graph. The purpose of this method is to connect the newly-added vertex to other vertices according to the properties of the topology.

Parameters

[in] idx index of the newly-added vertex.

Implemented in pagmo::topology::watts_strogatz, pagmo::topology::ageing_clustered_ba, pagmo::topology::barabasi_albert, pagmo::topology::erdos_renyi, pagmo::topology::clustered_ba, pagmo::topology::custom, pagmo::topology::pan, pagmo::topology::fully_connected, pagmo::topology::rim, pagmo::topology::unconnected, pagmo::topology::one_way_ring, pagmo::topology::ring, and pagmo::topology::hypercube.

std::pair< base::a_iterator, base::a_iterator > pagmo::topology::base::get_adjacent_vertices ( const vertices_size_type & idx ) const

protected

Return iterator range to adjacent vertices.

Adjacent vertices are those connected from the interested vertex.

Parameters

[in] idx index of the interested vertex.

Returns: iterator range over the adjacent vertices.

Definition at line 183 of file topology/base.cpp.

double pagmo::topology::base::get_average_shortest_path_length ( ) const

Calculate average path length.

Calculate and return the average path length of the underlying graph representation using Johnson's all pairs shortest paths algorithm. All edges are given equal weight 1. If a node is unconnected, its distance from any other node will be the highest value representable by the C++ int type. The average path length is calculated as the mean value of the shortest paths between all pairs of vertices.

Returns: the average path length for the topology.

See also: http://en.wikipedia.org/wiki/Johnson's_algorithm; http://www.boost.org/doc/libs/release/libs/graph/doc/johnson_all_pairs_shortest.html

Definition at line 462 of file topology/base.cpp.

std::pair< base::ia_iterator, base::ia_iterator > pagmo::topology::base::get_inv_adjacent_vertices ( const vertices_size_type & idx ) const

protected

Return iterator range to inversely adjacent vertices.

Inversely adjacent vertices are those connected to the interested vertex.

Parameters

[in] idx index of the interested vertex.

Returns: iterator range over the inversely adjacent vertices.

Definition at line 261 of file topology/base.cpp.

std::string pagmo::topology::base::get_name ( ) const

virtual

Get name of the topology.

Default implementation will return the class' mangled C++ name.

Returns: name of the topology.

Reimplemented in pagmo::topology::watts_strogatz, pagmo::topology::ageing_clustered_ba, pagmo::topology::barabasi_albert, pagmo::topology::erdos_renyi, pagmo::topology::clustered_ba, pagmo::topology::custom, pagmo::topology::pan, pagmo::topology::fully_connected, pagmo::topology::rim, pagmo::topology::unconnected, pagmo::topology::one_way_ring, pagmo::topology::ring, and pagmo::topology::hypercube.

Definition at line 86 of file topology/base.cpp.

base::edges_size_type pagmo::topology::base::get_num_adjacent_vertices ( const vertices_size_type & idx ) const

Return the number of adjacent vertices.

Adjacent vertices are those connected from the interested vertex.

Parameters

[in] idx index of the interested vertex.

Returns: number of adjacent vertices.

Definition at line 229 of file topology/base.cpp.

base::edges_size_type pagmo::topology::base::get_num_inv_adjacent_vertices ( const vertices_size_type & idx ) const

Return the number of inversely adjacent vertices.

Returns: number of inversely adjacent vertices.

Definition at line 285 of file topology/base.cpp.

base::edges_size_type pagmo::topology::base::get_number_of_edges ( ) const

Get number of edges.

Returns: total number of edges in the graph.

Definition at line 445 of file topology/base.cpp.

base::vertices_size_type pagmo::topology::base::get_number_of_vertices ( ) const

Get number of vertices.

Returns: total number of vertices in the graph.

Definition at line 436 of file topology/base.cpp.

std::vector< base::vertices_size_type > pagmo::topology::base::get_v_adjacent_vertices ( const vertices_size_type & idx ) const

Return vector of adjacent vertices.

Adjacent vertices are those connected from the interested index.

Parameters

[in] idx interested index.

Returns: vector of adjacent indices.

Definition at line 197 of file topology/base.cpp.

std::vector< base::vertices_size_type > pagmo::topology::base::get_v_inv_adjacent_vertices ( const vertices_size_type & idx ) const

Return vector of inversely adjacent vertices.

Inversely adjacent vertices are those connected to the interested index.

Parameters

[in] idx index of the interested vertex.

Returns: vector of inversely adjacent indices.

Definition at line 275 of file topology/base.cpp.

std::pair< base::v_iterator, base::v_iterator > pagmo::topology::base::get_vertices ( ) const

protected

Return iterator range to vertices.

Return a pair of iterators, the first one to the first vertex of the graph, the second one to the end of the graph.

Returns: begin/end iterator range for the graph.

Definition at line 427 of file topology/base.cpp.

double pagmo::topology::base::get_weight	(	const vertices_size_type &	n,
		const vertices_size_type &	m
	)		const

Get the migration probability.

Returns the weight (migration probability) for the edge going from vertex n to m

Parameters

[in]	n	index of the first vertex in the graph
[in]	m	index of the second vertex in the graph
[in]	w	weight (migration probability) for given edge

Definition at line 386 of file topology/base.cpp.

std::string pagmo::topology::base::human_readable ( ) const

Return complete human readable representation.

Will return a formatted string containing:

the output of human_readable_terse(),
the list of vertices and edges in a DOT-like syntax.

Returns: string containing complete human readable representation of the topology.

Definition at line 118 of file topology/base.cpp.

std::string pagmo::topology::base::human_readable_extra ( ) const

protectedvirtual

Return extra information for human readable representation.

Return extra topology-dependent information that will be displayed when calling human_readable(). Default implementation will return an empty string.

Returns: string containing extra information for human readable representation.

Reimplemented in pagmo::topology::ageing_clustered_ba, pagmo::topology::barabasi_albert, pagmo::topology::erdos_renyi, and pagmo::topology::clustered_ba.

Definition at line 151 of file topology/base.cpp.

std::string pagmo::topology::base::human_readable_terse ( ) const

Return terse human readable representation.

Will return a formatted string containing:

the output of get_name(),
the number of vertices,
the output of human_readable_extra().

Returns: string containing terse human readable representation of the topology.

Definition at line 100 of file topology/base.cpp.

base & pagmo::topology::base::operator= ( const base & t )

Assignment operator.

Will perform a deep copy of all members.

Parameters

[in] t topology::base which will be copied into this.

Returns: reference to this.

Definition at line 63 of file topology/base.cpp.

void pagmo::topology::base::push_back ( )

Push back vertex.

This method will add a vertex and will then call connect() to establish the connections between the newly-added node and the existing nodes in the graph.

Definition at line 554 of file topology/base.cpp.

void pagmo::topology::base::remove_all_edges ( )

protected

Remove all edges.

Remove all connections between vertices.

Definition at line 414 of file topology/base.cpp.

void pagmo::topology::base::remove_edge	(	const vertices_size_type &	n,
		const vertices_size_type &	m
	)

protected

Remove an edge.

Remove the edge connecting n to m. Will fail if are_adjacent() returns false.

Parameters

[in]	n	index of the first vertex.
[in]	m	index of the second vertex.

Definition at line 402 of file topology/base.cpp.

void pagmo::topology::base::set_weight ( double w )

Sets the migration probability.

Set the weight (migration probability) for each edge in the topology

Parameters

[in] w weight (migration probability) of each edge in the topology

Definition at line 339 of file topology/base.cpp.

void pagmo::topology::base::set_weight	(	const vertices_size_type &	n,
		double	w
	)

Sets the migration probability.

Set the weight (migration probability) for each edge outgoing from the vertex n.

Parameters

[in]	n	index of the first vertex in the graph
[in]	w	weight (migration probability) for each out-edge from vertex n.

Definition at line 353 of file topology/base.cpp.

void pagmo::topology::base::set_weight	(	const vertices_size_type &	n,
		const vertices_size_type &	m,
		double	w
	)

Sets the migration probability.

Set the weight (migration probability) for edge going from n to m

Parameters

[in]	n	index of the first vertex in the graph
[in]	m	index of the second vertex in the graph
[in]	w	weight (migration probability) for given edge

Definition at line 369 of file topology/base.cpp.

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Friends

Input/output.

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation