cusack.hcg.graph.algorithm.standard

Class BreadthFirstSearchSkeletonAlgorithm

java.lang.Object

cusack.hcg.graph.algorithm.AbstractAlgorithm<PuzzleInstance>

cusack.hcg.graph.algorithm.standard.BreadthFirstSearchSkeletonAlgorithm

All Implemented Interfaces:

AlgorithmInterface<PuzzleInstance>

Direct Known Subclasses:

ContainsTriangle, CountShortestPathsAlgorithm, EliminateDegree2Vertices, IsBipartite, ShortestPathAlgorithm

public abstract class BreadthFirstSearchSkeletonAlgorithm
extends AbstractAlgorithm<PuzzleInstance>

A skeleton Breadth First Search algorithm. It computes the parents and distances for each vertex. This implementation is based on the one from Chapter 5 of "The Algorithm Design Manual" by Steven Skiena.

Author:

cusack

Constructor Summary

Constructors

Constructor and Description
BreadthFirstSearchSkeletonAlgorithm()

Method Summary

Modifier and Type	Method and Description
java.lang.String	argumentFormat() Describe how the argument(s) to the algorithm should be formatted, if applicable.
boolean	countsOperations()
java.lang.String	getCurrentProblemData()
int	getDistance(Vertex v)
Vertex	getParent(Vertex v)
java.lang.Class<PuzzleInstance>	getProblemType()
Vertex	getSource()
void	initializeData() setProblemData is already implemented for you, but you might need to initialize other data related to your algorithm.
void	parseArguments(java.lang.String args) Sends a string that the user can enter to the algorithm.
void	quit() (Hopefully) gracefully stop the computation.
void	runAlgorithm() Runs the Algorithm.

Methods inherited from class cusack.hcg.graph.algorithm.AbstractAlgorithm

getNumberOfOperations, getState, isDone, isNotDone, isQuit, setProblemData, setState

Methods inherited from class java.lang.Object

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

Methods inherited from interface cusack.hcg.graph.algorithm.AlgorithmInterface

getProgressReport, getResult, getVersion

Constructor Detail

BreadthFirstSearchSkeletonAlgorithm

public BreadthFirstSearchSkeletonAlgorithm()

Method Detail

initializeData

public void initializeData()

Description copied from class: AbstractAlgorithm

setProblemData is already implemented for you, but you might need to initialize other data related to your algorithm. This method is called in setProblemData.

Specified by:

initializeData in class AbstractAlgorithm<PuzzleInstance>

runAlgorithm

public void runAlgorithm()

Description copied from interface: AlgorithmInterface

Runs the Algorithm. This is the most important method.

getParent

public Vertex getParent(Vertex v)

Parameters:

v - the vertex.

Returns:

the parent of v in the BFS tree.

getDistance

public int getDistance(Vertex v)

Parameters:

v - the vertex.

Returns:

the distance from source to v, or Integer.MAX_VALUE if no distance is stored.

getSource

public Vertex getSource()

Returns:

the source vertex used in BFS.

getCurrentProblemData

public java.lang.String getCurrentProblemData()

Returns:

A string representation of the current state of the problem data. This should be in the same format as it was passed in to setProblemData, but updated to give the current state based on the algorithm progress so far. The idea is that this can be used to show the progress of the algorithm by some GUI (or in text form, I suppose).

getProblemType

public java.lang.Class<PuzzleInstance> getProblemType()

Returns:

The class object representing the subclass of PuzzleInstance that this algorithm runs on. The implementation should probably be something like "return Blah.class;", where Blah is the subclass of PuzzleInstance used in place of T.

countsOperations

public boolean countsOperations()

Returns:

True if and only if the algorithm intends to keep track of the number of operations it is performing. Each algorithm is free to decide what it considers an "operation" to be.

quit

public void quit()

Description copied from interface: AlgorithmInterface

(Hopefully) gracefully stop the computation.

parseArguments

public void parseArguments(java.lang.String args)

Description copied from interface: AlgorithmInterface

Sends a string that the user can enter to the algorithm. The string will be in whatever format the user enters. Implementation can assume this method is called after the problem data has been set. Throw an exception if different arguments are required.

argumentFormat

public java.lang.String argumentFormat()

Description copied from interface: AlgorithmInterface

Describe how the argument(s) to the algorithm should be formatted, if applicable.

Returns: