pub fn streaming_bfs(
stream: &mut GraphStream,
config: &StreamingBfsConfig,
) -> StreamBfsResultExpand 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
- Consume the stream into an edge list (required for multi-pass).
- Pass 0: initialise
visited = {source},frontier = {source},dist[source] = 0. - 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.
- Repeat until no new vertices are discovered or
max_distis reached.