net.datastructures

Class FindPathDFS<V,E>

java.lang.Object

net.datastructures.DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

net.datastructures.FindPathDFS<V,E>

public class FindPathDFS<V,E>
extends DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

Class specializing DFS to find a path between a start vertex and a target vertex. It assumes the target vertex is passed as the info object to the execute method. It returns an iterable list of the vertices and edges comprising the path from start to info. The returned path is empty if info is unreachable from start.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	done
protected PositionList<Position>	path

Fields inherited from class net.datastructures.DFS

graph, info, start, STATUS, UNVISITED, VISITED, visitResult

Constructor Summary

Constructors

Constructor and Description
FindPathDFS()

Method Summary

Modifier and Type	Method and Description
java.lang.Iterable<Position>	finalResult(java.lang.Iterable<Position> r) Returns the final result of the DFS execute method.
protected void	finishVisit(Vertex<V> v) Called after we finish the visit for a vertex (v).
protected boolean	isDone() Determines whether the traversal is done early.
void	setup() Setup method to initialize the path.
protected void	startVisit(Vertex<V> v) Called when we encounter a vertex (v).
protected void	traverseDiscovery(Edge<E> e, Vertex<V> from) Called when we traverse a discovery edge (e) from a vertex (from).

Methods inherited from class net.datastructures.DFS

dfsTraversal, execute, 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 PositionList<Position> path

done

protected boolean done

Constructor Detail

FindPathDFS

public FindPathDFS()

Method Detail

setup

public void setup()

Setup method to initialize the path.

Overrides:

setup in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

startVisit

protected void startVisit(Vertex<V> v)

Description copied from class: DFS

Called when we encounter a vertex (v).

Overrides:

startVisit in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

finishVisit

protected void finishVisit(Vertex<V> v)

Description copied from class: DFS

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

Overrides:

finishVisit in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

traverseDiscovery

protected void traverseDiscovery(Edge<E> e,
                                 Vertex<V> from)

Description copied from class: DFS

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

Overrides:

traverseDiscovery in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

isDone

protected boolean isDone()

Description copied from class: DFS

Determines whether the traversal is done early.

Overrides:

isDone in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>

finalResult

public java.lang.Iterable<Position> finalResult(java.lang.Iterable<Position> r)

Description copied from class: DFS

Returns the final result of the DFS execute method.

Overrides:

finalResult in class DFS<V,E,Vertex<V>,java.lang.Iterable<Position>>