tspsolution.py

# tspsolution.py
# 9/26/2010-A

# Read a TSP tour file generated by either concorde or linkern

# Written by Daniel C. Newman for the Eggbot Project
# dan dot newman at mtbaldy dot us
# 25 September 2010

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

import sys

class tspSolution:

	def __init__( self ):

		# Input file name saved for error reporting
		self.infile = ''

		# Count declared at the start of the solution file
		# We save this for doing a sanity check later
		self.count = 0

		# The tour stored as a simple list
		self.tour = []

	# Solution files from linkern have the format
	#
	#   count count
	#   index-0 index-1 length-0-1
	#   index-1 index-2 length-1-2
	#   index-2 index-3 length-2-3
	#   ...     ...     ...

	def __load_linkern( self, f ):
		assert f
		for line in f:
			vals = line.strip().split(' ')
			if len( vals ) != 3:
				continue
			self.tour += vals[0:1]
			self.tour
		return True

	# Solution files from concorde have the format
	#
	#   count
	#   index-0 index-1 index-2 index-3 ... index-9
	#   index-10 index-11 length-12 index-13 ... index-19
	#   index-20 index-21 length-22 index-23 ... index-29
	#   ...
	#
	# The final line will have between 1 and 10 indices

	def __load_concorde( self, f ):
		assert f
		for line in f:
			vals = line.strip().split(' ')
			if len( vals ) == 0:
				continue
			self.tour += vals
		return True

	def load( self, infile ):
		self.count = 0
		self.tour = []
		self.infile = infile

		f = open( infile, 'r' )

		line = f.readline().strip()
		vals = line.split( ' ' )
		if len( vals ) == 1:
			# Looks like a solution from Concorde
			self.count = int( vals[0] )
			ok = self.__load_concorde( f )
		elif len( vals ) == 2:
			# Looks like a solution from Lin-Kern
			self.count = int( vals[0] )
			ok = self.__load_linkern( f )
		else:
			f.close()
			sys.stderr.write( 'Input file %s has unknown format\n' % self.infile )
			return False

		f.close()
		if not ok:
			return False

		# Sanity check that we read the correct number of indices from the file
		if len( self.tour ) != self.count:
			sys.stderr.write( 'Solution file contains wrong number of indices; %d != %d\n' % ( len( self.tour), self.count ) )
			return False

		# Sanity check that none of the indices are < 0 or >= self.size
		for t in self.tour:
			i = int( t )
			if ( i < 0 ) or ( i > self.count ):
				print( t, i )
				sys.stderr.write( 'Invalid tour index found in file %s\n' % self.infile )
				return False

		# Now "close" the tour by making the trip from the ending position
		# back to the starting position
		if len( self.tour ):
			self.tour.append( self.tour[0] )

		return True