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 coor‐
36 dinate systems in a graph that defines the relationships between them.
37 This class is primarely designed to analyze gene-related coordinate
38 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 algo‐
48 rithm is fast and greedy and requires all weights to be positive. All
49 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 impler and faster breadth-first would be enough. Luckily
52 the difference for small graphs is not signigicant and the implementa‐
53 tion is capable to take weights into account if needed at some later
54 time.
55 Input format
57 The graph needs to be primed using a hash of hashes where there is a
59 key for each node. The second keys are the names of the downstream
60 neighboring nodes and values are the weights for reaching them. Here is
61 part of the gene coordiante system graph::
62 $hash = {
64 '6' => undef,
65 '3' => {
66 '6' => 1
67 },
68 '2' => {
69 '6' => 1,
70 '4' => 1,
71 '3' => 1
72 },
73 '1' => {
74 '2' => 1
75 },
76 '4' => {
77 '5' => 1
78 },
79 '5' => undef
80 };
81 Note that the names need to be positive integrers. Root should be '1'
83 and directness of the graph is taken advantage of to speed calculations
84 by assuming that downsream nodes always have larger number as name.
85 An alternative (shorter) way of describing input is to use hash of
87 arrays. See Bio::Coordinate::Graph::hash_of_arrays.
88
90 Mailing Lists
91 User feedback is an integral part of the evolution of this and other
93 Bioperl modules. Send your comments and suggestions preferably to the
94 Bioperl mailing lists Your participation is much appreciated.
95 bioperl-l@bioperl.org - General discussion
97 http://bioperl.org/wiki/Mailing_lists - About the mailing lists
98 Reporting Bugs
100 report bugs to the Bioperl bug tracking system to help us keep track
102 the bugs and their resolution. Bug reports can be submitted via the
103 web:
104 http://bugzilla.open-bio.org/
106
108 Email: heikki-at-bioperl-dot-org
109
111 The rest of the documentation details each of the object methods.
112 Internal methods are usually preceded with a _
113 Graph structure input methods
115 graph
117 Title : graph
119 Usage : $obj->graph($my_graph)
120 Function: Read/write method for the graph structure
121 Example :
122 Returns : hash of hashes grah structure
123 Args : reference to a hash of hashes
124 hash_of_arrays
126 Title : hash_of_arrays
128 Usage : $obj->hash_of_array(%hasharray)
129 Function: An alternative method to read in the graph structure.
130 Hash arrays are easier to type. This method converts
131 arrays into hashes and assigns equal values "1" to
132 weights.
133 Example : Here is an example of simple structure containing a graph.
135 my $DAG = {
137 6 => [],
138 5 => [],
139 4 => [5],
140 3 => [6],
141 2 => [3, 4, 6],
142 1 => [2]
143 };
144 Returns : hash of hashes graph structure
146 Args : reference to a hash of arrays
147 Methods for determining the shortest path in the graph
149 shortest_path
151 Title : shortest_path
153 Usage : $obj->shortest_path($a, $b);
154 Function: Method for retrieving the shortest path between nodes.
155 If the start node remains the same, the method is sometimes
156 able to use cached results, otherwise it will recalculate
157 the paths.
158 Example :
159 Returns : array of node names, only the start node name if no path
160 Args : name of the start node
161 : name of the end node
162 dijkstra
164 Title : dijkstra
166 Usage : $graph->dijkstra(1);
167 Function: Implements Dijkstra's algorithm.
168 Returns or sets a list of mappers. The returned path
169 description is always directed down from the root.
170 Called from shortest_path().
171 Example :
172 Returns : Reference to a hash of hashes representing a linked list
173 which contains shortest path down to all nodes from the start
174 node. E.g.:
175 $res = {
177 '2' => {
178 'prev' => '1',
179 'dist' => 1
180 },
181 '1' => {
182 'prev' => undef,
183 'dist' => 0
184 },
185 };
186 Args : name of the start node
188perl v5.8.8 2007-05-07 Bio::Coordinate::Graph(3)