1Bio::Coordinate::Graph(U3s)er Contributed Perl DocumentatBiioon::Coordinate::Graph(3)
2
6 Bio::Coordinate::Graph - Finds shortest path between nodes in a graph
7
9 # get a hash of hashes representing the graph. E.g.:
10 my $hash= {
11 '1' => {
12 '2' => 1
13 },
14 '2' => {
15 '4' => 1,
16 '3' => 1
17 },
18 '3' => undef,
19 '4' => {
20 '5' => 1
21 },
22 '5' => undef
23 };
24 # create the object;
26 my $graph = Bio::Coordinate::Graph->new(-graph => $hash);
27 # find the shortest path between two nodes
29 my $a = 1;
30 my $b = 6;
31 my @path = $graph->shortest_paths($a);
32 print join (", ", @path), "\n";
33
35 This class calculates the shortest path between input and output
36 coordinate systems in a graph that defines the relationships between
37 them. This class is primarely designed to analyze gene-related
38 coordinate systems. See Bio::Coordinate::GeneMapper.
39 Note that this module can not be used to manage graphs.
41 Technically the graph implemented here is known as Directed Acyclic
43 Graph (DAG). DAG is composed of vertices (nodes) and edges (with
44 optional weights) linking them. Nodes of the graph are the coordinate
45 systems in gene mapper.
46 The shortest path is found using the Dijkstra's algorithm. This
48 algorithm is fast and greedy and requires all weights to be positive.
49 All weights in the gene coordinate system graph are currently equal (1)
50 making the graph unweighted. That makes the use of Dijkstra's algorithm
51 an overkill. A simpler and faster breadth-first would be enough.
52 Luckily the difference for small graphs is not significant and the
53 implementation is capable of taking weights into account if needed at
54 some later time.
55 Input format
57 The graph needs to be primed using a hash of hashes where there is a
58 key for each node. The second keys are the names of the downstream
59 neighboring nodes and values are the weights for reaching them. Here is
60 part of the gene coordiante system graph::
61 $hash = {
63 '6' => undef,
64 '3' => {
65 '6' => 1
66 },
67 '2' => {
68 '6' => 1,
69 '4' => 1,
70 '3' => 1
71 },
72 '1' => {
73 '2' => 1
74 },
75 '4' => {
76 '5' => 1
77 },
78 '5' => undef
79 };
80 Note that the names need to be positive integers. Root should be '1'
82 and directness of the graph is taken advantage of to speed calculations
83 by assuming that downsream nodes always have larger number as name.
84 An alternative (shorter) way of describing input is to use hash of
86 arrays. See Bio::Coordinate::Graph::hash_of_arrays.
87
89 Mailing Lists
90 User feedback is an integral part of the evolution of this and other
91 Bioperl modules. Send your comments and suggestions preferably to the
92 Bioperl mailing lists Your participation is much appreciated.
93 bioperl-l@bioperl.org - General discussion
95 http://bioperl.org/wiki/Mailing_lists - About the mailing lists
96 Support
98 Please direct usage questions or support issues to the mailing list:
99 bioperl-l@bioperl.org
101 rather than to the module maintainer directly. Many experienced and
103 reponsive experts will be able look at the problem and quickly address
104 it. Please include a thorough description of the problem with code and
105 data examples if at all possible.
106 Reporting Bugs
108 report bugs to the Bioperl bug tracking system to help us keep track
109 the bugs and their resolution. Bug reports can be submitted via the
110 web:
111 http://bugzilla.open-bio.org/
113
115 Email: heikki-at-bioperl-dot-org
116
118 The rest of the documentation details each of the object methods.
119 Internal methods are usually preceded with a _
120 Graph structure input methods
122 graph
123 Title : graph
124 Usage : $obj->graph($my_graph)
125 Function: Read/write method for the graph structure
126 Example :
127 Returns : hash of hashes grah structure
128 Args : reference to a hash of hashes
129 hash_of_arrays
131 Title : hash_of_arrays
132 Usage : $obj->hash_of_array(%hasharray)
133 Function: An alternative method to read in the graph structure.
134 Hash arrays are easier to type. This method converts
135 arrays into hashes and assigns equal values "1" to
136 weights.
137 Example : Here is an example of simple structure containing a graph.
139 my $DAG = {
141 6 => [],
142 5 => [],
143 4 => [5],
144 3 => [6],
145 2 => [3, 4, 6],
146 1 => [2]
147 };
148 Returns : hash of hashes graph structure
150 Args : reference to a hash of arrays
151 Methods for determining the shortest path in the graph
153 shortest_path
154 Title : shortest_path
155 Usage : $obj->shortest_path($a, $b);
156 Function: Method for retrieving the shortest path between nodes.
157 If the start node remains the same, the method is sometimes
158 able to use cached results, otherwise it will recalculate
159 the paths.
160 Example :
161 Returns : array of node names, only the start node name if no path
162 Args : name of the start node
163 : name of the end node
164 dijkstra
166 Title : dijkstra
167 Usage : $graph->dijkstra(1);
168 Function: Implements Dijkstra's algorithm.
169 Returns or sets a list of mappers. The returned path
170 description is always directed down from the root.
171 Called from shortest_path().
172 Example :
173 Returns : Reference to a hash of hashes representing a linked list
174 which contains shortest path down to all nodes from the start
175 node. E.g.:
176 $res = {
178 '2' => {
179 'prev' => '1',
180 'dist' => 1
181 },
182 '1' => {
183 'prev' => undef,
184 'dist' => 0
185 },
186 };
187 Args : name of the start node
189perl v5.12.0 2010-04-29 Bio::Coordinate::Graph(3)