tspreorder.pl.in,v

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

head	1.5;
access;
symbols
	zero-five-zero:1.5
	zero-four-seventeen:1.5
	zero-four-ten:1.5
	zero-four-nine:1.5
	zero-four-eight:1.5
	zero-four-five:1.5
	zero-four-three:1.4
	zero-four-zero:1.4;
locks
	neto:1.5; strict;
comment	@# @;


1.5
date	98.08.08.00.04.50;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	97.10.31.20.32.26;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	97.10.31.20.02.25;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	97.06.25.18.53.18;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	97.06.18.20.28.52;	author neto;	state Exp;
branches;
next	;


desc
@Reorder cities in Euclidean TSPLIB instances.
@


1.5
log
@Better in every way.
That's right, I have no idea.
@
text
@#! @@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;
@


1.4
log
@Added a check to see if we output the right number of cities.
@
text
@d54 3
a56 24
while (<>) {
	if ( $in_coords ) {
		local($saved_line)=$_;
		if ( $i < $num_cities && m/^\s*(\d+)\s+(.*)/ ) {
			# Read the city coordinates
			local($city_num,$rest) = ($1,$2);
			$i++;
			local($r);
			if ($seed) {$r=rand();} else {$r=$i}
			$cities{"<$r#$city_num>"}=$rest;
		} elsif ( $i==$num_cities ) {
			# Output the randomly rearranged cities.
			local($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 $saved_line;
		}
	} elsif (m/^DIMENSION\s*:\s*(\d+)/) {
d59 1
a59 1
	} elsif (m/^COMMENT\s*:(.*)/) {
d63 1
a63 1
	} elsif (m/NODE_COORD_SECTION/) {
d65 1
a65 1
		$in_coords=1;
d71 28
@


1.3
log
@Fixed a serious bug: I was only using the first digit of the city number
to ensure uniqueness of keys.  Sometimes this made the program output
too few lines, with the result that lk would assume 0 0 coordinates!

In minor news, I don't chop the comment anymore: . doesn't match newline.
@
text
@d72 2
@


1.2
log
@Seed 0 forces the identity permutation.
Can't chop dollar 1.
@
text
@d57 1
a57 1
		if ( $i < $num_cities && m/^\s*(\d)+(.*)/ ) {
d59 1
d63 1
a63 1
			$cities{"<$r#$1>"}=$2;
d80 1
a80 1
		chop($comment);
@


1.1
log
@Initial revision
@
text
@d19 2
a20 1
    -s n   --seed n        : Set the seed to n, default is $seed_default
d60 2
a61 1
			local($r)=rand();
d78 3
a80 2
		chop $1;
		print "COMMENT: $1 | tspreorder.pl -s $seed\n";
@