Package com.jgalgo.alg.traversal

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:

BfsIter, Wikipedia

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 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>

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