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), "\n";
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.
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¶
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
