Class: WeightedGraph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/weighted_graph/graph.rb

Overview

Graph API

Direct Known Subclasses

PositiveWeightedGraph

Instance Method Summary collapse

Constructor Details

#initialize(edges = Hash.new(0)) ⇒ Graph

Initialize a graph with an optional adjacency list


8
9
10
 
# File 'lib/weighted_graph/graph.rb', line 8

def initialize(edges = Hash.new(0))
  @edges = edges
end

Instance Method Details

#add_edge(source, destination, weight) ⇒ Object

Add directed edge (source, destination) to the graph with given weight


13
14
15
16
17
18
19
 
# 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) ⇒ Object

Add undirected edge (vertex_a, vertex_b) to the graph with given weight


22
23
24
25
 
# 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) ⇒ Boolean

Return true iff the graph contains directed edge (source, destination)

Returns:

  • (Boolean) 

39
40
41
 
# 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) ⇒ Object

Returns the set of vertices v_i where edge (source, v_i) is in the graph


54
55
56
57
58
59
60
 
# 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) ⇒ Object

Returns the weight of directed edge (source, destination), or returns Float::INFINITY if no such edge exists


45
46
47
48
49
50
51
 
# 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) ⇒ Object

Remove directed edge (source, destination) from the graph


28
29
30
 
# 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) ⇒ Object

Remove undirected edge (vertex_a, vertex_b) from the graph


33
34
35
36
 
# 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