Skip to main content

streaming_bfs

Function streaming_bfs 

Source
pub fn streaming_bfs(
    stream: &mut GraphStream,
    config: &StreamingBfsConfig,
) -> StreamBfsResult
Expand description

Memory-efficient multi-pass BFS over a GraphStream.

Because a streaming BFS cannot rewind the stream, we work over a snapshot of edges (the stream is fully consumed once and stored as an edge list). Pass k discovers all vertices at distance k from the source. Only the current frontier and the visited set need to be kept in memory.

ยงAlgorithm

  1. Consume the stream into an edge list (required for multi-pass).
  2. Pass 0: initialise visited = {source}, frontier = {source}, dist[source] = 0.
  3. Pass k: scan every edge; if exactly one endpoint is in the frontier and the other is unvisited, add the other to the next frontier at distance k+1.
  4. Repeat until no new vertices are discovered or max_dist is reached.