Module games 

Random graph generators, a.k.a. games (igraph_games.h).

igraph calls its random graph models games. Every generator of this module is an associated function of Graph returning a brand new Result<Graph> (or a small result struct when the model also produces vertex types or coordinates), while the two rewiring functions are methods mutating an existing graph in place.

All the games draw their random numbers from the calling thread’s default random number generator: seed it with rng::seed to obtain reproducible graphs. Two runs with the same seed and the same arguments produce exactly the same graph. Every thread has its own default generator (see rng), so seeding is per-thread and concurrent threads never disturb each other’s streams; an independent generator of a chosen RngType can be installed for the duration of a closure with Rng::scoped:

use igraph::prelude::*;

let sample = || {
    rng::seed(42).unwrap();
    Graph::erdos_renyi_game_gnm(50, 100, false, EdgeTypeSw::Simple, false).unwrap()
};
// Same seed, same graph, even in another thread.
let other_thread = std::thread::spawn(sample).join().unwrap();
assert!(sample().is_same_graph(&other_thread).unwrap());

// A scoped Mersenne Twister leaves the default generator untouched.
let mut mt = Rng::new(RngType::Mt19937, 42).unwrap();
let g = mt.scoped(|| Graph::tree_game(20, false, RandomTreeMethod::Prufer)).unwrap();
assert!(g.is_tree(NeighborMode::All).unwrap());

Example

use igraph::{games::BarabasiOptions, prelude::*};

rng::seed(42).unwrap();
// An Erdős–Rényi G(n, m) graph: 1000 vertices, 1000 edges, simple.
let g = Graph::erdos_renyi_game_gnm(1000, 1000, false, EdgeTypeSw::Simple, false).unwrap();
let degrees = g.degree(.., NeighborMode::All, Loops::Twice).unwrap();
let mean = degrees.iter().sum::<i64>() as f64 / g.vcount() as f64;
assert_eq!(mean, 2.0); // handshake lemma: 2m / n

// A scale-free graph grown by preferential attachment.
let ba = Graph::barabasi_game(100, &BarabasiOptions::default().with_m(2)).unwrap();
assert_eq!(ba.vcount(), 100);
assert_eq!(ba.ecount(), 1 + 98 * 2); // vertex 1 has only one vertex to attach to

Provided functionality

Model	Rust	C function
Erdős–Rényi G(n, m)	Graph::erdos_renyi_game_gnm	igraph_erdos_renyi_game_gnm
Erdős–Rényi G(n, p)	Graph::erdos_renyi_game_gnp	igraph_erdos_renyi_game_gnp
Independent edge assignment	Graph::iea_game	igraph_iea_game
Barabási–Albert / Price	Graph::barabasi_game	igraph_barabasi_game
Preferential attachment with aging	Graph::barabasi_aging_game	igraph_barabasi_aging_game
Recent degree	Graph::recent_degree_game	igraph_recent_degree_game
Recent degree with aging	Graph::recent_degree_aging_game	igraph_recent_degree_aging_game
Growing random graph	Graph::growing_random_game	igraph_growing_random_game
Prescribed degree sequence	Graph::degree_sequence_game	igraph_degree_sequence_game
Random regular graph	Graph::k_regular_game	igraph_k_regular_game
Static fitness	Graph::static_fitness_game	igraph_static_fitness_game
Static power law	Graph::static_power_law_game	igraph_static_power_law_game
Chung–Lu (expected degrees)	Graph::chung_lu_game	igraph_chung_lu_game
Watts–Strogatz small world	Graph::watts_strogatz_game	igraph_watts_strogatz_game
Rewire edges	Graph::rewire_edges	igraph_rewire_edges
Rewire directed edge endpoints	Graph::rewire_directed_edges	igraph_rewire_directed_edges
Forest fire	Graph::forest_fire_game	igraph_forest_fire_game
Stochastic block model	Graph::sbm_game	igraph_sbm_game
Hierarchical SBM	Graph::hsbm_game, Graph::hsbm_list_game	igraph_hsbm_game, igraph_hsbm_list_game
Preference (block model with random types)	Graph::preference_game	igraph_preference_game
Asymmetric preference	Graph::asymmetric_preference_game	igraph_asymmetric_preference_game
Callaway traits	Graph::callaway_traits_game	igraph_callaway_traits_game
Establishment	Graph::establishment_game	igraph_establishment_game
Geometric random graph	Graph::grg_game	igraph_grg_game
Last citation	Graph::lastcit_game	igraph_lastcit_game
Cited type	Graph::cited_type_game	igraph_cited_type_game
Citing–cited type	Graph::citing_cited_type_game	igraph_citing_cited_type_game
Interconnected islands	Graph::simple_interconnected_islands_game	igraph_simple_interconnected_islands_game
Correlated graphs	Graph::correlated_game, Graph::correlated_pair_game	igraph_correlated_game, igraph_correlated_pair_game
Uniform random tree	Graph::tree_game	igraph_tree_game
Random dot product graph	Graph::dot_product_game	igraph_dot_product_game

