DKRouteFinder Class Reference

This object implements an heuristic solution to the travelling salesman problem. More...

Inheritance diagram for DKRouteFinder:

Instance Methods
(DKRouteAlgorithmType)	- algorithm
(CGFloat)	- pathLength
(void)	- setProgressDelegate:
(NSArray *)	- shortestRoute
(NSArray *)	- shortestRouteOrder
(NSArray *)	- sortedArrayFromArray:
Instance Methods inherited from NSObject
(NSString *)	- address
(DKStyleRegistry *)	- applicationWillReturnStyleRegistry
(BOOL)	- canBeUsedWithSelectionTool
(id)	- categoryManager:shouldReplaceObject:withObject:
(Class)	- classForCoder
(NSColor *)	- colorValue
(NSColor *)	- colourValue
(id)	- copy
(void)	- dealloc
(id)	- deepCopy
(NSDictionary *)	- dimensionValuesForArrowStroke:
(CGFloat)	- drawing:convertDistanceToExternalCoordinates:
(NSPoint)	- drawing:convertLocationToExternalCoordinates:
(void)	- drawing:didDrawRect:inView:
(void)	- drawing:willDrawRect:inView:
(NSString *)	- drawing:willReturnAbbreviationForUnit:
(NSString *)	- drawing:willReturnFormattedCoordinateForDistance:
(CGFloat)	- drawingWillReturnUnitToPointsConversonFactor:
(void)	- finalize
(NSString *)	- hexString
(void)	- hotspot:didEndTrackingWithEvent:inView:
(void)	- hotspot:isTrackingWithEvent:inView:
(void)	- hotspot:willBeginTrackingWithEvent:inView:
(NSData *)	- imageData
(NSImage *)	- imageResourceNamed:
(id)	- init
(id)	- initWithExpression:
(id)	- instantiateObjectWithShortName:parameters:
(BOOL)	- isLiteralValue
(void)	- layoutManager:willPlaceGlyphAtIndex:atLocation:pathAngle:yOffset:
(void)	- menuItem:wasAddedForObject:inCategory:
(BOOL)	- moveObjectTo:position:slope:userInfo:
(id)	- mutableCopy
(void)	- oneShotComplete
(void)	- oneShotHasReached:
(void)	- oneShotWillBegin
(void)	- path:elementIndex:type:points:subPathIndex:subPathClosed:contextInfo:
(id)	- placeLinkFromPoint:toPoint:onPath:linkNumber:userInfo:
(id)	- placeObjectAtPoint:onPath:position:slope:userInfo:
(NSPoint)	- point
(NSPoint)	- pointForTextLayout
(DKStyle *)	- registry:shouldReplaceStyle:withStyle:
(NSBezierPath *)	- renderer:willRenderPath:
(void)	- routeFinder:progressHasReached:
(void)	- setValue:forNumericParameter:
(NSString *)	- stringValue
(CGFloat)	- taperFactorAtDistance:onPath:ofLength:
(void)	- toolDidPerformUndoableAction:
(void)	- toolWillPerformUndoableAction:
(NSURL *)	- url
Instance Methods inherited from <NSObject>
(NSString *)	- description
(NSUInteger)	- hash
(BOOL)	- isEqual:
Instance Methods inherited from <NSKeyValueBindingCreation>
(void)	- bind:toObject:withKeyPath:options:
(NSArray *)	- exposedBindings
(NSDictionary *)	- infoForBinding:
(NSArray *)	- optionDescriptionsForBinding:
(void)	- unbind:
(Class)	- valueClassForBinding:

Class Methods
(DKRouteFinder *)	+ routeFinderWithArrayOfPoints:
(DKRouteFinder *)	+ routeFinderWithObjects:withValueForKey:
(void)	+ setAlgorithm:
(NSArray *)	+ sortedArrayOfObjects:byShortestRouteForKey:
Class Methods inherited from NSObject
(id)	+ alloc
(Class)	+ class
(void)	+ initialize
(void)	+ load
(id)	+ new
Class Methods inherited from <NSKeyValueBindingCreation>
(void)	+ exposeBinding:

Detailed Description

This object implements an heuristic solution to the travelling salesman problem.

This object implements an heuristic solution to the travelling salesman problem. The algorithm is based on simulated annealing and is due to "Numerical Recipes in C", Chapter 10.

To use, initialise with an array of NSValues containing NSPoints. Then request the shortestRoute. The order of points returned by -shortestRoute will be the shortest route as determined by the algorithm. The first point object in both input and output arrays is the same - in other words the zeroth element of the input array sets the starting point of the path.

For uses with other object types, the -shortestRouteOrder might be more useful. This returns an array of integers which is the order of the objects. This can then be used to reorder arbitrary objects.

Most simply, the +sortedArrayOfObjects:byShortestRouteForKey: will deal with any objects as long as they have a KVC-compliant property that resolves to an NSPoint return value, and is given by <key>. The result is a new array of the same objects sorted according to the TSP solution.

Method Documentation

- (DKRouteAlgorithmType) algorithm

- (CGFloat) pathLength

+ (DKRouteFinder*) routeFinderWithArrayOfPoints:

(NSArray *)

arrayOfPoints

+ (DKRouteFinder*) routeFinderWithObjects:		(NSArray *)	objects
withValueForKey:		(NSString *)	key

+ (void) setAlgorithm:

(DKRouteAlgorithmType)

algType

- (void) setProgressDelegate:

(id)

aDelegate

- (NSArray*) shortestRoute

- (NSArray*) shortestRouteOrder

- (NSArray*) sortedArrayFromArray:

(NSArray *)

anArray

+ (NSArray*) sortedArrayOfObjects:		(NSArray *)	objects
byShortestRouteForKey:		(NSString *)	key