Class: Kruskal::MinimumSpanningTree

Inherits:
Object
  • Object
show all
Defined in:
lib/kruskal/minimum_spanning_tree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinimumSpanningTree

Returns a new instance of MinimumSpanningTree.



5
6
7
 
# File 'lib/kruskal/minimum_spanning_tree.rb', line 5

def initialize
  @forest = Forest.new
end

Instance Attribute Details

#forest ⇒ Object

Returns the value of attribute forest.



3
4
5
 
# File 'lib/kruskal/minimum_spanning_tree.rb', line 3

def forest
  @forest
end

Instance Method Details

#add(value = 0, source, target) ⇒ Object 



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/kruskal/minimum_spanning_tree.rb', line 9

def add(value = 0, source, target)
  # Here is the full algorithm
  tree_source = find_tree_for(source)
  tree_target = find_tree_for(target)
  if tree_source.nil? && tree_target.nil?
    new_tree(value, source, target)
  elsif tree_source && tree_target.nil?
    tree_source.add(value, source, target)
  elsif tree_source.nil? && tree_target
    tree_target.add(value, source, target)
  elsif tree_source != tree_target
    tree_source.merge!(tree_target)
    tree_source.add(value, source, target)
  end
end

#run(data) ⇒ Object 



25
26
27
28
29
 
# File 'lib/kruskal/minimum_spanning_tree.rb', line 25

def run(data)
  data.each do |relation|
    add(*relation)
  end
end