See also

• Deterministic generators (rings, lattices, trees, famous graphs, graphs realizing a degree sequence) live in constructors, e.g. Graph::famous, Graph::square_lattice, Graph::realize_degree_sequence.
• Random bipartite graphs: Graph::bipartite_game_gnp, Graph::bipartite_game_gnm, Graph::bipartite_iea_game; graphs from a hierarchical random graph model: Graph::hrg_game.
• Degree-preserving randomization of an existing graph: Graph::rewire; testing whether a degree sequence is realizable at all: is_graphical.
• Random spatial graphs from given points (the deterministic counterpart of Graph::grg_game): Graph::nearest_neighbor_graph.
• Measuring what the models produce: Graph::average_path_length, Graph::transitivity_avglocal_undirected, Graph::maxdegree, power_law_fit, Graph::community_multilevel (e.g. to recover the blocks of an sbm_game).

Allowed edge types

Several generators take an allowed_edge_types argument (the C type igraph_edge_type_sw_t) controlling whether self-loops and multi-edges may be created. It accepts both the shared EdgeTypeSw enum (simple graphs, loops or multi-edges) and the AllowedEdgeTypes flag set (defined in constants and re-exported here; the graphicality tests of mixing use the very same type), which can also express loops and multi-edges together:

use igraph::{games::AllowedEdgeTypes, prelude::*};

rng::seed(7).unwrap();
let any = AllowedEdgeTypes::LOOPS | AllowedEdgeTypes::MULTI;
assert_eq!(EdgeTypeSw::Loops | EdgeTypeSw::Multi, any);
let g = Graph::erdos_renyi_game_gnm(3, 50, false, any, false).unwrap();
assert_eq!(g.ecount(), 50); // impossible without multi-edges on 3 vertices
assert!(g.has_multiple().unwrap());

Re-exports

pub use crate::constants::AllowedEdgeTypes;

Structs

AsymmetricTypedGraph

Result of Graph::asymmetric_preference_game: every vertex has an out-type and an in-type.

BarabasiAgingOptions

Options of Graph::barabasi_aging_game.

BarabasiOptions

Options of Graph::barabasi_game, with the defaults of the classic undirected Barabási–Albert model (m = 1, power = 1, A = 1, BarabasiAlgorithm::Psumtree).

GeometricGraph

Result of Graph::grg_game: a geometric random graph together with the positions of its vertices in the unit square.

RecentDegreeAgingOptions

Options of Graph::recent_degree_aging_game.

RecentDegreeOptions

Options of Graph::recent_degree_game.

TypedGraph

A random graph whose vertices carry a type (category), as produced by the type-based games (Graph::preference_game, Graph::callaway_traits_game, Graph::establishment_game).