mktable.pl.in,v

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

a110 1
			$lower_bound_file = shift @@ARGV;
d138 4
a141 1
read_bounds($lower_bound_file) if defined $lower_bound_file;
d172 3
a174 2
	open IN, "<$file" || die "Couldn't open $file for reading";
	while (<IN>) {
d182 2
@


1.11
log
@Better help text.
Pass comment lines through
Better matching for instance line
@
text
@d170 1
a170 1
		if (m/^instance ([^:]+):\d+:-l\s+optimal\s+(\d+.?\d*)\x+:/) {
d238 3
a240 1
	return $1+0;
d284 1
d291 2
a292 1
			record($instance_iter,$kind,$iter,'pct',$pct);
@


1.10
log
@Avoid division by zero.  Doh!
@
text
@d81 1
a81 1
    --version       : Print a version info, then exit
d143 7
a149 1
	read_file($_);
d165 1
d170 1
a170 1
		if (m/^instance ([^:]+):\d+:-l optimal (\d+.?\d*) :/) {
@


1.9
log
@Close the lower bound file stream
@
text
@a169 1
	close IN;
d205 5
a209 1
			push @@pair,sprintf("%.2f",($pair[0]/$pair[1]));		# LK/LKcc
@


1.8
log
@Fixed tabs in help.
Fixed getting lower bound file name in option handling.
@
text
@d170 1
@


1.7
log
@New option -b to allow reading lower bounds from a file, overriding
log file's idea of lower bounds.
@
text
@d12 1
d63 2
a64 2
	-b <lower_bound_file>
					: Read lower bounds from <lower_bound_file>, overriding
d70 1
a70 1
					  $render_pair_macro\{LK result,LKcc result,LKcc-LK,LK/LKcc\}
d104 1
d109 2
a110 1
			my $lower_bound_file = shift @@ARGV;
@


1.6
log
@Since LK is the baseline, it should always come before LKcc.
@
text
@d19 1
d62 3
d86 1
d105 5
d134 2
d156 13
d252 2
d269 2
a270 2
		if (m/^Milestone:Requested:End of LK step (\d+): length\s+\d+\.?\d+?\s+(-?\d+.\d+)\% [a-z]+ $lower_bound_name after (\d+\.\d+) .* sec/) {
			my ($iter,$pct,$time) = ($1,$2,$3);
d273 3
a275 2
			record($instance_iter,$kind,$iter,'pct',($pct+0));
			record($instance_iter,$kind,$iter,'time',($time+0));
@


1.5
log
@Try to allow setting of line macros.
@
text
@d20 1
a20 1
my @@kinds=qw(deg no_d);
d65 1
a65 1
					  $render_pair_macro\{LKcc result,LK result,LK-LKcc,LK/LKcc\}
d166 1
a166 1
		foreach $kind (@@kinds) {
d176 2
a177 2
			push @@pair,sprintf("%.2f",($pair[1]-$pair[0]));
			push @@pair,sprintf("%.2f",($pair[1]/$pair[0]));
@


1.4
log
@Use TeX macros to render the line instead of trying to do
it all ourselves.  That way we can defer layout decisions.
@
text
@d93 7
d109 1
a109 1
		} else { die "$usage"."Option -l needs a string parameter"; }
@


1.3
log
@Added proper options processing.
Output only one of pct, time at a time.
Try to make the 1,n/10,n in proper order.
@
text
@d47 6
d62 10
d154 3
a156 1
	print canon_name($instance);
d158 1
d162 1
a162 1
				printf " & %.2f",avg(@@list) if $#list >= 0;
d168 6
d175 2
a176 1
	print " \\\\ \\hline % $value_type\n";
@


1.2
log
@Removed old results.pl code
Added prefix substitution (for Bentley distributions)
Changed debug output to more TeX-friendly table output.
@
text
@d12 7
a18 4
my $prog = "mktable.pl";
my $usage = <<USAGE;
./$prog <lower_bound_name> [out.<instance>..i<iters>..*.gz ...]
USAGE
d44 55
a98 1
my $lower_bound_name = shift @@ARGV;
d101 3
d108 1
a108 2
my $valuetype;
foreach $valuetype ( qw(pct time) ) {
d115 1
a115 1
		summarize($valuetype,$instance,$instance_iter);
d117 1
a117 1
}
d133 1
a133 1
	my ($valuetype,$instance,$instance_iter) = @@_;
d137 1
a137 1
	my %ns = (1=>1,$n/10=>1,$n=>1);
d139 1
a139 1
	foreach $iter ( sort keys %ns ) {
d141 7
a147 4
			my @@list = @@{record($instance_iter,$kind,$iter,$valuetype)};
			# print "%%$instance_iter $kind $iter $valuetype: avg ",
			#				  " of ",join(' ',@@list)," \n";
			printf " & %.2f",avg(@@list) if defined @@list && $#list >= 0;
d150 1
a150 1
	print " % $valuetype\n";
d192 1
d207 1
a207 1
	print "%%<";
d209 2
a210 2
		if (m/^Milestone:Requested:End of LK step (\d+): length \d+(\.\d+)?\s+(\d+.\d+)\% [a-z]+ $lower_bound_name after (\d+\.\d+) .* sec/) {
			my ($iter,$dummy,$pct,$time) = ($1,$2,$3,$4);
d215 1
a215 1
	#		print "+";
d217 1
a217 1
	#	print ".";
d220 1
a220 1
	print ">\n";
d224 2
a225 2
	my ($instance_iter,$kind,$iter,$valuetype,$value) = @@_;
	my $key = "$instance_iter#$kind#$valuetype";
d232 1
@


1.1
log
@Initial revision
@
text
@d10 1
d27 13
d48 10
a57 7
foreach ( sort cmp_instance keys %instance_iters ) {
	my $instance_iter = $_;
	my $n = n_instance($instance_iter);	
	print "\n";
	print "# $instance_iter, n = $n\n";
	my $instance = $instance_iter; $instance=s/#.*//;
	summarize($instance_iter);
d62 11
d74 1
a74 1
	my $instance_iter = shift;
d79 2
a80 2
	my $valuetype;
	foreach $valuetype ( qw(pct time) ) {
d82 4
a85 6
			foreach $iter ( sort keys %ns ) {
				my @@list = @@{record($instance_iter,$kind,$iter,$valuetype)};
				print "#$instance_iter $kind $iter $valuetype: avg ",
					(sprintf "%.2f",avg(@@list)),
					  " of ",join(' ',@@list)," \n";
			}
d88 1
d101 2
d111 3
a113 1
	return $a <=> $b;
d144 1
a144 1
	print "<";
d146 2
a147 2
		if (m/^Milestone:Requested:End of LK step (\d+): length \d+\s+(\d+.\d+)\% [a-z]+ $lower_bound_name after (\d+\.\d+) .* sec/) {
			my ($iter,$pct,$time) = ($1,$2,$3);
a168 128

###
####! @@PERL@@ -w
#### @@configure_input@@
####
#### results.pl
#### Summarize statistics from many experiments.
###
#### usage: 
####   cat (list of filenames) | results.pl minfile 
#### Content of minfile is a collection of pairs of instance names followed by
#### the lowest observed length. (or some other bound, e.g. Held-Karp lower bound)
####
#### Generate TeX lines with data:
####    Instance & 
####    LK time & 
####    LK+dec time & 
####    LK/LK+dec & 
####    LK tour (length/lower bound) & 
####    LK+dec (length/lower bound) & 
####    LK/LK+dec \\
####
###
#### Key is instance name.
#### Value is an array of: 
####	number of LK samples, 
####	sum LK time,
####	sum LK tour length
####	number of LK+dec samples, 
####	sum LK+dec time,
####	sum LK+dec tour length
###%instance = ();
###
###
#### Find the minimum value observed for all the instances, drawn from the
#### file named as the first argument.
###$minfile = shift(@@ARGV);
###open(LEAST,"<$minfile") || die "Can't open $minfile for reading.";
###%least = ();
###while (<LEAST>) {
###	m/^([^\s]+)\s+([^\s]+)/;
###	$least{$1}=$2+0;
###}
###
###@@file_names=();
###while(<>) {
###	chop;
###	push(@@file_names,$_);
###}
###
#### Now parse the values found in individual experiments listed on stdin.
###my $this_instance = "";
###my $is_decluster;
###my $seconds;
###
###my $file;
###foreach $file (@@file_names) {
###	print "\%\%\% file is $file\n";
###	open(IN,"zcat $file |") || die "Can't uncompress input files";
###
###	while(<IN>) {
###		chop;
###		if (m/^LK [0-9]+\.[0-9]+\.[0-9]+([^\s]*)/) {
###			$is_decluster = $1 eq "deg";
###		} elsif (m/^\s+(\d+\.\d+) user seconds and/ ) {
###			$seconds = $1+0;  # Last one is the total run time.
###		} elsif (m/^Instance name:\s+([^\s]+)/) {
###			$this_instance=$1;
###	#print "instance $1\n";
###		} elsif (m/^Length:\s+([^\s]+)/) {
###			my $aref = $instance{$this_instance};
###			my $this_length=$1+0;
###			if ( !defined($aref) ) {
###				$aref = $instance{$this_instance} = [ 0, 0, 0, 0, 0, 0 ];
###			}
###			if ( $is_decluster ) {
###				$$aref[3]++;
###				$$aref[4]+=$seconds;
###				$$aref[5]+=$this_length;
###			} else {
###				$$aref[0]++;
###				$$aref[1]+=$seconds;
###				$$aref[2]+=$this_length;
###			}
###	print "\t\% $this_instance ".join(' ',@@{$instance{$this_instance}})."\n";
###		}
###	}
###}
###
###print STDERR "\%\%\%\%\% Now ready to output results.\n";
###print "\%\%\%\%\% Now ready to output results.\n";
###
###my $i;
###LOOP: for $i ( sort { (nv($a)+0)<=> (nv($b)+0) } keys %instance ) {
###print " \%". join(' ',@@{$instance{$i}})."\n";
###    my ($nsamp, $time, $len, $dnsamp, $dtime, $dlen ) = @@{$instance{$i}};
###    if ( $nsamp != $dnsamp ) { 
###        print  "\% following mismatch: nsamp $nsamp != dnsamp $dnsamp\n";
###        next LOOP; 
###    }
###    if ( !defined($least{$i}) ) { 
###        print  "\% No lower bound for $i\n";
###        next LOOP; 
###    }
###    if ( $nsamp == 0 ||  $dnsamp == 0 ) {
###        print "\% nsamp $nsamp  dnsamp $dnsamp\n";
###        next LOOP;
###    }
###
###printf "%s \&\t%0.1f \&\t%0.1f \&\t%0.2f \&\t%0.2f\\%% \&\t%0.2f\\%% \&\t%0.2f\\ \\\\\n",
###        $i, $time/$nsamp, $dtime/$dnsamp, ($time/$nsamp)/($dtime/$dnsamp),
###            pct($len/$nsamp/$least{$i}), pct($dlen/$dnsamp/$least{$i}),
###            -pct($len/$nsamp/$least{$i})+ pct($dlen/$dnsamp/$least{$i});
###}
###
###exit 0;
###
###sub pct {
###	my($a)=shift;
###	return ($a-1)*100;
###}
###
###sub nv { 
###	my ($a)=shift ;
###	$a =~ m/.*[^\d]+(\d+)/; 
####print "a $a $1\n";
###	return $1+0;
###}
@