Utopia  2 Framework for studying models of complex & adaptive systems.
Graph
Collaboration diagram for Graph:

## Modules

Rules on Entities
Algorithms for conveniently applying function objects on entities.

GraphEntity

GraphIterators

## Functions

template<typename Graph >
Graph Utopia::Graph::create_complete_graph (const std::size_t n)
Create a complete graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_ErdosRenyi_graph (const std::size_t num_vertices, const std::size_t mean_degree, bool allow_parallel, bool self_edges, RNG &rng)
Create a Erdös-Rényi random graph. More...

template<typename Graph >
Graph Utopia::Graph::create_regular_graph (const std::size_t n, const std::size_t k, const bool oriented)
Create a regular lattice graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_KlemmEguiluz_graph (const std::size_t num_vertices, const std::size_t mean_degree, const double mu, RNG &rng)
Create a Klemm-Eguíluz scale-free small-world highly-clustered graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::BarabasiAlbert_parallel_generator (std::size_t num_vertices, std::size_t mean_degree, RNG &rng)
Generate a Barabási-Albert scale-free graph with parallel edges. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_BarabasiAlbert_graph (std::size_t num_vertices, std::size_t mean_degree, bool parallel, RNG &rng)
Create a Barabási-Albert scale-free graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_BollobasRiordan_graph (std::size_t num_vertices, double alpha, double beta, double gamma, double del_in, double del_out, RNG &rng)
Create a scale-free directed graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_WattsStrogatz_graph (const std::size_t n, const std::size_t k, const double p_rewire, const bool oriented, RNG &rng)
Create a Watts-Strogatz small-world graph. More...

template<typename Graph , typename RNG >
Graph Utopia::Graph::create_graph (const Config &cfg, RNG &rng, boost::dynamic_properties pmaps={boost::ignore_other_properties})
Create a graph from a configuration node. More...

## ◆ BarabasiAlbert_parallel_generator()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::BarabasiAlbert_parallel_generator ( std::size_t num_vertices, std::size_t mean_degree, RNG & rng )

Generate a Barabási-Albert scale-free graph with parallel edges.

This is the classic version of the generating model with a completely connected spawning network. This function generates a scale-free graph using the Barabási-Albert model. The algorithm starts with a small spawning network to which new vertices are added one at a time. Each new vertex receives a connection to mean_degree existing vertices with a probability that is proportional to the number of links of the corresponding vertex. In this version, the repeated vertices, that are added during the whole generating process, are stored. With each vertex added a uniform sample from the repeated_vertex is drawn. Each vertex thus has a probability to get selected that is proportional to the number of degrees of that vertex.

Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 num_vertices The total number of vertices mean_degree The mean degree rng The random number generator
Returns
Graph The scale-free graph

## ◆ create_BarabasiAlbert_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_BarabasiAlbert_graph ( std::size_t num_vertices, std::size_t mean_degree, bool parallel, RNG & rng )

Create a Barabási-Albert scale-free graph.

This function generates a scale-free graph using the Barabási-Albert model. The algorithm starts with a small spawning network to which new vertices are added one at a time. Each new vertex receives a connection to mean_degree existing vertices with a probability that is proportional to the number of links of the corresponding vertex.

There are two slightly different variants of the algorithm, one that creates a graph with no parallel edges and one that creates a graph with parallel edges.

Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 num_vertices The total number of vertices mean_degree The mean degree parallel Whether the graph should have parallel edges or not rng The random number generator
Returns
Graph The scale-free graph

## ◆ create_BollobasRiordan_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_BollobasRiordan_graph ( std::size_t num_vertices, double alpha, double beta, double gamma, double del_in, double del_out, RNG & rng )

Create a scale-free directed graph.

This function generates a scale-free graph using the model from Bollobás et al. Multi-edges and self-loops are not allowed. The graph is built by continuously adding new edges via preferential attachment. In each step, an edge is added in one of the following three ways:

• A: add edge from a newly added vertex to an existing one
• C: add edge from an existing vertex to a newly added vertex As the graph is directed there can be different attachment probability distributions for in-edges and out-edges. The probability for choosing a vertex as source (target) of the new edge is proportional to its current out-degree (in-degree). Each newly added vertex has a fixed initial probability to be chosen as source (target) which is proportional to del_out (del_in).
Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 n The total number of vertices alpha The probability for option 'A' beta The probability for option 'B' gamma The probability for option 'C' del_in The unnormalized attraction of newly added vertices del_out The unnormalized connectivity of newly added vertices rng The random number generator
Returns
Graph The scale-free directed graph

