class WeightedGraph::Graph
Graph
API
Public Class Methods
new(edges = Hash.new(0))
click to toggle source
Initialize a graph with an optional adjacency list
# File lib/weighted_graph/graph.rb, line 8 def initialize(edges = Hash.new(0)) @edges = edges end
Public Instance Methods
add_edge(source, destination, weight)
click to toggle source
Add directed edge (source, destination) to the graph with given weight
# File lib/weighted_graph/graph.rb, line 13 def add_edge(source, destination, weight) if @edges.key?(source) @edges[source][destination] = weight else @edges[source] = { destination => weight } end end
add_undirected_edge(vertex_a, vertex_b, weight)
click to toggle source
Add undirected edge (vertex_a, vertex_b) to the graph with given weight
# File lib/weighted_graph/graph.rb, line 22 def add_undirected_edge(vertex_a, vertex_b, weight) add_edge(vertex_a, vertex_b, weight) add_edge(vertex_b, vertex_a, weight) end
contains_edge?(source, destination)
click to toggle source
Return true iff the graph contains directed edge (source, destination)
# File lib/weighted_graph/graph.rb, line 39 def contains_edge?(source, destination) @edges.key?(source) && @edges[source].key?(destination) end
get_adjacent_vertices(source)
click to toggle source
Returns the set of vertices v_i where edge (source, v_i) is in the graph
# File lib/weighted_graph/graph.rb, line 54 def get_adjacent_vertices(source) adjacent_array = [] if @edges.key?(source) adjacent_array = @edges[source].map { |dst, _weight| dst } end Set.new(adjacent_array) end
get_edge_weight(source, destination)
click to toggle source
Returns the weight of directed edge (source, destination), or returns Float::INFINITY if no such edge exists
# File lib/weighted_graph/graph.rb, line 45 def get_edge_weight(source, destination) if contains_edge?(source, destination) @edges[source][destination] else Float::INFINITY end end
remove_edge(source, destination)
click to toggle source
Remove directed edge (source, destination) from the graph
# File lib/weighted_graph/graph.rb, line 28 def remove_edge(source, destination) @edges[source].delete(destination) if @edges.key?(source) end
remove_undirected_edge(vertex_a, vertex_b)
click to toggle source
Remove undirected edge (vertex_a, vertex_b) from the graph
# File lib/weighted_graph/graph.rb, line 33 def remove_undirected_edge(vertex_a, vertex_b) remove_edge(vertex_a, vertex_b) remove_edge(vertex_b, vertex_a) end