Bio::Coordinate::Graph - Finds shortest path between nodes in a graph # 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"; 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 impler and faster breadth-first would be enough. Luckily the difference for small graphs is not signigicant and the implementation is capable to take 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 integrers. 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.

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://bio.perl.org/MailList.html - About the mailing lists

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 email or the web: bioperl-bugs@bio.perl.org http://bugzilla.bioperl.org/ Email: heikki@ebi.ac.uk Address: EMBL Outstation, European Bioinformatics Institute Wellcome Trust Genome Campus, Hinxton Cambs. CB10 1SD, United Kingdom 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