Class: Graphunk::WeightedUndirectedGraph

Inherits:
WeightedGraph show all
Defined in:
lib/graphunk/weighted_undirected_graph.rb

Instance Attribute Summary

Attributes inherited from WeightedGraph

#weights

Instance Method Summary collapse

Methods inherited from WeightedGraph

#initialize

Methods inherited from Graph

#add_vertex, #add_vertices, #edge_exists?, #edges, #edges_on_vertex, #initialize, #neighbors_of_vertex, #remove_vertex, #vertex_exists?, #vertices

Constructor Details

This class inherits a constructor from Graphunk::WeightedGraph

Instance Method Details

#add_edge(v, u, w) ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
 
# File 'lib/graphunk/weighted_undirected_graph.rb', line 4

def add_edge(v, u, w)
  if edge_exists?(v, u)
    raise ArgumentError, "This edge already exists"
  elsif vertex_exists?(v) && vertex_exists?(u)
    ordered_vertices = order_vertices(v, u)
    @representation[ordered_vertices.first] << ordered_vertices.last
    @weights[ordered_vertices] = w
  else
    raise ArgumentError, "One of the vertices referenced does not exist in the graph"
  end
end

#adjust_weight(v, u, w) ⇒ Object 



34
35
36
37
38
39
40
 
# File 'lib/graphunk/weighted_undirected_graph.rb', line 34

def adjust_weight(v, u, w)
  if edge_exists?(v, u)
    @weights[order_vertices(v,u)] = w
  else
    raise ArgumentError, "That edge does not exist in the graph"
  end
end

#edge_weight(v, u) ⇒ Object 



26
27
28
29
30
31
32
 
# File 'lib/graphunk/weighted_undirected_graph.rb', line 26

def edge_weight(v, u)
  if edge_exists?(v,u)
    @weights[order_vertices(v,u)]
  else
    raise ArgumentError, "That edge does not exist in the graph"
  end
end

#minimum_spanning_tree ⇒ Object

Prim’s Algorithm



43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/graphunk/weighted_undirected_graph.rb', line 43

def minimum_spanning_tree
  forest = WeightedUndirectedGraph.new
  forest.add_vertex(vertices.first)
  until forest.vertices.sort == vertices.sort
    minimum_edge = edges_to_examine(forest.vertices).min_by { |edge| weights[edge] }
    vertex_to_add = forest.vertices.include?(minimum_edge.first) ? minimum_edge.last : minimum_edge.first
    forest.add_vertex(vertex_to_add)
    forest.add_edge(minimum_edge.first, minimum_edge.last, weights[minimum_edge])
  end
  forest
end

#remove_edge(v, u) ⇒ Object 



16
17
18
19
20
21
22
23
24
 
# File 'lib/graphunk/weighted_undirected_graph.rb', line 16

def remove_edge(v, u)
  if edge_exists?(v, u)
    ordered_vertices = order_vertices(v, u)
    @representation[ordered_vertices.first].delete(ordered_vertices.last)
    remove_weight(v, u)
  else
    raise ArgumentError, "That edge does not exist in the graph"
  end
end