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