class GADDAG::Node
Represents a node in the GADDAG
data structure
Attributes
A mapping of letters to arcs
Public Class Methods
Initializes a GADDAG
node @return [Node]
# File lib/gaddag/node.rb, line 15 def initialize @outgoing_arcs = {} end
Public Instance Methods
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
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
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
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
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
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
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
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
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
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