nick.graph.util
Class DepthFirstSearch<E>

java.lang.Object
  nick.graph.util.DepthFirstSearch<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 DepthFirstSearch<E>
extends java.lang.Object

A utility class designed to do a depth first search (DFS) on a given graph.

Version:

March 23, 2009

Author:

Nick Aschenbach

Constructor Summary

DepthFirstSearch(GraphInterface<E> the_graph)
Construct the DFS object.

Method Summary

void	dfs() Perform a depth first search.
void	dfs(java.lang.String start) Perform a depth first search from a given vertex in an iterative fashion.
void	dfs(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 DFS.
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

DepthFirstSearch

public DepthFirstSearch(GraphInterface<E> the_graph)

Construct the DFS object.

Parameters:

the_graph - A GraphInterface object to run the DFS on.

Method Detail

dfs

public void dfs(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 DFS.

dest - The ending point of the DFS.

dfs

public void dfs(java.lang.String start)

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

Parameters:

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

dfs

public void dfs()

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 DFS. If a graph is connected, then there should be the same number in both. Please note that this method does a DFS traversal and may reset previous DFS searches!

Returns:

True if the graph is connected and false otherwise.

hasGraphBeenSearched

public boolean hasGraphBeenSearched()

Returns:

Returns true if a DFS 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