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...

Detailed Description

Function Documentation

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
• 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

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