drasys.or.graph.tsp
Class BestOf

java.lang.Object
  |
  +--drasys.or.graph.tsp.TSPBase
        |
        +--drasys.or.graph.tsp.BestOf

Direct Known Subclasses:

BestOfAll

public class BestOf

extends TSPBase

implements ConstructI

This class implements a composite TSP algorithm by combining a set of construction algorithms with a set of improvement algorithms. A composite TSP algorithm is one that has a construction phase followed by an improvement phase. In the TSP package all basic algorithms are implemented as either a pure construction or improvement class with the associated interface. This class implements the construction phase by constructing a set of initial tours using each of the construction algorithms and retaining the best. Then in the improvement phase each of the improvement algorithms are applied in turn to improve the retained tour. If the new tour is an improvement then it becomes the retained tour.

Constructor Summary

BestOf()

BestOf(GraphI graph)

 

Method Summary
void	addConstruct(ConstructI construct)           Adds a construction algorithm.
void	addConstruct(ConstructI construct, int minSize, int maxSize)           Adds a construction algorithm.
void	addImprove(ImproveI improve)           Adds an improvement algorithm.
void	addImprove(ImproveI improve, int minSize, int maxSize)           Adds an improvement algorithm.
double	constructClosedTour()           Construct a closed tour solution.
double	constructOpenTour()           Construct an open tour solution with arbitrary end points.
double	constructOpenTour(java.lang.Object originKey, java.lang.Object destinationKey)           Construct a tour with explicit end points.
double	constructOpenTourFrom(java.lang.Object originKey)           Construct an open tour solution with an explicit origin and arbitrary destination.
double	constructOpenTourTo(java.lang.Object destinationKey)           Construct an open tour solution with an explicit destination and arbitrary origin.
double	getCost()           Returns the cost of the solution tour.
java.util.Vector	getTour()           Returns the improved tour from the construction algorithm.
void	selectVertex(boolean select)           Selects all of the vertices in the graph to be in the tour if 'select' is true.
void	selectVertex(boolean[] select)           Selects all of the vertices whose corresponding element in 'select' is true.
void	selectVertex(java.lang.Object key, boolean select)           Selects the vertex to be in the tour if 'select' is true.
void	setEdgeKey(java.lang.Object edgeKey)           Sets the edge key for all of the contained TSP algorithms.
void	setGraph(GraphI graph)           Sets the graph for all of the contained TSP algorithms.
void	setProperties(PropertiesI properties)           Sets the edge properties object for all of the contained TSP algorithms.

 

Methods inherited from class drasys.or.graph.tsp.TSPBase

checkChangeCount, countVertices, forwardCost, initVertices, initVertices, reverseCost, rotateClosedTour

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

BestOf

public BestOf()

BestOf

public BestOf(GraphI graph)

addConstruct

public void addConstruct(ConstructI construct)

Adds a construction algorithm. The default minimum problem size is zero. The default maximum problem size is Integer.MAX_VALUE. If the graph has been set, then it is set in the added algorithm.

addConstruct

public void addConstruct(ConstructI construct,
                         int minSize,
                         int maxSize)

Adds a construction algorithm. The algorithm will not be exectued on problems with a dimension less than 'minSize' or greater than 'maxSize'. If the graph has been set, then it is set in the added algorithm.

addImprove

public void addImprove(ImproveI improve)

Adds an improvement algorithm. The default minimum problem size is zero. The default maximum problem size is Integer.MAX_VALUE. If the graph has been set, then it is set in the added algorithm.

addImprove

public void addImprove(ImproveI improve,
                       int minSize,
                       int maxSize)

Adds an improvement algorithm. The algorithm will not be exectued on problems with a dimension less than 'minSize' or greater than 'maxSize'. If the graph has been set, then it is set in the added algorithm.

setGraph

public void setGraph(GraphI graph)

Sets the graph for all of the contained TSP algorithms.

Overrides:

setGraph in class TSPBase

setProperties

public void setProperties(PropertiesI properties)

Sets the edge properties object for all of the contained TSP algorithms.

Overrides:

setProperties in class TSPBase

setEdgeKey

public void setEdgeKey(java.lang.Object edgeKey)

Sets the edge key for all of the contained TSP algorithms. The default value for 'edgeKey' is null.

Overrides:

setEdgeKey in class TSPBase

constructOpenTour

public double constructOpenTour(java.lang.Object originKey,
                                java.lang.Object destinationKey)
                         throws TourNotFoundException,
                                VertexNotFoundException

Construct a tour with explicit end points. An open tour is one where the origin and destination vertices are different.

Specified by:

constructOpenTour in interface ConstructI

Throws:

TourNotFoundException - if the tour can not be constructed.

constructOpenTourFrom

public double constructOpenTourFrom(java.lang.Object originKey)
                             throws TourNotFoundException,
                                    VertexNotFoundException

Construct an open tour solution with an explicit origin and arbitrary destination. An open tour is one where the origin and destination vertices are different.

Specified by:

constructOpenTourFrom in interface ConstructI

Throws:

TourNotFoundException - if the tour can not be constructed.

constructOpenTourTo

public double constructOpenTourTo(java.lang.Object destinationKey)
                           throws TourNotFoundException,
                                  VertexNotFoundException

Construct an open tour solution with an explicit destination and arbitrary origin. An open tour is one where the origin and destination vertices are different.

Specified by:

constructOpenTourTo in interface ConstructI

Throws:

TourNotFoundException - if the tour can not be constructed.

constructOpenTour

public double constructOpenTour()
                         throws TourNotFoundException

Construct an open tour solution with arbitrary end points. An open tour is one where the origin and destination vertices are different.

Specified by:

constructOpenTour in interface ConstructI

Throws:

TourNotFoundException - if the tour can not be constructed.

constructClosedTour

public double constructClosedTour()
                           throws TourNotFoundException

Construct a closed tour solution. A closed tour is one where the origin and destination vertices are the same.

Specified by:

constructClosedTour in interface ConstructI

Throws:

TourNotFoundException - if the tour can not be constructed.

selectVertex

public void selectVertex(boolean[] select)

Selects all of the vertices whose corresponding element in 'select' is true. Unselects all of the vertices whose corresponding element in 'select' is false. All of the vertices are selected by default when the algorithm is constructed.

Specified by:

selectVertex in interface ConstructI

selectVertex

public void selectVertex(boolean select)

Selects all of the vertices in the graph to be in the tour if 'select' is true. Unselects all of the vertices if 'select' is false. All of the vertices are selected by default when the algorithm is constructed.

Specified by:

selectVertex in interface ConstructI

selectVertex

public void selectVertex(java.lang.Object key,
                         boolean select)
                  throws VertexNotFoundException

Selects the vertex to be in the tour if 'select' is true. Unselects the vertex if 'select' is false. All of the vertices are selected by default when the algorithm is constructed.

Specified by:

selectVertex in interface ConstructI

getTour

public java.util.Vector getTour()

Returns the improved tour from the construction algorithm. The vector contains all the edges and the vertices in alternating order starting and ending with a vertex. The elements will always be arranged in the order of forward tour traversal.

Overrides:

getTour in class TSPBase

Throws:

GraphError - if no solution was created.

getCost

public double getCost()

Returns the cost of the solution tour.

Overrides:

getCost in class TSPBase

Throws:

GraphError - if no solution was created.