Struct DoulionTriangleCounter 

pub struct DoulionTriangleCounter { /* private fields */ }

Approximate streaming triangle counter using edge sampling (Doulion algorithm).

The Doulion algorithm samples each edge with probability p and counts triangles in the sampled subgraph. The triangle count is then scaled by 1/p^3 to estimate the total.

Reference

Tsourakakis et al., “Doulion: Counting Triangles in Massive Graphs with a Coin”, KDD 2009.

Implementations

impl DoulionTriangleCounter

pub fn new(sample_prob: f64, seed: u64) -> Result<Self>

Create a new Doulion triangle counter with given sampling probability.

Lower sample_prob uses less memory but gives less accurate estimates. A value of 0.1 is reasonable for graphs with millions of edges.

pub fn process_edge(&mut self, src: usize, dst: usize)

Process a new edge from the stream.

With probability p, the edge is sampled. If both endpoints are already in the sample, we check for triangles formed.

pub fn estimated_triangles(&self) -> f64

Get the estimated total number of triangles.

pub fn sampled_triangles(&self) -> usize

Get the number of sampled triangles (unscaled).

pub fn stats(&self) -> TriangleCounterStats

Get statistics about the counter.

Trait Implementations

impl Debug for DoulionTriangleCounter

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.