ALGOTUTOR(1) User Contributed Perl Documentation ALGOTUTOR(1)NAME
algotutor - an interactive program for observing the intermediate steps of algorithms.
SYNOPSIS
algotutor [OPTION] ... DATA ...
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.
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.
OPTIONS -a ALGO
Runs the algorithm ALGO. Currently ALGO can be one of:
bst operations on binary search trees
rbt operations on red-black trees (remove() is not implemented yet)
heap operations on heaps -- the remove operation on a heap always removes the top element regardless of the argument
sbs stack-based search on graphs, a variant of depth first search
bfs breadth first search on graphs
prim Prim's minimal spanning tree on graphs
dijk Dijkstra's single-source shortest path on graphs
flwa Floyd-Warshall's all-pair shortest path on graphs (very, very slow)
dom 2-dimensional point domination
graham Graham's scan for convex hull
lcs longest common subsequence -- it requires two strings as the command line arguments. For example, "algotutor -a lcs AGCTATACGATGACT
GTCAGTATAGTCATATG"
matc optimal matrix chain multiplication -- it requires an alternating sequence of integers and matrix names as the command line
arguments. For example, "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.
-s VERTEX
Use VERTEX as the starting vertex (for sbs, bfs, prim, and dijk)
-i STEP
Display step STEP as the initial image.
-d FILENAME
Dump the picture into FILENAME as a ps file and exit immediately without going into interactive mode.
LICENSE
This code is distributed under the GNU General Public License
AUTHOR
Chao-Kuei Hung ckhung AT ofset DOT org
SEE ALSO
Please see /usr/share/doc/algotutor/doc/ for examples and the full set of documentations.
perl v5.10.1 2010-07-05 ALGOTUTOR(1)
Check Out this Related Man Page
Bio::Coordinate::Graph(3pm) User Contributed Perl Documentation Bio::Coordinate::Graph(3pm)NAME
Bio::Coordinate::Graph - Finds shortest path between nodes in a graph
SYNOPSIS
# get a hash of hashes representing the graph. E.g.:
my $hash= {
'1' => {
'2' => 1
},
'2' => {
'4' => 1,
'3' => 1
},
'3' => undef,
'4' => {
'5' => 1
},
'5' => undef
};
# create the object;
my $graph = Bio::Coordinate::Graph->new(-graph => $hash);
# find the shortest path between two nodes
my $a = 1;
my $b = 6;
my @path = $graph->shortest_paths($a);
print join (", ", @path), "
";
DESCRIPTION
This class calculates the shortest path between input and output coordinate systems in a graph that defines the relationships between them.
This class is primarely designed to analyze gene-related coordinate systems. See Bio::Coordinate::GeneMapper.
Note that this module can not be used to manage graphs.
Technically the graph implemented here is known as Directed Acyclic Graph (DAG). DAG is composed of vertices (nodes) and edges (with
optional weights) linking them. Nodes of the graph are the coordinate systems in gene mapper.
The shortest path is found using the Dijkstra's algorithm. This algorithm is fast and greedy and requires all weights to be positive. All
weights in the gene coordinate system graph are currently equal(1) making the graph unweighted. That makes the use of Dijkstra's algorithm
an overkill. A simpler and faster breadth-first would be enough. Luckily the difference for small graphs is not significant and the
implementation is capable of taking weights into account if needed at some later time.
Input format
The graph needs to be primed using a hash of hashes where there is a key for each node. The second keys are the names of the downstream
neighboring nodes and values are the weights for reaching them. Here is part of the gene coordiante system graph::
$hash = {
'6' => undef,
'3' => {
'6' => 1
},
'2' => {
'6' => 1,
'4' => 1,
'3' => 1
},
'1' => {
'2' => 1
},
'4' => {
'5' => 1
},
'5' => undef
};
Note that the names need to be positive integers. Root should be '1' and directness of the graph is taken advantage of to speed
calculations by assuming that downsream nodes always have larger number as name.
An alternative (shorter) way of describing input is to use hash of arrays. See Bio::Coordinate::Graph::hash_of_arrays.
FEEDBACK
Mailing Lists
User feedback is an integral part of the evolution of this and other Bioperl modules. Send your comments and suggestions preferably to the
Bioperl mailing lists Your participation is much appreciated.
bioperl-l@bioperl.org - General discussion
http://bioperl.org/wiki/Mailing_lists - About the mailing lists
Support
Please direct usage questions or support issues to the mailing list:
bioperl-l@bioperl.org
rather than to the module maintainer directly. Many experienced and reponsive experts will be able look at the problem and quickly address
it. Please include a thorough description of the problem with code and data examples if at all possible.
Reporting Bugs
report bugs to the Bioperl bug tracking system to help us keep track the bugs and their resolution. Bug reports can be submitted via the
web:
https://redmine.open-bio.org/projects/bioperl/
AUTHOR - Heikki Lehvaslaiho
Email: heikki-at-bioperl-dot-org
APPENDIX
The rest of the documentation details each of the object methods. Internal methods are usually preceded with a _
Graph structure input methods
graph
Title : graph
Usage : $obj->graph($my_graph)
Function: Read/write method for the graph structure
Example :
Returns : hash of hashes grah structure
Args : reference to a hash of hashes
hash_of_arrays
Title : hash_of_arrays
Usage : $obj->hash_of_array(%hasharray)
Function: An alternative method to read in the graph structure.
Hash arrays are easier to type. This method converts
arrays into hashes and assigns equal values "1" to
weights.
Example : Here is an example of simple structure containing a graph.
my $DAG = {
6 => [],
5 => [],
4 => [5],
3 => [6],
2 => [3, 4, 6],
1 => [2]
};
Returns : hash of hashes graph structure
Args : reference to a hash of arrays
Methods for determining the shortest path in the graph
shortest_path
Title : shortest_path
Usage : $obj->shortest_path($a, $b);
Function: Method for retrieving the shortest path between nodes.
If the start node remains the same, the method is sometimes
able to use cached results, otherwise it will recalculate
the paths.
Example :
Returns : array of node names, only the start node name if no path
Args : name of the start node
: name of the end node
dijkstra
Title : dijkstra
Usage : $graph->dijkstra(1);
Function: Implements Dijkstra's algorithm.
Returns or sets a list of mappers. The returned path
description is always directed down from the root.
Called from shortest_path().
Example :
Returns : Reference to a hash of hashes representing a linked list
which contains shortest path down to all nodes from the start
node. E.g.:
$res = {
'2' => {
'prev' => '1',
'dist' => 1
},
'1' => {
'prev' => undef,
'dist' => 0
},
};
Args : name of the start node
perl v5.14.2 2012-03-02 Bio::Coordinate::Graph(3pm)