File: algotutor

package info (click to toggle)
algotutor 0.8.6-3
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 580 kB
  • sloc: perl: 2,563; makefile: 41; php: 24; sh: 1
file content (246 lines) | stat: -rwxr-xr-x 7,145 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#!/usr/bin/perl -w
# Author:  Chao-Kuei Hung
# For more info, including license, please see doc/index.html

use strict;
use Getopt::Std;
use lib '/usr/share/perl5/algotutor';

BEGIN {
    my ($path) = $0 =~ m#(.*/)#;
    $path = "." unless defined $path;
    push @INC, $path;
}

my (
    %opts,		# command line options
    $wd,		# tk widgets
    $dfn,		# data file name
    $mds,		# main data structure
);
%opts = (
    a => undef,		# which algorithm to run?
    s => undef,		# start vertex (for some graph algos)
    i => 0,		# step # of initial image
    d => undef,		# dump ps file and exit immediately
);

require "utilalgo";
require "basic.pl";

$wd->{main} = MainWindow->new(-title=>"algotutor");

getopts('a:s:i:d:', \%opts);
if (grep { $opts{a} eq $_ } qw(lcs matc flwa)) {
    # dynamic programming
    my ($algo) = $opts{a};
    my ($tab) = {
	lcs   => { maxlvl => 3,
	    run => sub {
		require "dp/lcs"; lcs(@ARGV[0,1], $wd->{can}{main});
	    },
	},
	matc  => { maxlvl => 3,
	    run => sub {
		require "dp/matrixchain"; matrixchain(\@ARGV, $wd->{can}{main});
	    },
	},
	flwa => { maxlvl => 3,
	    run => sub {
		require "dp/flwa"; flwa($ARGV[0], $wd->{can}{main});
	    },
	}
    };
    require Board;
    $wd->{can}{main} = gen_can($wd->{main}, undef, -elevation=>1,
	-maxlevel=>$tab->{$algo}{maxlvl} );
    $wd->{ctrl} = gen_ctrl($wd->{main}, $wd->{can});
    $tab->{$algo}{run}();
} else {
    # algorithms other than dynamic programming
    die "need exactly one data file. Example:\n\talgotutor -a bst /usr/share/algotutor/data/countries.gr\n" 
	unless $#ARGV == 0;
    $dfn = $ARGV[0];
    die "cannot read data file '$dfn'.\nDoes it exist and do you have read permissions?\n" unless -r $dfn;
    die "please specify an algorithm to run using -a. Example:\n\t-a bst\n\t-a heap\n\t-a sbs\n\t-a bfs\n\t-a prim\n\t-a dijk\n\t-a flwa\n"
	unless defined $opts{a};

    $mds = eval { do $dfn };
    die "'$dfn' does not look like a valid algotutor data file\n"
	unless ($mds and ref $mds eq "HASH");

    if (grep { $opts{a} eq $_ } qw(bst rbt heap graham dom)) {
	usual_algo($opts{a});
    } elsif (grep { $opts{a} eq $_ } qw(bfs sbs dijk prim)) {
	$mds = prio_first($wd, $mds, $opts{a});
    } else {
	die "unknown algorithm '$opts{a}'\n";
    }
}

$wd->{ctrl}->configure(-recorder=>0);
my ($steps) = $wd->{ctrl}->{"#lowest_canvas"}->total_marks(
    $wd->{ctrl}->{"#slevel"} );
printf "total marks: %d\n", $steps;
if (defined $opts{i}) {
    if ($opts{i} < 0 or $opts{i} >= $steps) {
	print STDERR "illegal request to display step $opts{i} (out of range)\n";
    } else {
	print "seeking to step $opts{i}...\n";
	$wd->{ctrl}->timeknob_seek($opts{i});
    }
}
if ($opts{d}) {
    dump_image($wd->{can}, $opts{d});
} else {
    Tk::MainLoop();
}
exit();
# end of main program

sub disp_vert_val {
    my ($v, $val) = @_;
    $v->configure(-text=>"$v\n$val");
}


sub prio_first {
    my ($wd, $mds, $prio) = @_;
    require Graph;
    $wd->{can}{main} = gen_can($wd->{main}, undef, -elevation=>2, -maxlevel=>3);
    $wd->{can}{fr} = gen_can($wd->{main}, "Fringe", -elevation=>1, -maxlevel=>3);
    $wd->{ctrl} = gen_ctrl($wd->{main}, $wd->{can});
    $mds = Graph->new(-canvas=>$wd->{can}{main}, %$mds);
    require "graph/pfs";
    pfs($mds, $wd->{can}{fr}, -start=>$opts{s}, -priority=>$prio, -on_vertex=>\&disp_vert_val);
    return $mds;
}

