class Graphunk::WeightedUndirectedGraph
Public Instance Methods
add_edge(v, u, w)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
Prim’s Algorithm
# 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)
click to toggle source
# 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
Private Instance Methods
edges_to_examine(vertices)
click to toggle source
# File lib/graphunk/weighted_undirected_graph.rb, line 57 def edges_to_examine(vertices) [].tap do |examinable| edges.each do |edge| examinable << edge if (edge & vertices).count == 1 end end end
remove_weight(v, u)
click to toggle source
# File lib/graphunk/weighted_undirected_graph.rb, line 65 def remove_weight(v, u) @weights.delete(order_vertices(v, u)) end