tspreorder.pl.in

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

#! @PERL@
# @configure_input@
# Randomly reorder the cities in a Euclidean TSPLIB instance.
# Doesn't handle plotting coordinates, only definition coordinates.

$progname="tspreorder.pl";
$pkgname = "@PACKAGE@";
$pkgversion = "@VERSION@";
$version_banner="$progname ($pkgname) $pkgversion";

$seed_default = 42;

$usage = <<EOT;
$version_banner
Randomly reorder cities in a Euclidean TSPLIB instance.
$progname [options]
  where options can be:
    -h     --help          : Print this message
    -s n   --seed n        : Set the random seed to n, default is $seed_default
                             seed 0 forces the identity permutation
           --version       : Print a version info, then exit
EOT

# Set the random number seed
$seed=$seed_default;

# Parse the command line options
while ($#ARGV >= 0 && $ARGV[0] =~ m/^-/) {
    $option = $_ = shift(@ARGV);
    if (m/^-h$/ || m/^--help$/)    { print $usage; exit; }
    if (m/^-s$/ || m/^--seed$/) { # mandatory seed parameter
		if ( $#ARGV >= 0 ) {$seed=shift(@ARGV); next;}
		else { die "$progname: option $option requires a seed argument\n";}
	}
    if (m/^--version$/) { print "$version_banner\n"; exit; }
    die "$progname: Unknown option $option\n$usage";
}


############################################
srand($seed);

#print STDERR "seed is $seed\n";

# The cities dictionary. Keys are <randnumber#origordinal>
# The original ordinal number is preserved to ensure uniqueness of keys.
# It must come after the random number so that reordering does actually
# occur.
%cities=(); 

$num_cities=0;
$i=0;
$in_coords=0;
HEADER: while (<>) {
	$line=$_;
	if ($line =~ m/^DIMENSION\s*:\s*(\d+)/) {
		print;
		$num_cities=$1;
	} elsif ($line =~ m/^COMMENT\s*:(.*)/) {
		local($comment)=$1;
		#chop($comment);
		print "COMMENT: $comment | tspreorder.pl -s $seed\n";
	} elsif ($line =~ m/NODE_COORD_SECTION/) {
		print;
		last HEADER;
	} else {
		# All other output piped straight through
		print;
	}
}


# Read the city coordinates
BODY: while (<>) {
	$line=$_;
	if ( $i < $num_cities && $line =~ m/^\s*(\d+)\s+(.*)/ ) {
		local($city_num,$rest) = ($1,$2);
		$i++;
		local($r);
		if ($seed) {$r=rand();} else {$r=$i}
		$key=sprintf "<%17.15f %15d>", $r, $city_num;
		$cities{$key}=$rest;
	}
}


# Output the randomly rearranged cities.
$key,$j;
$j=1;
foreach $key (sort keys(%cities)) {
	print "$j $cities{$key}\n";
	$j++;
}
$j--;
$j == $num_cities || die "Output $j cities instead of $num_cities";
$in_coords=0;
print "EOF\n";
exit 0;