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:
    DfsIter, Wikipedia

    • Nested Class Summary

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

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods 
      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.

    • Method Detail

      • 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