## ◆ create_complete_graph()

template<typename Graph >
 Graph Utopia::Graph::create_complete_graph ( const std::size_t n )

Create a complete graph.

This function creates a complete graph, i.e. one in which every vertex is connected to every other. No parallel edges are created.

Template Parameters
 Graph The graph type
Parameters
 n The total number of vertices
Returns
Graph The graph

## ◆ create_ErdosRenyi_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_ErdosRenyi_graph ( const std::size_t num_vertices, const std::size_t mean_degree, bool allow_parallel, bool self_edges, RNG & rng )

Create a Erdös-Rényi random graph.

This function uses the create_random_graph function from the boost graph library. It uses the Erdös-Rényi algorithm to generate the random graph. Sources and targets of edges are randomly selected with equal probability. Thus, every possible edge has the same probability to be created.

Note
The underlying boost::generate_random_graph function requires the total number of edges as input. In case of an undirected graph it is calculated through: num_edges = num_vertices * mean_degree / 2, in case of a directed graph through: num_edges = num_vertices * mean_degree. If the integer division of the right hand side leaves a rest, the mean degree will be slightly distorted. However, for large numbers of num_vertices this effect is negligible.
Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 num_vertices The total number of vertices mean_degree The mean degree (= mean in-degree = mean out-degree for directed graphs) allow_parallel Allow parallel edges within the graph self_edges Allows a vertex to be connected to itself rng The random number generator
Returns
Graph The random graph

## ◆ create_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_graph ( const Config & cfg, RNG & rng, boost::dynamic_properties pmaps = {boost::ignore_other_properties} )

Create a graph from a configuration node.

Select a graph creation algorithm and create the graph object a configuration node.

Template Parameters
 Graph The graph type Config The configuration node type RNG The random number generator type
Parameters
 cfg The configuration rng The random number generator pmaps Property maps that may be used by the graph creation algorithms. At this point, only the load_from_file model will make use of this, allowing to populate a weight property map.
Returns
Graph The graph

## ◆ create_KlemmEguiluz_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_KlemmEguiluz_graph ( const std::size_t num_vertices, const std::size_t mean_degree, const double mu, RNG & rng )

Create a Klemm-Eguíluz scale-free small-world highly-clustered graph.

This function generates a graph using the Klemm-Eguíluz model (Klemm & Eguíluz 2002). The algorithm starts with a small spawning network to which new vertices are added one at a time. Each new vertex receives a connection to mean_degree existing vertices with a probability that is proportional to the number of links of the corresponding vertex. With probability mu, links are instead rewired to a (possibly non-active) vertex, chosen with a probability that is proportional to its degree. Thus, for mu=1 we obtain the Barabasi-Albert linear preferential attachment model.

Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 num_vertices The total number of vertices mean_degree The mean degree mu The probability of rewiring to a random vertex rng The random number generator
Returns
Graph The scale-free graph

## ◆ create_regular_graph()

template<typename Graph >
 Graph Utopia::Graph::create_regular_graph ( const std::size_t n, const std::size_t k, const bool oriented )

Create a regular lattice graph.

This function creates a k-regular graph. The algorithm has been adapted for directed graphs, for which it can be specified whether the underlying lattice graph is oriented or not.

Template Parameters
 Graph The graph type
Parameters
 n The total number of vertices k The mean degree (= mean in-degree = mean out-degree for directed graphs) oriented (For directed graphs) whether the created lattice is oriented (only connecting to forward neighbors) or not rng The random number generator
Returns
Graph The regular graph

## ◆ create_WattsStrogatz_graph()

template<typename Graph , typename RNG >
 Graph Utopia::Graph::create_WattsStrogatz_graph ( const std::size_t n, const std::size_t k, const double p_rewire, const bool oriented, RNG & rng )

Create a Watts-Strogatz small-world graph.

This function creates a small-world graph using the Watts-Strogatz model. It creates a k-regular graph and relocates vertex connections with a given probability. The algorithm has been adapted for directed graphs, for which it can be specified whether the underlying lattice graph is oriented or not.

Template Parameters
 Graph The graph type RNG The random number generator type
Parameters
 n The total number of vertices k The mean degree (= mean in-degree = mean out-degree for directed graphs) p_rewire The rewiring probability oriented (for directed graphs) Whether the underlying starting graph is oriented (only connecting to forward neighbors) or not RNG The random number generator
Returns
Graph The small-world graph