Package com.jgalgo.alg.traversal

Interface BfsIter<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Superinterfaces:
Iterator<V>
All Known Subinterfaces:
BfsIter.Int
public interface BfsIter<V,E> extends Iterator<V>
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<String, Integer> g = ...;
 String sourceVertex = ...;
 for (BfsIter<String, Integer> iter = BfsIter.newInstance(g, sourceVertex); iter.hasNext();) {
     String v = iter.next();
     Integer e = iter.inEdge();
     int layer = iter.layer();
     System.out.println("Reached vertex " + v + " at layer " + layer + " using edge " + e);
 }
Author:
Barak Ugav
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    BfsIter.Int
    A BFS iterator for IntGraph.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> List<Set<V>>
    bfsLayers(Graph<V,E> g, V source)
    Compute all the layers of the vertices in a graph.
    static <V, E> Graph<V,E>
    bfsTree(Graph<V,E> g, V source)
    Create a tree from all the vertices and edges traversed by a bread first search.
    static <V, E> Graph<V,E>
    bfsTree(Graph<V,E> g, V source, boolean directed)
    Create a tree from all the vertices and edges traversed by a bread first search, optionally directed or undirected.
    boolean
    hasNext()
    Check whether there is more vertices to iterate over.
    E
    lastEdge()
    Get the edge that led to the last vertex returned by next().
    int
    layer()
    Get the layer of the last vertex returned by next().
    static <V, E> BfsIter<V,E>
    newInstance(Graph<V,E> g, V source)
    Create a BFS iterator.
    static BfsIter.Int
    newInstance(IntGraph g, int source)
    Create a BFS iterator in an int graph.
    V
    next()
    Advance the iterator and return a vertex that was not visited by the iterator yet.

    Methods inherited from interface java.util.Iterator

    forEachRemaining, remove

  • Method Details

    • hasNext

      boolean hasNext()
      Check whether there is more vertices to iterate over.
      Specified by:
      hasNext in interface Iterator<V>

    • next

      V next()
      Advance the iterator and return a vertex that was not visited by the iterator yet.
      Specified by:
      next in interface Iterator<V>

    • lastEdge

      E lastEdge()
      Get the edge that led to the last vertex returned by next().

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

      Returns:
      the edge that led to the last vertex returned by next()

    • layer

      int layer()
      Get the layer of the last vertex returned by next().

      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 next() was not called yet.

      Returns:
      the layer of the last vertex returned by next().

    • newInstance

      static <V, E> BfsIter<V,E> newInstance(Graph<V,E> g, V source)
      Create a BFS iterator.

      If an IntGraph is passed as an argument BfsIter.Int is returned.

      Type Parameters:
      V - the vertices type
      E - the edges type
      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
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • newInstance

      static BfsIter.Int newInstance(IntGraph g, int source)
      Create a BFS iterator in an int graph.
      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
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • bfsTree

      static <V, E> Graph<V,E> bfsTree(Graph<V,E> g, V source)
      Create a tree from all the vertices and edges traversed by a bread first search.

      The created graph will contain only the vertices reachable from the source vertex. For each such vertex other than the source vertex, the graph will contain the edge that led to it during the search. If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

      The returned graph will be directed if the original graph is directed. In such case, the tree is directed from the source to the other vertices. To control the directionality of the returned graph, use bfsTree(Graph, Object, boolean).

      If an IntGraph is passed as an argument, IntGraph is returned.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      source - a vertex in the graph from which the search will start from
      Returns:
      a tree graph that contains all the vertices and edges traversed by a bread first search rooted at the source vertex
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • bfsTree

      static <V, E> Graph<V,E> bfsTree(Graph<V,E> g, V source, boolean directed)
      Create a tree from all the vertices and edges traversed by a bread first search, optionally directed or undirected.

      The created graph will contain only the vertices reachable from the source vertex. For each such vertex other than the source vertex, the graph will contain the edge that led to it during the search. If there are \(k\) reachable vertices, the graph will contain \(k-1\) edges.

      If an IntGraph is passed as an argument, IntGraph is returned.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      source - a vertex in the graph from which the search will start from
      directed - if true the returned tree will be directed. If the original graph was undirected and a directed tree is created, the edges in the tree will be directed from the source towards the other vertices
      Returns:
      a tree graph that contains all the vertices and edges traversed by a bread first search rooted at the source vertex
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • bfsLayers

      static <V, E> List<Set<V>> bfsLayers(Graph<V,E> g, V source)
      Compute all the layers of the vertices in a graph.

      A 'layer' is a set of vertices which have the same cardinality distance from the source vertex. The union of all the layers are all the reachable vertices from the source. The source vertex is in layer 0, and it is the only vertex in that layer. The vertices in layer \(i\) are the vertices that are reachable from the source using exactly \(i\) edges. The layers are a partition of the reachable vertices.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      source - a vertex in the graph from which the search will start from
      Returns:
      a list of sets of vertices, where each set is a layer. If g is an IntGraph the returned list will contain IntSet instances
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph