#!/usr/bin/perl -w

use strict;
use Getopt::Std;

my (%opts) = (
    r => 4,	# # of rows
    c => 4,	# # of columns
    w => 80,	# width of a grid cell
    h => 60,	# height of a grid cell
    l =>  1,	# lower bound
    u => 10,	# upper bound
#    d => '\\/;/\\',	# diagonals
    d => 0.9,	# probability of generating each diagonal
);

getopts('r:c:l:u:w:h:d:', \%opts);
# $opts{d} = [ map { [split "", $_] } split ";", $opts{d}];

sub randfill {
    my ($adj) = @_;
    my ($v, $w);
    foreach $v (keys %$adj) {
	foreach $w (keys %{ $adj->{$v} }) {
	    $adj->{$v}{$w} = $adj->{$w}{$v} =
		int(rand($opts{u}-$opts{l})) + $opts{l};
	}
    }
}

sub rc2name {
    my ($r, $c) = @_;
    return "" if ($r>=$opts{r} or $c>=$opts{c});
    return chr(ord('A') + $opts{c}*$r + $c)
	if ($opts{c}*$opts{r} <= 26);
    return chr(ord('A') + $r) . chr(ord('A') + $c);
}

sub name2rc {
    my ($name) = @_;
    my ($r) = ord($name) - ord('A');
    return (int($r / $opts{c}), $r % $opts{c})
	if (length($name) == 1);
    my ($c) = ord(substr($name,1)) - ord('A');
    return ($r, $c);
}

sub print_adj {
    my ($adj) = @_;
    my ($v, $w);
    foreach $v (sort keys %$adj) {
	my ($r, $c) = name2rc($v);
	printf "    $v => { -pos=>[%d, %d],\n   ",
	    ($c+0.5)*$opts{w}, ($r+0.5)*$opts{h};
	foreach $w (sort keys %{ $adj->{$v} }) {
	    print "\t$w => $adj->{$v}{$w},"
	}
	print "\n    },\n";
    }
    print "\n}\n";
}

sub rectangular {
    my ($i, $j, $adj, $v, $w, $t);
#    $dr = $#{$opts{d}} + 1;
#    $dc = $#{$opts{d}->[0]} + 1;
    for ($i=0; $i<$opts{r}; ++$i) {
	for ($j=0; $j<$opts{c}; ++$j) {
	    $v = rc2name($i, $j);
	    $adj->{$v}{rc2name($i+1,$j)} = 1;
	    $adj->{$v}{rc2name($i,$j+1)} = 1;
	    $t = rand();
	    if ($t < $opts{d}) {
		if ($t / $opts{d} > 0.5) {
		    $adj->{$v}{rc2name($i+1,$j+1)} = 1;
		} else {
		    $adj->{rc2name($i,$j+1)}{rc2name($i+1,$j)} = 1;
		}
	    }
#		if ($opts{d}->[$i % $dr][$j % $dc] eq '\\');
#		if ($opts{d}->[$i % $dr][$j % $dc] eq '/');
	}
    }
    foreach $v (keys %$adj) {
	if (not $v) {
	    delete $adj->{$v};
	    next;
	}
	foreach $w (keys %{$adj->{$v}}) {
	    delete $adj->{$v}{$w} if (not $w);
	}
    }
    randfill($adj);
    print_adj($adj);
}

#my ($ht) = ($opts{r} + 0.3) * $opts{h};
print <<HDR;
# generated by gengr

{
"-name" => "random grid",
-type => "graph",
-linear_transform => {
    -scale => [1, 1],
    -offset => [0, 0],
},
-directed => 0,

-init_data => {
HDR
rectangular();
print "\n}\n";

#my ($i,$j);
#for ($i=0; $i<$opts{r}; ++$i) {
#    for ($j=0; $j<$opts{c}; ++$j) {
#	printf "($i:$j %s %d:%d), ", rc2name($i,$j), name2rc(rc2name($i,$j));
#    }
#    print "\n";
#}

#my ($i, $j);
#for ($i=0; $i<=$#{$opts{d}}; ++$i) {
#    for ($j=0; $j<=$#{$opts{d}->[$i]}; ++$j) {
#	print $opts{d}->[$i][$j];
#    }
#    print "\n";
#}

__END__

=head1 NAME

gen_at_graph - generates a random graph for use in algotutor.

=head1 SYNOPSIS

B<gen_at_graph> [I<OPTION>] ...

=head1 DESCRIPTION

gen_at_graph generates a random graph for use in algotutor. Currently
the only type of graph it can generate is a rectangular grid of
vertices. Each vertex is connected to at most 8 adjacent vertices
around it.

=head1 OPTIONS

=over

=item B<-r> I<ROWS>

generate ROWS rows of vertices

=item B<-c> I<COLS>

generate COLS columns of vertices

=item B<-w> I<WIDTH>

make each grid cell WIDTH pixel wide

=item B<-h> I<HEIGHT>

make each grid cell HEIGHT pixel high

=item B<-l> I<LOWER>

make all random numbers greater than or equal to LOWER

=item B<-u> I<UPPER>

make all random numbers less than (but never equal to) UPPER

=item B<-d> I<PATTERN>

specify the probability of generating each diagonal

=back

=head1 LICENSE

This code is distributed under the GNU General Public License

=head1 AUTHOR

B<Chao-Kuei Hung> ckhung AT cyut DOT edu DOT tw

=head1 SEE ALSO 

Please see /usr/share/doc/algotutor/doc/ for the full set of documentations.

=cut