.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "Bio::Coordinate::Graph 3pm"
.TH Bio::Coordinate::Graph 3pm "2020-11-24" "perl v5.32.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Bio::Coordinate::Graph \- Finds shortest path between nodes in a graph.
.SH "VERSION"
.IX Header "VERSION"
version 1.007001
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 10
\&  # get a hash of hashes representing the graph. E.g.:
\&  my $hash= {
\&             \*(Aq1\*(Aq => {
\&                     \*(Aq2\*(Aq => 1
\&                    },
\&             \*(Aq2\*(Aq => {
\&                     \*(Aq4\*(Aq => 1,
\&                     \*(Aq3\*(Aq => 1
\&                    },
\&             \*(Aq3\*(Aq => undef,
\&             \*(Aq4\*(Aq => {
\&                     \*(Aq5\*(Aq => 1
\&                    },
\&             \*(Aq5\*(Aq => 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), "\en";
.Ve
.SH "DESCRIPTION"
.IX Header "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.
.PP
Note that this module can not be used to manage graphs.
.PP
Technically the graph implemented here is known as Directed Acyclic
Graph (\s-1DAG\s0). \s-1DAG\s0 is composed of vertices (nodes) and edges (with
optional weights) linking them. Nodes of the graph are the coordinate
systems in gene mapper.
.PP
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.
.SS "Input format"
.IX Subsection "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:
.PP
.Vb 10
\&    $hash = {
\&             \*(Aq6\*(Aq => undef,
\&             \*(Aq3\*(Aq => {
\&                     \*(Aq6\*(Aq => 1
\&                    },
\&             \*(Aq2\*(Aq => {
\&                     \*(Aq6\*(Aq => 1,
\&                     \*(Aq4\*(Aq => 1,
\&                     \*(Aq3\*(Aq => 1
\&                    },
\&             \*(Aq1\*(Aq => {
\&                     \*(Aq2\*(Aq => 1
\&                    },
\&             \*(Aq4\*(Aq => {
\&                     \*(Aq5\*(Aq => 1
\&                    },
\&             \*(Aq5\*(Aq => undef
\&            };
.Ve
.PP
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.
.PP
An alternative (shorter) way of describing input is to use hash of
arrays. See Bio::Coordinate::Graph::hash_of_arrays.
.SH "METHODS"
.IX Header "METHODS"
.SS "new"
.IX Subsection "new"
.SS "graph"
.IX Subsection "graph"
.Vb 6
\& 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
.Ve
.SS "hash_of_arrays"
.IX Subsection "hash_of_arrays"
.Vb 6
\& 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
.Ve
.SS "shortest_path"
.IX Subsection "shortest_path"
.Vb 10
\& 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
.Ve
.SS "dijkstra"
.IX Subsection "dijkstra"
.Vb 10
\& Title   : dijkstra
\& Usage   : $graph\->dijkstra(1);
\& Function: Implements Dijkstra\*(Aqs 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 = {
\&                      \*(Aq2\*(Aq => {
\&                               \*(Aqprev\*(Aq => \*(Aq1\*(Aq,
\&                               \*(Aqdist\*(Aq => 1
\&                             },
\&                      \*(Aq1\*(Aq => {
\&                               \*(Aqprev\*(Aq => undef,
\&                               \*(Aqdist\*(Aq => 0
\&                             },
\&                    };
\&
\& Args    : name of the start node
.Ve
.SH "FEEDBACK"
.IX Header "FEEDBACK"
.SS "Mailing lists"
.IX Subsection "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 list.  Your participation is much appreciated.
.PP
.Vb 2
\&  bioperl\-l@bioperl.org                  \- General discussion
\&  http://bioperl.org/wiki/Mailing_lists  \- About the mailing lists
.Ve
.SS "Support"
.IX Subsection "Support"
Please direct usage questions or support issues to the mailing list:
\&\fIbioperl\-l@bioperl.org\fR
.PP
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.
.SS "Reporting bugs"
.IX Subsection "Reporting bugs"
Report bugs to the Bioperl bug tracking system to help us keep track
of the bugs and their resolution. Bug reports can be submitted via the
web:
.PP
.Vb 1
\&  https://github.com/bioperl/%%7Bdist%7D
.Ve
.SH "AUTHOR"
.IX Header "AUTHOR"
Heikki Lehvaslaiho <heikki@bioperl.org>
.SH "COPYRIGHT"
.IX Header "COPYRIGHT"
This software is copyright (c) by Heikki Lehvaslaiho.
.PP
This software is available under the same terms as the perl 5 programming language system itself.