Class: Zelkova::Graph

Inherits:
Object
  • Object
show all
Extended by:
T::Sig
Defined in:
lib/zelkova/graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(radius = 2) ⇒ Graph

Returns a new instance of Graph.



25
26
27
28
29
30
31
 
# File 'lib/zelkova/graph.rb', line 25

def initialize(radius = 2)
  @root_node = T.let(nil, T.nilable(Zelkova::Node))
  @nodes = T.let([], T::Array[Zelkova::Node])
  @depth = T.let(0, Integer)

  @radius = T.let(T.must(radius), Integer)
end

Instance Attribute Details

#depth ⇒ Object (readonly)

Returns the value of attribute depth.



19
20
21
 
# File 'lib/zelkova/graph.rb', line 19

def depth
  @depth
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



16
17
18
 
# File 'lib/zelkova/graph.rb', line 16

def nodes
  @nodes
end

#radius ⇒ Object

Returns the value of attribute radius.



22
23
24
 
# File 'lib/zelkova/graph.rb', line 22

def radius
  @radius
end

#root_node ⇒ Object (readonly)

Returns the value of attribute root_node.



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

def root_node
  @root_node
end

Instance Method Details

#add_node(word, metadata = {}) ⇒ Object 



41
42
43
44
45
46
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
 
# File 'lib/zelkova/graph.rb', line 41

def add_node(word, metadata = {})
  node = Zelkova::Node.new(word, self, metadata)
  nodes << node

  if @root_node.nil?
    @root_node = node
    @depth = 1
    return node
  end

  current_node = T.let(@root_node, Zelkova::Node)
  node_depth = 1

  loop do
    distance = Eikon::Comparator.compare(current_node.word, word)
    break if distance.zero? # don't add if it's already in the graph

    edge = current_node.edges.select { |edge| edge.weight == distance }

    unless edge.empty?
      current_node = T.must(edge.first).end_node
      node_depth += 1
      next
    end

    current_node.add_edge(node, distance)
    break
  end

  @depth = node_depth if node_depth > @depth

  node
end

#reset ⇒ Object 



34
35
36
37
38
 
# File 'lib/zelkova/graph.rb', line 34

def reset
  @root_node = nil
  @nodes = []
  @depth = 0
end

#search(query) ⇒ Object 



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

def search(query)
  radius = @radius
  candidate_nodes = []
  candidate_edges = []

  # just so we can start this out
  candidate_edges << Zelkova::Edge.new(T.must(@root_node), T.must(@root_node), 0)

  loop do
    node = candidate_edges.pop.end_node

    distance = Eikon::Comparator.compare(query, node.word)
    candidate_nodes << { node: node, distance: distance } if distance <= radius

    node.edges.each do |edge|
      if edge.weight > (distance - radius) || edge.weight < (distance + radius)
        candidate_edges << edge
      end
    end

    break if candidate_edges.empty?
  end

  candidate_nodes.sort_by! { |candidate_node| candidate_node[:distance] }
  candidate_nodes
end