class Mazemap::Graph
Graph
object class
@author Evgenii Shevchenko @!attribute [r] graph
@return [NMatrix] graph map matrix
@!attribute [r] queue
@return [Queue] progress queue
@!attribute [r] rows
@return [Integer] number of the rows
@!attribute [r] cols
@return [Integer] number of the cols
Constants
- BLANK
- FINISH
- INF
- START
- VISITED
Attributes
Public Class Methods
Initializes Graph
object, sets rows and cols, graph map
@param n [Integer] number of rows @param m [Integer] number of columns @param graph_map [Array] prepared vector of the graph map
# File lib/mazemap/graph.rb, line 30 def initialize(n, m, graph_map) @rows, @cols = n, m @graph = NMatrix.new([n, m], graph_map) @queue = Queue.new end
Public Instance Methods
Starts a search for the shortest path
@param start [Array] start vertex coords @param finish [Array] finish vertex coords
# File lib/mazemap/graph.rb, line 40 def shortest_path(start, finish) queue << [start, 0] loop do break if queue.empty? vertex, d = queue.pop graph[*vertex] = d break if vertex == finish enqueue_neighbours(*vertex, d + 1) end queue.clear !blank?(finish) ? build_path(start, finish) : [] end
Private Instance Methods
Checks if vertex is blank
@param vertex [Array] vertex coords
# File lib/mazemap/graph.rb, line 58 def blank?(vertex) graph[*vertex] == BLANK end
Builds the shortest path from the processed graph
@param start [Array] start vertex coords @param finish [Array] finish vertex coords
# File lib/mazemap/graph.rb, line 66 def build_path(start, finish) path = [finish] loop do vertex = path.last d = graph[*vertex] neighbours = get_neighbours(*vertex) next_vertex = neighbours.select{|n_vert| graph[*n_vert] == d - 1}.first path << next_vertex if next_vertex break if vertex == start end path end
Adds the neighbours of the given vertex to the queue and marks them
@param n [Integer] row number of vertex @param m [Integer] column number of vertex @param d [Integer] distance mark of vertex
# File lib/mazemap/graph.rb, line 94 def enqueue_neighbours(n, m, d) get_neighbours(n, m).each do |vertex| if blank?(vertex) graph[*vertex] = VISITED queue << [vertex, d] end end end
Collects the neighbours of the given vertex
@param n [Integer] row number of vertex @param m [Integer] column number of vertex
# File lib/mazemap/graph.rb, line 83 def get_neighbours(n, m) [[n - 1, m],[n + 1, m],[n, m - 1],[n, m + 1]].select do |coords| coords.first.between?(0, rows - 1) && coords.last.between?(0, cols - 1) end end