net.datastructures
Class FindPathDFS

java.lang.Object
  net.datastructures.DFS
      net.datastructures.FindPathDFS

public class FindPathDFS

extends DFS

This class specializes DFS to find a path between the start vertex and a given target vertex.

Field Summary

protected boolean	done
protected List	path
protected Vertex	target

Fields inherited from class net.datastructures.DFS

G, STATUS, UNVISITED, VISITED, visitResult

Constructor Summary

FindPathDFS()

Method Summary

Object	execute(Graph g, Vertex start, Object info) Execute a depth first search traversal on graph g, starting from a vertex v, optionally passing in an information object (info)
protected void	finishVisit(Vertex v) Called after we finish the visit for a vertex (v).
protected boolean	isDone() Determines whether the traversal is done early.
protected void	startVisit(Vertex v) Called when we encounter a vertex (v).
protected void	traverseDiscovery(Edge e, Vertex from) Called when we traverse a discovery edge (e) from a vertex (from).

Methods inherited from class net.datastructures.DFS

dfsTraversal, init, initResult, isVisited, result, traverseBack, unVisit, visit

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

path

protected List path

done

protected boolean done

target

protected Vertex target

Constructor Detail

FindPathDFS

public FindPathDFS()

Method Detail

execute

public Object execute(Graph g,
                      Vertex start,
                      Object info)

Description copied from class: DFS

Execute a depth first search traversal on graph g, starting from a vertex v, optionally passing in an information object (info)

Specified by:

execute in class DFS

Parameters:

info - target vertex of the path

g - Input graph.

start - Start vertex of the traversal.

Returns:

Iterator of the vertices and edges in a path from the start vertex to the target vertex, or an empty iterator if no such path exists in the graph

startVisit

protected void startVisit(Vertex v)

Description copied from class: DFS

Called when we encounter a vertex (v).

Overrides:

startVisit in class DFS

finishVisit

protected void finishVisit(Vertex v)

Description copied from class: DFS

Called after we finish the visit for a vertex (v).

Overrides:

finishVisit in class DFS

traverseDiscovery

protected void traverseDiscovery(Edge e,
                                 Vertex from)

Description copied from class: DFS

Called when we traverse a discovery edge (e) from a vertex (from).

Overrides:

traverseDiscovery in class DFS

isDone

protected boolean isDone()

Description copied from class: DFS

Determines whether the traversal is done early.

Overrides:

isDone in class DFS