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