Bio::C...:Graph(3pm)

💖 Bio::Coordinate::Graph 💖

User Contributed Perl Documentation — yes bestie, that's the manual name, and we're about to make it make sense.

okay so real talk: this is Bio::Coordinate::Graph, and it does exactly one thing but it does it gorgeously — it finds the shortest path between nodes in a graph. Sit down, hydrate, let's go. 🦋

---

✨ VERSION ✨

version 1.007001 — iconic, no notes. 💅

---

🌸 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 🎀

So what does this class actually do? It calculates the shortest path between input and output coordinate systems, inside a graph that defines the relationships between them. It's primarely (their spelling, not mine, love that for them) built to analyze gene-related coordinate systems — peep Bio::Coordinate::GeneMapper.

⚠️ Important vibe check: this module can not be used to manage graphs. It finds paths. That's the gig. Don't ask it to do your taxes.

Technically speaking, the graph implemented here is known as a Directed Acyclic Graph (DAG). A DAG is composed of vertices (nodes) and edges (with optional weights) linking them. And the nodes of the graph? Those are the coordinate systems in gene mapper. Cute, right? 🧚

The shortest path is found using Dijkstra's algorithm. That algorithm is fast and greedy, and it requires all weights to be positive. All weights in the gene coordinate system graph are currently equal (1), which makes the graph unweighted. Which means using Dijkstra's algorithm here is honestly a little overkill 😭 — a simpler and faster breadth-first would be enough. But 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. So it's giving "prepared, flexible, future-proof." 💅

🦋 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 the values are the weights for reaching them. Here's 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
        };

Heads up on the rules 📋:

• The names need to be positive integers.
• Root should be '1'.
• The directness of the graph is taken advantage of to speed up calculations, by assuming that downstream nodes always have a larger number as their name.

An alternative (shorter) way of describing input is to use a hash of arrays. See Bio::Coordinate::Graph::hash_of_arrays. 🌈

---

👑 METHODS 👑

new

(no docs here, she's just the constructor bestie — go build your object 🫶)

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

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
• Args: 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

---

💌 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 list. 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. (Yes, code and data examples — they're not being dramatic, it genuinely helps. 🙈)

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:

https://github.com/bioperl/%%7Bdist%7D

---

🌟 AUTHOR 🌟

Heikki Lehvaslaiho <heikki@bioperl.org> — thank you for your service, king. 👑

---

📜 COPYRIGHT 📜

This software is copyright (c) by Heikki Lehvaslaiho.

This software is available under the same terms as the perl 5 programming language system itself.

---

and that's the whole page bestie!! 🎀 this one was rendered by perl v5.32.0 on 2020-11-24 — vintage, lowkey iconic, and honestly? it ate. go find your shortest path, you're the main character now. 💖✨🦋