class GADDAG::Node

Represents a node in the GADDAG data structure

Attributes

outgoing_arcs[R]

A mapping of letters to arcs

Public Class Methods

new() click to toggle source

Initializes a GADDAG node @return [Node]

# File lib/gaddag/node.rb, line 15
def initialize
  @outgoing_arcs = {}
end

Public Instance Methods

arc?(letter) click to toggle source

Checks whether an outgoing arc for the given letter exists @param letter [String] the letter to check for @return [Boolean] whether the outgoing arc exists

# File lib/gaddag/node.rb, line 32
def arc?(letter)
  @outgoing_arcs.key?(letter.to_sym)
end
create_arc(letter, destination = Node.new) click to toggle source

Creates an outgoing arc for a letter to a destination node @param letter [String] the letter to be added to the path when this arc is followed @param destination [Node] the node to which this arc should point @return [Arc] the newly created arc or an existing arc if one already

exists for this letter
# File lib/gaddag/node.rb, line 25
def create_arc(letter, destination = Node.new)
  @outgoing_arcs[letter.to_sym] ||= Arc.new(destination)
end
create_final_arc(letter, final_letter, destination = Node.new) click to toggle source

Creates a final outgoing arc for a letter to a destination node. Effectively this will add a final letter to the outgoing arc, indicating that a valid word can be formed with it. @see create_arc

# File lib/gaddag/node.rb, line 40
def create_final_arc(letter, final_letter, destination = Node.new)
  create_arc(letter, destination).tap { |arc| arc.add_final_letter(final_letter) }
end
create_final_path(letters, destinations = []) click to toggle source

Creates a path for a list of letters and optional destination nodes, ommiting the last node, and marking the last letter as final @see create_path

# File lib/gaddag/node.rb, line 66
def create_final_path(letters, destinations = [])
  *initial_letters, second_last_letter, last_letter = *letters
  second_last_node = create_path(initial_letters, destinations)

  (destinations[initial_letters.length] || Node.new).tap do |final_destination|
    second_last_node.create_final_arc(second_last_letter, last_letter, final_destination)
  end
end
create_path(letters, destinations = []) click to toggle source

Creates a path for a list of letters and optional destination nodes @param letters [Array<String>] the letters for which the path should be build @param destinations [Array<Node>] the destination nodes which the path should visit @return [Node] the lastly created destination ode

# File lib/gaddag/node.rb, line 48
def create_path(letters, destinations = [])
  letters.zip(destinations).inject(self) do |node, (letter, destination)|
    node.create_arc(letter, destination || Node.new).destination
  end
end
final_path?(letters) click to toggle source

Checks whether a final path exists for the given list of letters @param letters [Array<String>] the letter path to check for @return [Boolean] whether the final path exists

# File lib/gaddag/node.rb, line 78
def final_path?(letters)
  *initial_letters, second_last_letter, last_letter = *letters

  path?(initial_letters) && follow_path(initial_letters).final_paths.any? do |path|
    path == Path.new([second_last_letter, last_letter])
  end
end
final_paths() click to toggle source

Returns all paths from this node that are final. The set of final paths are all paths for which the last arc includes a final letter. For each final letter a seperate path is created. @return [Array<Path>] a list of final paths

# File lib/gaddag/node.rb, line 108
def final_paths
  @outgoing_arcs.reduce([]) do |paths, (letter_sym, arc)|
    paths += arc.final_paths.map { |path| Path.new([letter_sym.to_s] + path) }
  end
end
follow_arc(letter) click to toggle source

Follows a single outgoing arc for a given letter @param letter [String] the letter that should be followed @raise [KeyError] if no outgoing arc exists for the given letter @return [Node] the destination node that the arc for this letter leads to

# File lib/gaddag/node.rb, line 90
def follow_arc(letter)
  @outgoing_arcs.fetch(letter.to_sym).destination
end
follow_path(letters) click to toggle source

Recursively follows a list of letters @param letters [Array<String>] the letters to be followed @raise [KeyError] if an outgoing arc does not exist for a given letter

at the corresponding node

@return [Node] the destination node that the path of letters leads to

# File lib/gaddag/node.rb, line 99
def follow_path(letters)
  return self if letters.empty?
  follow_arc(letters[0]).follow_path(letters[1..-1])
end
path?(letters) click to toggle source

Checks whether a path exists for the given list of letters @param letters [Array<String>] the letter path to check for @return [Boolean] whether the path exists

# File lib/gaddag/node.rb, line 57
def path?(letters)
  return true if letters.empty?
  return false unless arc?(letters.first)
  follow_arc(letters.first).path?(letters[1..-1])
end