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