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

cols[R]
graph[R]
queue[R]
rows[R]

Public Class Methods

new(n, m, graph_map) click to toggle source

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

shortest_path(start, finish) click to toggle source

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

blank?(vertex) click to toggle source

Checks if vertex is blank

@param vertex [Array] vertex coords

# File lib/mazemap/graph.rb, line 58
def blank?(vertex)
  graph[*vertex] == BLANK
end
build_path(start, finish) click to toggle source

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
enqueue_neighbours(n, m, d) click to toggle source

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
get_neighbours(n, m) click to toggle source

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