nick.graph.util
Class BreadthFirstSearch<E>

java.lang.Object
  nick.graph.util.BreadthFirstSearch<E>

Type Parameters:

E - The type for this class would typically be numerical (Integer or Double). In some applications it might be some other class, but it is important that those classes override both the hashCode() and equals() methods.

public class BreadthFirstSearch<E>
extends java.lang.Object

A utility class designed to do a breadth first search (BFS) on a given graph.

Version:

March 23, 2009

Author:

Nick Aschenbach

Constructor Summary

BreadthFirstSearch(GraphInterface<E> the_graph)
Construct the BFS object.

Method Summary

void	bfs() Perform a depth first search.
void	bfs(java.lang.String start) Perform a depth first search from a given vertex in an iterative fashion.
void	bfs(java.lang.String start, java.lang.String dest) Perform a depth first search from a given vertex to a given vertex in an iterative fashion.
boolean	hasGraphBeenSearched()
boolean	isGraphConnected() This method compares the number of vertices on a graph with the number of vertices visited by the BFS.
boolean	pathExists(java.lang.String start, java.lang.String dest) This method finds out if two vertices are part of the same connected component.
java.lang.String	toString()
java.util.HashMap<java.lang.String,java.lang.Integer>	visitedVertices()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BreadthFirstSearch

public BreadthFirstSearch(GraphInterface<E> the_graph)

Construct the BFS object.

Parameters:

the_graph - A GraphInterface object to run the BFS on.

Method Detail

bfs

public void bfs(java.lang.String start,
                java.lang.String dest)

Perform a depth first search from a given vertex to a given vertex in an iterative fashion.

Parameters:

start - The starting point of the BFS.

dest - The ending point of the BFS.

bfs

public void bfs(java.lang.String start)

Perform a depth first search from a given vertex in an iterative fashion.

Parameters:

start - The BFS will proceed from here until all vertices are found.

bfs

public void bfs()

Perform a depth first search. This method will grab a random vertex from the graph.

visitedVertices

public java.util.HashMap<java.lang.String,java.lang.Integer> visitedVertices()

Returns:

A HashSet of visited vertices. Non-visited vertices are labeled with a -1.

isGraphConnected

public boolean isGraphConnected()

This method compares the number of vertices on a graph with the number of vertices visited by the BFS. If a graph is connected, then there should be the same number in both. Please note that this method does a BFS traversal and may reset previous BFS searches!

Returns:

True if the graph is connected and false otherwise.

hasGraphBeenSearched

public boolean hasGraphBeenSearched()

Returns:

Returns true if a BFS has been performed and false otherwise.

pathExists

public boolean pathExists(java.lang.String start,
                          java.lang.String dest)

This method finds out if two vertices are part of the same connected component. Please note that this method does a BFS traversal and may reset previous BFS searches!

Parameters:

start - The starting vertex.

dest - The destination vertex.

Returns:

True if a path exists and false otherwise.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

A string representation of this object.