Class: WeightedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures/weighted_graph.rb

Direct Known Subclasses

WeightedDirectedGraph

Instance Method Summary collapse

Constructor Details

#initialize ⇒ WeightedGraph

Returns a new instance of WeightedGraph.



2
3
4
 
# File 'lib/data_structures/weighted_graph.rb', line 2

def initialize
  @adjacency_list = Hash.new { |h, k| h[k] = {} }
end

Instance Method Details

#[](id) ⇒ Object 



6
7
8
 
# File 'lib/data_structures/weighted_graph.rb', line 6

def [](id)
  @adjacency_list[id]
end

#add_vertex(id) ⇒ Object 



10
11
12
 
# File 'lib/data_structures/weighted_graph.rb', line 10

def add_vertex(id)
  @adjacency_list[id]
end

#adjacent?(id1, id2) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (RuntimeError) 


28
29
30
31
32
 
# 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) ⇒ Object

Raises:

  • (RuntimeError) 


34
35
36
37
 
# 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) ⇒ Object 



18
19
20
21
 
# 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) ⇒ Object 



23
24
25
26
 
# 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) ⇒ Object 



14
15
16
 
# File 'lib/data_structures/weighted_graph.rb', line 14

def delete_vertex(id)
  @adjacency_list.delete(id)
end

#highest_weight_adjacent(id) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# 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) ⇒ Object 



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# 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