Class: Graph

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

Direct Known Subclasses

DirectedGraph

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



4
5
6
 
# File 'lib/data_structures/graph.rb', line 4

def initialize
  @adjacency_list = Hash.new { |h, k| h[k] = Set.new }
end

Instance Method Details

#[](id) ⇒ Object 



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

def [](id)
  @adjacency_list[id]
end

#add_vertex(id) ⇒ Object

Raises:

  • (RuntimeError) 


12
13
14
15
 
# File 'lib/data_structures/graph.rb', line 12

def add_vertex(id)
  raise RuntimeError.new("#{id} is already a Vertex") if @adjacency_list.include?(id)
  @adjacency_list[id]
end

#adjacent?(id1, id2) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (RuntimeError) 


36
37
38
39
40
 
# File 'lib/data_structures/graph.rb', line 36

def adjacent?(id1, id2)
  raise RuntimeError.new("#{id1} is not a Vertex") unless @adjacency_list.include?(id1)
  raise RuntimeError.new("#{id2} is not a Vertex") unless @adjacency_list.include?(id2)
  @adjacency_list[id1].include?(id2)
end

#adjacent_vertices(id) ⇒ Object

Raises:

  • (RuntimeError) 


42
43
44
45
 
# File 'lib/data_structures/graph.rb', line 42

def adjacent_vertices(id)
  raise RuntimeError.new("#{id} is not a Vertex") unless @adjacency_list.include?(id)
  @adjacency_list[id]
end

#breadth_first_search(target_id = nil, start_id = nil, &prc) ⇒ Object

Raises:

  • (ArgumentError) 


77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/data_structures/graph.rb', line 77

def breadth_first_search(target_id=nil, start_id=nil, &prc)
  raise ArgumentError.new('Must pass either a target value or a block') unless (target_id || prc) && !(target_id && prc)
  prc ||= Proc.new { |vertex| vertex == target_id }

  return false if @adjacency_list.empty?
  start_id ||= @adjacency_list.first.first
  vertex_queue = [start_id]

  memo = Set.new
  until vertex_queue.empty?
    current_vertex = vertex_queue.shift
    return true if prc.call(current_vertex)

    current_adjacency_list = @adjacency_list[current_vertex]

    vertex_queue += current_adjacency_list.to_a.reject { |vertex| memo.include?(vertex) }
    memo.add(current_vertex)
  end

  false
end

#create_edge(id1, id2) ⇒ Object

Raises:

  • (RuntimeError) 


22
23
24
25
26
27
 
# File 'lib/data_structures/graph.rb', line 22

def create_edge(id1, id2)
  raise RuntimeError.new("#{id1} is not a Vertex") unless @adjacency_list.include?(id1)
  raise RuntimeError.new("#{id2} is not a Vertex") unless @adjacency_list.include?(id2)
  @adjacency_list[id1].add(id2)
  @adjacency_list[id2].add(id1)
end

#delete_edge(id1, id2) ⇒ Object

Raises:

  • (RuntimeError) 


29
30
31
32
33
34
 
# File 'lib/data_structures/graph.rb', line 29

def delete_edge(id1, id2)
  raise RuntimeError.new("#{id1} is not a Vertex") unless @adjacency_list.include?(id1)
  raise RuntimeError.new("#{id1} is not connected to #{id2}") unless @adjacency_list[id1].include?(id2)
  @adjacency_list[id1].delete(id2)
  @adjacency_list[id2].delete(id1)
end

#delete_vertex(id) ⇒ Object

Raises:

  • (RuntimeError) 


17
18
19
20
 
# File 'lib/data_structures/graph.rb', line 17

def delete_vertex(id)
  raise RuntimeError.new("#{id} is not a Vertex") unless @adjacency_list.include?(id)
  @adjacency_list.delete(id)
end

#depth_first_search(target_id = nil, start_id = nil, &prc) ⇒ Object

Raises:

  • (ArgumentError) 


47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/data_structures/graph.rb', line 47

def depth_first_search(target_id=nil, start_id=nil, &prc)
  raise ArgumentError.new('Must pass either a target value or a block') unless (target_id || prc) && !(target_id && prc)
  prc ||= Proc.new { |vertex| vertex == target_id }

  return false if @adjacency_list.empty?
  current_vertex = start_id || @adjacency_list.first.first
  @memo = Set.new unless start_id
  @memo ||= Set.new

  unless @memo.include?(current_vertex)
    return true if prc.call(current_vertex)
    @memo.add(current_vertex)
  end

  current_adjacency_list = @adjacency_list[current_vertex]
  current_adjacency_list.each do |vertex|
    if @memo.include?(vertex)
      next
    else
      @memo.add(vertex)
    end

    return true if prc.call(vertex)
    result = depth_first_search(nil, vertex, &prc)
    return result if result
  end

  false
end