forked from revskill10/algorithms2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
prims.rb
66 lines (52 loc) · 2.2 KB
/
prims.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Prim's Minimum Spanning Tree Algorithm - Naive version
def file
@file ||= File.readlines("edges.txt")
end
def header
@header ||= file.take(1)[0]
end
def number_of_nodes
@number_of_nodes ||= header.split(" ")[0].to_i
end
def create_adjacency_matrix
adjacency_matrix = [].tap { |m| number_of_nodes.times { m << Array.new(number_of_nodes) } }
file.drop(1).map { |x| x.gsub(/\n/, "").split(" ").map(&:to_i) }.each do |(node1, node2, weight)|
adjacency_matrix[node1 - 1][node2 - 1] = weight
adjacency_matrix[node2 - 1][node1 - 1] = weight
end
adjacency_matrix
end
def find_cheapest_edge(adjacency_matrix, nodes_spanned_so_far, number_of_nodes)
available_nodes = (0..number_of_nodes-1).to_a.reject { |node_index| nodes_spanned_so_far.include?(node_index + 1) }
cheapest_edges = available_nodes.inject([]) do |acc, node_index|
get_edges(adjacency_matrix, node_index).select { |_, other_node_index| nodes_spanned_so_far.include?(other_node_index + 1) }.each do |weight, other_node_index|
acc << { :start => node_index + 1, :end => other_node_index + 1, :weight => weight }
end
acc
end
cheapest_edges.sort { |x,y| x[:weight] <=> y[:weight] }.first
end
def get_edges(adjacency_matrix, node_index)
adjacency_matrix[node_index].each_with_index.reject { |edge, index| edge.nil? }
end
def select_first_edge(adjacency_matrix)
starting_node = 1
cheapest_edges = get_edges(adjacency_matrix, 0).inject([]) do |all_edges, (edge, index)|
all_edges << { :start => starting_node, :end => index + 1, :weight => edge }
all_edges
end
cheapest_edges.sort { |x,y| x[:weight] <=> y[:weight] }.first
end
def nodes_left_to_cover
(1..number_of_nodes).to_a - @nodes_spanned_so_far
end
# Prim's algorithm
adjacency_matrix = create_adjacency_matrix
first_edge = select_first_edge(adjacency_matrix)
@nodes_spanned_so_far, @edges = [first_edge[:start], first_edge[:end]], [first_edge]
while !nodes_left_to_cover.empty?
cheapest_edge = find_cheapest_edge(adjacency_matrix, @nodes_spanned_so_far, number_of_nodes)
@edges << cheapest_edge
@nodes_spanned_so_far << cheapest_edge[:start]
end
puts "edges: #{@edges}, total spanning tree cost #{@edges.inject(0) {|acc, edge| acc + edge[:weight]}}"