sub usual_algo {
    my ($algo) = @_;
    my ($tab) = {
	bst   => { ds => "BST",    maxlvl => 2 },
	rbt   => { ds => "RBTree", maxlvl => 2 },
	heap  => { ds => "Heap",   maxlvl => 3 },
	graham=> { ds => "Graph",  maxlvl => 2, post=> sub {
	    require "cgeom/graham"; graham($mds);
	} },
	dom   => { ds => "Graph",  maxlvl => 2, post=> sub {
	    require "cgeom/dom"; dom($mds);
	} },
#	dfs   => { ds => "Graph",  maxlvl => 2, post=> sub {
#	    require "graph/dfs";
#	    dfs($mds, -start=>$opts{s}, -on_vertex=>\&disp_vert_val);
#	} },
	flwa  => { ds => "Graph",  maxlvl => 2, post=> sub {
	    require "graph/flwa"; flwa($mds);
	} },
    };
    require $tab->{$algo}{ds} . ".pm";
    $wd->{can}{main} = gen_can($wd->{main}, undef, -elevation=>1,
	-maxlevel=>$tab->{$algo}{maxlvl} );
    $wd->{ctrl} = gen_ctrl($wd->{main}, $wd->{can});
    $mds = eval($tab->{$algo}{ds} . '->new(-canvas=>$wd->{can}{main}, %$mds)');
    $tab->{$algo}{post}->() if ref $tab->{$algo}{post};
}

__END__

=head1 NAME

algotutor - an interactive program for observing the intermediate steps 
of algorithms.

=head1 SYNOPSIS

B<algotutor> [I<OPTION>] ... I<DATA> ...

=head1 DESCRIPTION

algotutor is an interactive program for observing the intermediate steps 
of algorithms. The target audience is computer science students and/or anyone 
who studies algorithms and/or data structures. One can create data files in 
plain text format (actually perl anonymous hashes, but one need not care) 
and let algotutor runs through some predefined algorithm. Then one can step 
backward and forward through the execution sequence of the algorithm at 
different levels of details. It requires perl-Tk.

I<DATA> is the input data. For the dynamic programming algorithms such
as lcs and matc, please see the respective entries in the following
list; for other algorithms, it is the file name containing the
actual input data.

=head1 OPTIONS

=over

=item B<-a> I<ALGO>

Runs the algorithm ALGO. Currently ALGO can be one of:

=over

=item B<bst> operations on binary search trees

=item B<rbt> operations on red-black trees (remove() is not implemented yet)

=item B<heap> operations on heaps -- the remove operation on a heap always removes the top element regardless of the argument

=item B<sbs> stack-based search on graphs, a variant of depth first search

=item B<bfs> breadth first search on graphs

=item B<prim> Prim's minimal spanning tree on graphs

=item B<dijk> Dijkstra's single-source shortest path on graphs

=item B<flwa> Floyd-Warshall's all-pair shortest path on graphs (very, very slow)

=item B<dom> 2-dimensional point domination

=item B<graham> Graham's scan for convex hull

=item B<lcs> longest common subsequence -- it requires two strings as
    the command line arguments. For example,
    C<algotutor -a lcs AGCTATACGATGACT GTCAGTATAGTCATATG>

=item B<matc> optimal matrix chain multiplication -- it requires an
    alternating sequence of integers and matrix names as the command
    line arguments. For example, 
    C<algotutor -a matc 32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35>
    means finding the optimal multiplication sequence of the
    chain of matrices: A of size 32 by 35, B of size 35 by 24, ...
    H of size 34 by 35.

=back

=item B<-s> I<VERTEX>

Use VERTEX as the starting vertex (for sbs, bfs, prim, and dijk)

=item B<-i> I<STEP>

Display step STEP as the initial image.

=item B<-d> I<FILENAME>

Dump the picture into FILENAME as a ps file and exit immediately
without going into interactive mode.

=back

=head1 LICENSE

This code is distributed under the GNU General Public License

=head1 AUTHOR

B<Chao-Kuei Hung> ckhung AT ofset DOT org

=head1 SEE ALSO 

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

=cut