Interface DfsIter<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Superinterfaces:
Iterator<V>
All Known Subinterfaces:
DfsIter.Int
public interface DfsIter<V,E> extends Iterator<V>
Depth first search (DFS) iterators static class.

The DFS iterator is used to iterate over the vertices of a graph is a depth first manner, namely it explore as far as possible along each branch before backtracking. 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 DFS iteration. 

 
 Graph<String, Integer> g = ...;
 String sourceVertex = ...;
 for (DfsIter<String, Integer> iter = DfsIter.newInstance(g, sourceVertex); iter.hasNext();) {
     String v = iter.next();
     List<E> edgePath = iter.edgePath();
     System.out.println("Reached vertex " + v + " using the edges: " + edgePath.edges());
 }
Author:
Barak Ugav
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    DfsIter.Int
    A DFS iterator for IntGraph.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> Graph<V,E>
    dfsTree(Graph<V,E> g, V source)
    Create a tree from all the vertices and edges traversed by a depth first search.
    static <V, E> Graph<V,E>
    dfsTree(Graph<V,E> g, V source, boolean directed)
    Create a tree from all the vertices and edges traversed by a depth first search, optionally directed or undirected.
    List<E>
    edgePath()
    Get the path from the source to the last vertex returned by next().
    boolean
    hasNext()
    Check whether there is more vertices to iterate over.
    static <V, E> DfsIter<V,E>
    newInstance(Graph<V,E> g, V source)
    Create a DFS iterator.
    static DfsIter.Int
    newInstance(IntGraph g, int source)
    Create a DFS iterator for 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>

    • edgePath

      List<E> edgePath()
      Get the path from the source to the last vertex returned by next().

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

      Returns:
      list of edges forming a path from the source to the last vertex returned by next(). The returned list should not be modified

    • newInstance

      static <V, E> DfsIter<V,E> newInstance(Graph<V,E> g, V source)
      Create a DFS iterator.
      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 DFS iterator that iterate over the vertices of the graph
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • newInstance

      static DfsIter.Int newInstance(IntGraph g, int source)
      Create a DFS iterator for an int graph.
      Parameters:
      g - a graph
      source - a vertex in the graph from which the search will start from
      Returns:
      a DFS iterator that iterate over the vertices of the graph
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • dfsTree

      static <V, E> Graph<V,E> dfsTree(Graph<V,E> g, V source)
      Create a tree from all the vertices and edges traversed by a depth 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 dfsTree(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 depth first search rooted at the source vertex
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph

    • dfsTree

      static <V, E> Graph<V,E> dfsTree(Graph<V,E> g, V source, boolean directed)
      Create a tree from all the vertices and edges traversed by a depth 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 depth first search rooted at the source vertex
      Throws:
      NoSuchVertexException - if the source vertex is not in the graph