Package com.jgalgo

Interface BFSIter

All Superinterfaces:

IntIterator, Iterator<Integer>, PrimitiveIterator<Integer,IntConsumer>, PrimitiveIterator.OfInt

public interface BFSIter
extends IntIterator

Bread first search (BFS) iterator.

The BFS iterator is used to iterate over the vertices of a graph in a bread first manner, namely by the cardinality distance of the vertices from some source(s) vertex. The iterator will visit every vertex \(v\) for which there is a path from the source(s) to \(v\). Each such vertex will be visited exactly once.

The graph should not be modified during the BFS iteration.

 
 Graph g = ...;
 int sourceVertex = ...;
 for (BFSIter iter = BFSIter.newInstance(g, sourceVertex); iter.hasNext();) {
     int v = iter.nextInt();
     int e = iter.inEdge();
     int layer = iter.layer();
     System.out.println("Reached vertex " + v + " at layer " + layer + " using edge " + e);
 }
 

Author:

Barak Ugav

See Also:

DFSIter, Wikipedia

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.PrimitiveIterator

PrimitiveIterator.OfDouble, PrimitiveIterator.OfInt, PrimitiveIterator.OfLong

Method Summary

Modifier and Type	Method	Description
boolean	hasNext()	Check whether there is more vertices to iterate over.
int	lastEdge()	Get the edge that led to the last vertex returned by nextInt().
int	layer()	Get the layer of the last vertex returned by nextInt().
static BFSIter	newInstance(Graph g, int source)	Create a BFS iterator rooted at a single source vertex.
static BFSIter	newInstanceBackward(Graph g, int source)	Create a backward BFS iterator rooted at a single source vertex.
int	nextInt()	Advance the iterator and return a vertex that was not visited by the iterator yet.

Methods inherited from interface it.unimi.dsi.fastutil.ints.IntIterator

forEachRemaining, forEachRemaining, next, skip

Methods inherited from interface java.util.Iterator

remove

Methods inherited from interface java.util.PrimitiveIterator.OfInt

forEachRemaining

Method Detail

newInstance

static BFSIter newInstance(Graph g,
                           int source)

Create a BFS iterator rooted at a single source vertex.

Parameters:

g - a graph

source - a vertex in the graph from which the search will start from

Returns:

a BFS iterator that iterate over the vertices of the graph

newInstanceBackward

static BFSIter newInstanceBackward(Graph g,
                                   int source)

Create a backward BFS iterator rooted at a single source vertex.

The regular BFS uses the out-edges of each vertex to explore its neighbors, while the backward BFS uses the in-edges to do so.

Parameters:

g - a graph

source - a vertex in the graph from which the search will start from

Returns:

a BFS iterator that iterate over the vertices of the graph using the in-edges

hasNext

boolean hasNext()

Check whether there is more vertices to iterate over.

Specified by:

hasNext in interface Iterator<Integer>

nextInt

int nextInt()

Advance the iterator and return a vertex that was not visited by the iterator yet.

Specified by:

nextInt in interface IntIterator

Specified by:

nextInt in interface PrimitiveIterator.OfInt

lastEdge

int lastEdge()

Get the edge that led to the last vertex returned by nextInt().

The behavior is undefined if nextInt() was not called yet.

Returns:

the edge that led to the last vertex returned by nextInt()

layer

int layer()

Get the layer of the last vertex returned by nextInt().

The layer of a vertex is the cardinality distance, the number of edges in the path, from the source(s) to the vertex.

The behavior is undefined if nextInt() was not called yet.

Returns:

the layer of the last vertex returned by nextInt().