cusack.hcg.games.pebble.algorithms.pebblingNumber

Class PebblingNumberBottomUp

java.lang.Object

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

cusack.hcg.games.pebble.algorithms.PebbleAlgorithm

cusack.hcg.games.pebble.algorithms.pebblingNumber.PebblingNumberBottomUp

All Implemented Interfaces:

AlgorithmInterface<PebbleInstance>

Direct Known Subclasses:

PebblingNumberRootedBottomUp

public class PebblingNumberBottomUp
extends PebbleAlgorithm

As of June 4, 2015, this is by far our fastest pebbling number algorithm. This algorithm finds the pebbling number of a graph. It does so by finding the maximum unsolvable configuration on the graph. To do this it uses a backtracking algorithm based on page 232 of Skiena's Algorithm Design Manual. It adds one pebble at a time to a vertex until the configuration becomes solvable, then it backtracks to the last unsolvable configuration and starts placing pebbles on the next vertex until it becomes solvable, and so on. Note that most of the code here was taken from PebblingNumberExhaustiveGeneric.

Author:

Aaron Green Summer 2015 Modified by CAC, Summer 2016.

Constructor Summary

Constructors

Constructor and Description
PebblingNumberBottomUp()

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.
java.lang.String	briefProgress()
boolean	countsOperations()
java.lang.String	getCurrentProblemData()
int	getPebblingNumber()
java.lang.String	getProgressReport() The printout in the Solvability Dialog box.
java.lang.String	getResult() Return the result of the algorithm in the context of the problem.
double	getVersion() Mostly for use in comparing results from previous versions of algorithms, and/or so we can know whether or not data in the database is based on an older version of the algorithm.
void	initializeMoreData() Called by initializeData which is called by setPuzzleData.
void	parseArguments(java.lang.String args) Sends a string that the user can enter to the algorithm.
void	runAlgorithm() Runs the Algorithm.

Methods inherited from class cusack.hcg.games.pebble.algorithms.PebbleAlgorithm

getPebbleState, getProblemType, initializeData, quit, setPebbleState

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

Constructor Detail

PebblingNumberBottomUp

public PebblingNumberBottomUp()

Method Detail

initializeMoreData

public void initializeMoreData()

Description copied from class: PebbleAlgorithm

Called by initializeData which is called by setPuzzleData. It should initialize data in the subclass that needs it.

Specified by:

initializeMoreData in class PebbleAlgorithm

getPebblingNumber

public int getPebblingNumber()

getResult

public java.lang.String getResult()

Description copied from interface: AlgorithmInterface

Return the result of the algorithm in the context of the problem. i.e. Solvable, Unsolvable, Unknown. This tells more than "Done" or "Not_Done" that is given in the more general sense. This might just be "true" or "false", it might be the encoding of a series of moves, etc.

Specified by:

getResult in interface AlgorithmInterface<PebbleInstance>

Overrides:

getResult in class PebbleAlgorithm

Returns:

the result

runAlgorithm

public void runAlgorithm()

Description copied from interface: AlgorithmInterface

Runs the Algorithm. This is the most important method.

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).

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.

getVersion

public double getVersion()

Description copied from interface: AlgorithmInterface

Mostly for use in comparing results from previous versions of algorithms, and/or so we can know whether or not data in the database is based on an older version of the algorithm. Start with "return 1.0". Go up by whatever increments you like (e.g. 1.1, 1.2, etc. or 1, 2, 3, etc.)

Returns:

getProgressReport

public java.lang.String getProgressReport()

The printout in the Solvability Dialog box.

Specified by:

getProgressReport in interface AlgorithmInterface<PebbleInstance>

Overrides:

getProgressReport in class PebbleAlgorithm

Returns:

briefProgress

public java.lang.String briefProgress()

parseArguments

public void parseArguments(java.lang.String args)
                    throws java.lang.RuntimeException

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.

Throws:

java.lang.RuntimeException

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: