Class: Bio::AssemblyGraphAlgorithms::Dijkstra
- Inherits:
-
Object
- Object
- Bio::AssemblyGraphAlgorithms::Dijkstra
- Includes:
- FinishM::Logging
- Defined in:
- lib/assembly/dijkstra.rb
Defined Under Namespace
Classes: DistancedOrientedNode
Instance Method Summary collapse
-
#min_distances(graph, initial_oriented_node, options = {}) ⇒ Object
Return an array of DistancedOrientedNode objects, those reachable from the initial_oriented_node.
- #min_distances_from_many_nodes_in_both_directions(graph, nodes, options = {}) ⇒ Object
-
#min_distances_in_both_directions(graph, node, options = {}) ⇒ Object
like #min_distances except explores in both directions.
Methods included from FinishM::Logging
Instance Method Details
#min_distances(graph, initial_oriented_node, options = {}) ⇒ Object
Return an array of DistancedOrientedNode objects, those reachable from the initial_oriented_node. options: :leash_length => max distance explored,
can be set to nil to search indefinitely
:ignore_directions: => true or false (default). If true, explore direction-independently.
i.e. if 1s->3s and 2s->3s, then include 2s in the returned set of min_distances
and continue exploring from 2s. Return each found node twice, once for each direction
:neighbour_finder => an object that responds to #neighbours(oriented_node) and
returns an array of Bio::FinishM::PairedEndNeighbourFinder::Neighbour objects
default: just search using OrientedNode#next_neighbours
:max_nodes => maximum number of nodes to return, to prevent out of control
exploring of the graph. If there is plenty of nodes to explore, then the
length of the returned hash is options[:max_nodes]+1 (+1 because the starting
node is included). It will probably be longer if :ignore_directions == true, in that
case the number of node_ids is constrained. It may also be longer if there is ties
at the edges of the constrained exploration.
Returns a Hash of [node_id, first_side] => distance
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
# File 'lib/assembly/dijkstra.rb', line 25 def min_distances(graph, initial_oriented_node, ={}) pqueue = DS::AnyPriorityQueue.new {|a,b| a < b} first = DistancedOrientedNode.new first.node = initial_oriented_node.node first.first_side = initial_oriented_node.first_side first.distance = 0 pqueue.push first, first.distance to_return = {} first_node = true found_nodes = Set.new([first.node.node_id]) while min_distanced_node = pqueue.shift # Add/overwrite the current one to_return[min_distanced_node.to_settable] = min_distanced_node.distance log.debug "Working from #{min_distanced_node.inspect}" if log.debug? if [:leash_length] and min_distanced_node.distance > [:leash_length] # we are passed leash length, and this is the nearest node. So we are finito. log.debug "passed the leash length, cutting short our travels" if log.debug? break end if [:max_nodes] and found_nodes.length > [:max_nodes] log.debug "passed max-nodes threshold and have #{found_nodes.length} nodes" if log.debug? # remove extras that may have been queued if we are over the limit distances_direction_agnostic = {} to_return.each do |key, distance| prev = distances_direction_agnostic[key[0]] if prev.nil? or prev > distance distances_direction_agnostic[key[0]] = distance end end if distances_direction_agnostic.length > [:max_nodes] sorted = distances_direction_agnostic.to_a.sort{|a,b| a[1]<=>b[1]} # deal with ties i.e. at the edge there can be multiple neighbours last_distance = sorted[[:max_nodes]][1] # only keep those nodes that are sufficiently close to_return.select! do |key, distance| distance <= last_distance end end break end # Queue nodes after this one current_distance = min_distanced_node.distance # Find neighbouring nodes neighbours = nil if [:neighbour_finder] neighbours = [:neighbour_finder].neighbours(min_distanced_node) else neighbours = min_distanced_node.next_neighbours(graph) end # explore each neighbour node neighbours.each do |onode| found_nodes << onode.node.node_id new_distance = current_distance if [:neighbour_finder] # Don't use negative distances as this algorithm cannot handle it, and it is impossible # anyway if onode.distance > 0 new_distance += onode.distance else new_distance += 0 end end unless first_node new_distance += min_distanced_node.node.length_alone end if to_return[onode.to_settable] and to_return[onode.to_settable] <= new_distance # We already know a shorter path to this neighbour, so ignore it log.debug "Already seen this node at the same or shorter distance, going no further" if log.debug? else log.debug "Queuing new distance for neighbour: #{onode}: #{new_distance}" if log.debug? # new shortest distance found. queue it up distanced_node = DistancedOrientedNode.new distanced_node.node = onode.node distanced_node.first_side = onode.first_side distanced_node.distance = new_distance to_return[onode.to_settable] = new_distance pqueue.push distanced_node, new_distance if [:ignore_directions] reverse = DistancedOrientedNode.new reverse.node = onode.node reverse.first_side = onode.reverse.first_side reverse.distance = new_distance to_return[onode.to_settable] = new_distance pqueue.push reverse, new_distance end end end first_node = false end # if ignore directions, then fixup the return so that each direction is included if [:ignore_directions] new_to_return = {} to_return.each do |key, distance| keys = [ Bio::Velvet::Graph::OrientedNodeTrail::START_IS_FIRST, Bio::Velvet::Graph::OrientedNodeTrail::END_IS_FIRST].collect do |direction| [key[0], direction] end new_distance = keys.collect{|k| to_return[k]}.reject{|d| d.nil?}.min keys.each do |key| new_to_return[key] = new_distance end end to_return = new_to_return end return to_return end |
#min_distances_from_many_nodes_in_both_directions(graph, nodes, options = {}) ⇒ Object
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 |
# File 'lib/assembly/dijkstra.rb', line 167 def min_distances_from_many_nodes_in_both_directions(graph, nodes, ={}) all_min_distances = {} nodes.each do |node| [ Bio::Velvet::Graph::OrientedNodeTrail::START_IS_FIRST, Bio::Velvet::Graph::OrientedNodeTrail::END_IS_FIRST, ].each do |direction| onode = Bio::Velvet::Graph::OrientedNodeTrail::OrientedNode.new(node, direction) min_distances = min_distances(graph, onode, ) min_distances.each do |node_direction, distance| current = all_min_distances[node_direction] unless current and current > distance all_min_distances[node_direction] = distance end end end end return all_min_distances end |
#min_distances_in_both_directions(graph, node, options = {}) ⇒ Object
like #min_distances except explores in both directions
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
# File 'lib/assembly/dijkstra.rb', line 149 def min_distances_in_both_directions(graph, node, ={}) all_min_distances = {} [ Bio::Velvet::Graph::OrientedNodeTrail::START_IS_FIRST, Bio::Velvet::Graph::OrientedNodeTrail::END_IS_FIRST, ].each do |direction| onode = Bio::Velvet::Graph::OrientedNodeTrail::OrientedNode.new(node, direction) min_distances = min_distances(graph, onode, ) min_distances.each do |node_direction, distance| current = all_min_distances[node_direction] unless current and current > distance all_min_distances[node_direction] = distance end end end return all_min_distances end |