Package com.gengoai.graph.algorithms

Class BreadthFirstSearch<V>

java.lang.Object

com.gengoai.graph.algorithms.BreadthFirstSearch<V>

Type Parameters:

V - the vertex type parameter

All Implemented Interfaces:

GraphSearch<V>, Serializable

public class BreadthFirstSearch<V>
extends Object

Performs a breadth first search to find a path between the given starting point and ending point.

Author:

David B. Bracewell

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor	Description
BreadthFirstSearch(Graph<V> graph)	Instantiates a new BreadthFirstSearch.

Method Summary

Modifier and Type	Method	Description
protected void	add(Deque<List<Tuple2<V,Edge<V>>>> pathes, List<Tuple2<V,Edge<V>>> path)
protected List<Tuple2<V,Edge<V>>>	next(Deque<List<Tuple2<V,Edge<V>>>> pathes)
List<Edge<V>>	search(V startingPoint, V endingPoint)	Searches for a path from the given starting point to the given ending point

Methods inherited from class java.lang.Object

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

Constructor Detail

BreadthFirstSearch

public BreadthFirstSearch(Graph<V> graph)

Instantiates a new BreadthFirstSearch.

Parameters:

graph - the graph to search

Method Detail

add

protected void add(Deque<List<Tuple2<V,Edge<V>>>> pathes,
                   List<Tuple2<V,Edge<V>>> path)

next

protected List<Tuple2<V,Edge<V>>> next(Deque<List<Tuple2<V,Edge<V>>>> pathes)

search

public final List<Edge<V>> search(V startingPoint,
                                  V endingPoint)

Description copied from interface: GraphSearch

Searches for a path from the given starting point to the given ending point

Specified by:

search in interface GraphSearch<V>

Parameters:

startingPoint - the starting point

endingPoint - the ending point

Returns:

the path as a list of edges (empty list if no path exists)