class Graphunk::WeightedDirectedGraph
Public Instance Methods
add_edge(v, u, w)
click to toggle source
# File lib/graphunk/weighted_directed_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) @representation[v] << u @weights[[v,u]] = 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_directed_graph.rb, line 32 def adjust_weight(v, u, w) if edge_exists?(v, u) @weights[[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_directed_graph.rb, line 24 def edge_weight(v, u) if edge_exists?(v,u) @weights[[v,u]] else raise ArgumentError, "That edge does not exist in the graph" end end
neighbors_of_vertex(v)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 40 def neighbors_of_vertex(v) if vertex_exists?(v) @representation[v] else raise ArgumentError, "That vertex does not exist in the graph" end end
remove_edge(v, u)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 15 def remove_edge(v, u) if edge_exists?(v, u) @representation[v].delete(u) @weights.delete([v,u]) else raise ArgumentError, "That edge does not exist in the graph" end end
shortest_path(v, u)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 56 def shortest_path(v, u) if vertex_exists?(u) [].tap do |s| previous = single_source_shortest_path_previous(v) while previous[u] s.insert(0, u) u = previous[u] end s.insert(0, v) end else raise ArgumentError, "A specified vertex does not exist in the graph" end end
shortest_path_distance(v, u)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 48 def shortest_path_distance(v, u) if vertex_exists?(u) single_source_shortest_path_distances(v)[u] else raise ArgumentError, "A specified vertex does not exist in the graph" end end
Private Instance Methods
edge_exists?(v, u)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 111 def edge_exists?(v, u) edges.include?([v,u]) end
single_source_shortest_path(source)
click to toggle source
Dijsktra’s Algorithm
# File lib/graphunk/weighted_directed_graph.rb, line 74 def single_source_shortest_path(source) raise ArgumentError, "A specified vertex does not exist in the graph" unless vertex_exists?(source) distance = {} previous = {} vertices.each do |vertex| distance[vertex] = Float::INFINITY previous[vertex] = nil end distance[source] = 0 q = vertices until q.empty? u = q.delete(q.min_by { |vertex| distance[vertex] }) break if distance[u] == Float::INFINITY neighbors_of_vertex(u).each do |v| alt = distance[u] + edge_weight(u, v) if alt < distance[v] distance[v] = alt previous[v] = u end end end {distance: distance, previous: previous} end
single_source_shortest_path_distances(source)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 103 def single_source_shortest_path_distances(source) single_source_shortest_path(source)[:distance] end
single_source_shortest_path_previous(source)
click to toggle source
# File lib/graphunk/weighted_directed_graph.rb, line 107 def single_source_shortest_path_previous(source) single_source_shortest_path(source)[:previous] end