Module forestfire 

Forest fire random-graph generator (ALGO-GN-006).

Counterpart of igraph_forest_fire_game() in references/igraph/src/games/forestfire.c:106-257.

Model

Leskovec–Kleinberg–Faloutsos (KDD’05). Nodes are added one at a time. Each new node v:

1. picks ambs ambassador vertices uniformly at random from the already-present nodes and cites each of them;
2. for every ambassador a, draws x ~ Geom(1 − p) outgoing and y ~ Geom(1 − r·p) incoming neighbours of a (where p is the forward burning probability and r the backward factor), cites those still-unvisited neighbours, and pushes them onto the burn queue;
3. the burn continues breadth-first until the queue empties.

The corrected variant from https://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf is the one mirrored here — the published paper algorithm uses mean = p/(1−p) which igraph corrects to a single geometric draw.

Validation

• fw_prob ∈ [0, 1) — strict upper bound so the geometric draw is finite (geometric mean is p/(1−p)).
• bw_factor · fw_prob ∈ [0, 1) — same guard for the incoming draw.
• ambs ≥ 0. ambs = 0 returns an edgeless graph of n isolated vertices, matching upstream.

Algorithm cost

Asymptotic cost is hard to pin down because the burn radius depends on the in/out-neighbourhood sizes built up so far. In the sparse regime (p away from 1) the expected work per new node is bounded by the geometric tail, giving roughly O(n / (1 − p)²) overall. Memory is O(n + |E|): two per-vertex Vec<u32> adjacency arrays plus the edge buffer.

Determinism

Fully deterministic in (n, fw_prob, bw_factor, ambs, directed, seed) via SplitMix64.

Functions

forest_fire_game

Generate a forest-fire-model random graph on n vertices.