Class: Biosphere::TerraformGraph::Graph

Inherits:
Array
  • Object
show all
Defined in:
lib/biosphere/cli/terraformplanning.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



25
26
27
28
 
# File 'lib/biosphere/cli/terraformplanning.rb', line 25

def initialize
    @map = {}
    @edges = []
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



23
24
25
 
# File 'lib/biosphere/cli/terraformplanning.rb', line 23

def edges
  @edges
end

#map ⇒ Object (readonly)

Returns the value of attribute map.



23
24
25
 
# File 'lib/biosphere/cli/terraformplanning.rb', line 23

def map
  @map
end

Instance Method Details

#connect(src_name, dst_name, length = 1) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
 
# 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) ⇒ Object 



55
56
57
58
 
# 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) ⇒ Object 



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
 
# 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) ⇒ Object 



77
78
79
80
81
82
83
84
85
 
# 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) ⇒ Object 



87
88
89
90
91
92
 
# 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) ⇒ Object 



60
61
62
63
64
65
66
67
 
# 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) ⇒ Object 



69
70
71
72
73
74
75
 
# 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) ⇒ Object 



44
45
46
47
48
49
50
51
52
53
 
# 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