class Biosphere::TerraformGraph::Graph
Attributes
edges[R]
map[R]
Public Class Methods
new()
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 25 def initialize @map = {} @edges = [] end
Public Instance Methods
connect(src_name, dst_name, length = 1)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 30 def connect(src_name, dst_name, length = 1) unless @map.include?(src_name) raise ArgumentError, "No such vertex: #{src_name}" end unless @map.include?(dst_name) raise ArgumentError, "No such vertex: #{dst_name}" end src = @map[src_name] dst = @map[dst_name] @edges.push Edge.new(src, dst, length) end
connect_mutually(vertex1_name, vertex2_name, length = 1)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 55 def connect_mutually(vertex1_name, vertex2_name, length = 1) self.connect vertex1_name, vertex2_name, length self.connect vertex2_name, vertex1_name, length end
dijkstra(src_name, dst_name = nil)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 94 def dijkstra(src_name, dst_name = nil) src = @map[src_name] dst = @map[dst_name] distances = {} previouses = {} self.each do |vertex| distances[vertex] = nil # Infinity previouses[vertex] = nil end distances[src] = 0 vertices = self.clone until vertices.empty? nearest_vertex = vertices.inject do |a, b| next b unless distances[a] next a unless distances[b] next a if distances[a] < distances[b] b end break unless distances[nearest_vertex] # Infinity if dst and nearest_vertex == dst path = path_to_names(get_path(previouses, src, dst)) return { path: path, distance: distances[dst] } end neighbors = vertices.neighbors_by_index(nearest_vertex) neighbors.each do |vertex| alt = distances[nearest_vertex] + vertices.length_between_index(nearest_vertex, vertex) if distances[vertex].nil? or alt < distances[vertex] distances[vertex] = alt previouses[vertex] = nearest_vertex # decrease-key v in Q # ??? end end vertices.delete nearest_vertex end if dst return nil else paths = {} distances.each { |k, v| paths[k] = path_to_names(get_path(previouses, src, k)) } return { paths: paths, distances: distances } end end
length_between(src_name, dst_name)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 77 def length_between(src_name, dst_name) src = @map[src_name] dst = @map[dst_name] @edges.each do |edge| return edge.length if edge.src == src and edge.dst == dst end nil end
length_between_index(src, dst)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 87 def length_between_index(src, dst) @edges.each do |edge| return edge.length if edge.src == src and edge.dst == dst end nil end
neighbors(vertex_name)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 60 def neighbors(vertex_name) vertex = @map[vertex_name] neighbors = [] @edges.each do |edge| neighbors.push edge.dst if edge.src == vertex end return neighbors.uniq.collect { |x| @map.key(x) } end
neighbors_by_index(vertex)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 69 def neighbors_by_index(vertex) neighbors = [] @edges.each do |edge| neighbors.push edge.dst if edge.src == vertex end return neighbors.uniq end
push_name(name)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 44 def push_name(name) if !@map[name] index = @map.length + 1 @map[name] = index self.push(index) return index else return @map[name] end end
Private Instance Methods
get_path(previouses, src, dest)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 148 def get_path(previouses, src, dest) path = get_path_recursively(previouses, src, dest) path.is_a?(Array) ? path.reverse : path end
get_path_recursively(previouses, src, dest)
click to toggle source
Unroll through previouses array until we get to source
# File lib/biosphere/cli/terraformplanning.rb, line 154 def get_path_recursively(previouses, src, dest) return src if src == dest raise ArgumentError, "No path from #{src} to #{dest}" if previouses[dest].nil? [dest, get_path_recursively(previouses, src, previouses[dest])].flatten end
path_to_names(path)
click to toggle source
# File lib/biosphere/cli/terraformplanning.rb, line 139 def path_to_names(path) p = [] path.each do |index| p << @map.key(index) end return p end