|
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...
|
|
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
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
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
- B: add edge between two already existing vertices
- 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
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
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
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