class WeightedGraph
Public Class Methods
new()
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 2 def initialize @adjacency_list = Hash.new { |h, k| h[k] = {} } end
Public Instance Methods
[](id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 6 def [](id) @adjacency_list[id] end
add_vertex(id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 10 def add_vertex(id) @adjacency_list[id] end
adjacent?(id1, id2)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 28 def adjacent?(id1, id2) raise RuntimeError.new("#{id1} is not a Vertex") unless @adjacency_list.include?(id1) raise RuntimeError.new("#{id2} is not a Vertex") unless @adjacency_list.include?(id2) @adjacency_list[id1].include?(id2) end
adjacent_vertices(id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 34 def adjacent_vertices(id) raise RuntimeError.new("#{id} is not a Vertex") unless @adjacency_list.include?(id) @adjacency_list[id] end
create_edge(id1, id2, weight)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 18 def create_edge(id1, id2, weight) @adjacency_list[id1][id2] = weight @adjacency_list[id2][id1] = weight end
delete_edge(id1, id2)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 23 def delete_edge(id1, id2) @adjacency_list[id1].delete(id2) @adjacency_list[id2].delete(id1) end
delete_vertex(id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 14 def delete_vertex(id) @adjacency_list.delete(id) end
highest_weight_adjacent(id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 39 def highest_weight_adjacent(id) adjacent_vertices = self.adjacent_vertices(id) return nil if adjacent_vertices.empty? highest = nil highest_weight = nil adjacent_vertices.each do |vertex, weight| if highest_weight == nil || weight > highest_weight highest = vertex highest_weight = weight end end highest end
lowest_weight_adjacent(id)
click to toggle source
# File lib/data_structures/weighted_graph.rb, line 55 def lowest_weight_adjacent(id) adjacent_vertices = self.adjacent_vertices(id) return nil if adjacent_vertices.empty? lowest = nil lowest_weight = nil adjacent_vertices.each do |vertex, weight| if lowest_weight == nil || weight < lowest_weight lowest = vertex lowest_weight = weight end end lowest end