Class: Mazemap::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/mazemap/graph.rb

Overview

Graph object class

Author:

  • Evgenii Shevchenko

Since:

  • 0.0.1

Constant Summary collapse

INF =

Since:

  • 0.0.1

Float::INFINITY
BLANK =

Since:

  • 0.0.1

-Float::INFINITY
VISITED =

Since:

  • 0.0.1

Float::MAX
START =

Since:

  • 0.0.1

1
FINISH =

Since:

  • 0.0.1

2

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, m, graph_map) ⇒ Graph

Initializes Graph object, sets rows and cols, graph map

Parameters:

  • n (Integer) —

    number of rows

  • m (Integer) —

    number of columns

  • graph_map (Array) —

    prepared vector of the graph map

Since:

  • 0.0.1



30
31
32
33
34
 
# 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

Instance Attribute Details

#cols ⇒ Integer (readonly)

Returns number of the cols.

Returns:

  • (Integer) —

    number of the cols

Since:

  • 0.0.1



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
74
75
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
102
103
 
# File 'lib/mazemap/graph.rb', line 13

class Graph
  attr_reader :graph
  attr_reader :queue
  attr_reader :rows
  attr_reader :cols

  INF = Float::INFINITY
  BLANK = -Float::INFINITY
  VISITED = Float::MAX
  START = 1
  FINISH = 2

  # 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
  def initialize(n, m, graph_map)
    @rows, @cols = n, m
    @graph = NMatrix.new([n, m], graph_map)
    @queue = Queue.new
  end

  # Starts a search for the shortest path
  #
  # @param start [Array] start vertex coords
  # @param finish [Array] finish vertex coords
  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

  # Checks if vertex is blank
  #
  # @param vertex [Array] vertex coords
  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
  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

  # Collects the neighbours of the given vertex
  #
  # @param n [Integer] row number of vertex
  # @param m [Integer] column number of vertex
  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

  # 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
  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

end

#graph ⇒ NMatrix (readonly)

Returns graph map matrix.

Returns:

  • (NMatrix) —

    graph map matrix

Since:

  • 0.0.1



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
74
75
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
102
103
 
# File 'lib/mazemap/graph.rb', line 13

class Graph
  attr_reader :graph
  attr_reader :queue
  attr_reader :rows
  attr_reader :cols

  INF = Float::INFINITY
  BLANK = -Float::INFINITY
  VISITED = Float::MAX
  START = 1
  FINISH = 2

  # 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
  def initialize(n, m, graph_map)
    @rows, @cols = n, m
    @graph = NMatrix.new([n, m], graph_map)
    @queue = Queue.new
  end

  # Starts a search for the shortest path
  #
  # @param start [Array] start vertex coords
  # @param finish [Array] finish vertex coords
  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

  # Checks if vertex is blank
  #
  # @param vertex [Array] vertex coords
  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
  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

  # Collects the neighbours of the given vertex
  #
  # @param n [Integer] row number of vertex
  # @param m [Integer] column number of vertex
  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

  # 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
  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

end

#queue ⇒ Queue (readonly)

Returns progress queue.

Returns:

  • (Queue) —

    progress queue

Since:

  • 0.0.1



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
74
75
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
102
103
 
# File 'lib/mazemap/graph.rb', line 13

class Graph
  attr_reader :graph
  attr_reader :queue
  attr_reader :rows
  attr_reader :cols

  INF = Float::INFINITY
  BLANK = -Float::INFINITY
  VISITED = Float::MAX
  START = 1
  FINISH = 2

  # 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
  def initialize(n, m, graph_map)
    @rows, @cols = n, m
    @graph = NMatrix.new([n, m], graph_map)
    @queue = Queue.new
  end

  # Starts a search for the shortest path
  #
  # @param start [Array] start vertex coords
  # @param finish [Array] finish vertex coords
  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

  # Checks if vertex is blank
  #
  # @param vertex [Array] vertex coords
  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
  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

  # Collects the neighbours of the given vertex
  #
  # @param n [Integer] row number of vertex
  # @param m [Integer] column number of vertex
  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

  # 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
  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

end

#rows ⇒ Integer (readonly)

Returns number of the rows.

Returns:

  • (Integer) —

    number of the rows

Since:

  • 0.0.1



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
74
75
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
102
103
 
# File 'lib/mazemap/graph.rb', line 13

class Graph
  attr_reader :graph
  attr_reader :queue
  attr_reader :rows
  attr_reader :cols

  INF = Float::INFINITY
  BLANK = -Float::INFINITY
  VISITED = Float::MAX
  START = 1
  FINISH = 2

  # 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
  def initialize(n, m, graph_map)
    @rows, @cols = n, m
    @graph = NMatrix.new([n, m], graph_map)
    @queue = Queue.new
  end

  # Starts a search for the shortest path
  #
  # @param start [Array] start vertex coords
  # @param finish [Array] finish vertex coords
  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

  # Checks if vertex is blank
  #
  # @param vertex [Array] vertex coords
  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
  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

  # Collects the neighbours of the given vertex
  #
  # @param n [Integer] row number of vertex
  # @param m [Integer] column number of vertex
  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

  # 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
  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

end

Instance Method Details

#shortest_path(start, finish) ⇒ Object

Starts a search for the shortest path

Parameters:

  • start (Array) —

    start vertex coords

  • finish (Array) —

    finish vertex coords

Since:

  • 0.0.1



40
41
42
43
44
45
46
47
48
49
50
51
 
# 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