Class: BoggleSolver::AdjacencyMatrix

Inherits:
Object
  • Object
show all
Defined in:
lib/boggle_solver/adjacency_matrix.rb

Direct Known Subclasses

Board

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n = 2) ⇒ AdjacencyMatrix

Returns a new instance of AdjacencyMatrix.



6
7
8
9
10
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 6

def initialize( n = 2 )
  @m = Array.new(n, 0)
  @m.map!{Array.new(n, 0)}
  @n = n
end

Instance Attribute Details

#finished ⇒ Object (readonly)

Returns the value of attribute finished.



4
5
6
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 4

def finished
  @finished
end

#visited ⇒ Object (readonly)

Returns the value of attribute visited.



4
5
6
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 4

def visited
  @visited
end

Instance Method Details

#add_directed_edge(i, j, w = 1) ⇒ Object 



21
22
23
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 21

def add_directed_edge(i, j, w=1)
  @m[i][j] = w unless i == j
end

#add_edge(i, j, w = 1) ⇒ Object 



25
26
27
28
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 25

def add_edge(i, j, w=1)
  add_directed_edge(i, j, w)
  add_directed_edge(j, i, w)
end

#adjacent(u) ⇒ Object 



30
31
32
33
34
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 30

def adjacent(u)
  a = Array.new
  @m[u].each_with_index {|v,i| a.push i unless v == 0 }
  a
end

#depth_first_search ⇒ Object 



36
37
38
39
40
41
42
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 36

def depth_first_search
  @visited  = Array.new(@n, nil)
  @finished = Array.new(@n, nil)
  @visited.each_with_index do |visit_status, u|
    depth_first_search_visit(u) if visit_status.nil?
  end
end

#depth_first_search_visit(u) ⇒ Object 



44
45
46
47
48
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 44

def depth_first_search_visit(u, *)
  @visited[u] = 1
  adjacent(u).each { |v| depth_first_search_visit(v) if @visited[v].nil?}
  @finished[u] = 1
end

#to_s ⇒ Object 



12
13
14
15
16
17
18
19
 
# File 'lib/boggle_solver/adjacency_matrix.rb', line 12

def to_s
  s = ""
  @m.each do |row|
    row.each {|e| s += e.to_s + " "}
    s += "\n"
  end
  s.chop
end