Class: Graph

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/mvGraph.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



14
15
16
 
# File 'lib/mvGraph.rb', line 14

def initialize
  @adj_matrix = Hash.new 
end

Instance Method Details

#add_edge(v1, v2) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
 
# File 'lib/mvGraph.rb', line 26

def add_edge(v1, v2)
  if @adj_matrix[v1].nil?
    @adj_matrix[v1] = Hash.new
  end
  if @adj_matrix[v2].nil?
    @adj_matrix[v2] = Hash.new
  end
    @adj_matrix[v2][v1] = 1
    @adj_matrix[v1][v2] = 1
end

#add_vertex(v) ⇒ Object 



18
19
20
 
# File 'lib/mvGraph.rb', line 18

def add_vertex(v)
  @adj_matrix[v] = Hash.new
end

#each ⇒ Object 



4
5
6
7
8
 
# File 'lib/mvGraph.rb', line 4

def each
  @adj_matrix.keys.each do |vertex|
    yield vertex
  end
end

#get_vertex_color(v) ⇒ Object 



152
153
154
 
# File 'lib/mvGraph.rb', line 152

def get_vertex_color(v)
  get_graph_vertex(v).color
end

#get_vertex_distance(v) ⇒ Object 



160
161
162
 
# File 'lib/mvGraph.rb', line 160

def get_vertex_distance(v)
  get_graph_vertex(v).distance
end

#get_vertex_predecessor(v) ⇒ Object 



168
169
170
 
# File 'lib/mvGraph.rb', line 168

def get_vertex_predecessor(v)
  get_graph_vertex(v).predecessor
end

#has_edge?(v1, v2) ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
44
45
 
# File 'lib/mvGraph.rb', line 41

def has_edge?(v1, v2)
  unless @adj_matrix[v1].nil? or @adj_matrix[v1][v2].nil?
    @adj_matrix[v1][v2] == 1
  end
end

#neighbors_of(vertex) ⇒ Object 



10
11
12
 
# File 'lib/mvGraph.rb', line 10

def neighbors_of(vertex)
  @adj_matrix[vertex].select { |v| has_edge?(vertex, v) }.keys
end

#search(start_vertex, queue_type, neighbor_function = nil, goal_state = nil, search_depth = nil) ⇒ Object

queue_type is one of fifo or lifo

Look into passing a hash of arguments



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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/mvGraph.rb', line 51

def search(start_vertex, queue_type, neighbor_function=nil, goal_state=nil, search_depth=nil)
  set_vertex_color(start_vertex, "gray")
  set_vertex_distance(start_vertex, 0)
  queue = Queue.new(queue_type)
  queue.enqueue(get_graph_vertex(start_vertex))
  goal_not_reached = true
  count = 0
  return_goal_state = nil
  while queue.length != 0 and goal_not_reached
    current_vertex = queue.dequeue
    count += 1
    # Full BFS or DFS with no goal state
    if neighbor_function.nil? and search_depth.nil? and goal_state.nil?
      neighbors_of(current_vertex).each do |neighbor|
 if neighbor.color == "white"
   set_vertex_color(get_graph_vertex(neighbor), "gray")
   set_vertex_distance(get_graph_vertex(neighbor), get_vertex_distance(get_graph_vertex(current_vertex)) + 1)
   set_vertex_predecessor(get_graph_vertex(neighbor), get_graph_vertex(current_vertex))
   queue.enqueue(get_graph_vertex(neighbor))
 end
	end
	set_vertex_color(get_graph_vertex(current_vertex), "black")
    # Search for goal_state with no distance limit
    elsif !neighbor_function.nil? and !goal_state.nil? and search_depth.nil?
	neighbors = get_graph_vertex(current_vertex).send(neighbor_function, goal_state)
	neighbors.each do |neighbor|
 unless self.include? neighbor
   self.add_vertex(neighbor)
   self.add_edge(current_vertex, neighbor)
   if neighbor == goal_state
            set_vertex_color(get_graph_vertex(neighbor), "gray")
     set_vertex_distance(get_graph_vertex(neighbor), get_vertex_distance(get_graph_vertex(current_vertex)) + 1)
     set_vertex_predecessor(get_graph_vertex(neighbor), get_graph_vertex(current_vertex))
puts "	   a;dslfkj   #{return_goal_state} "
     return_goal_state = neighbor
     goal_not_reached = false
     break
   end
   if get_vertex_color(get_graph_vertex(neighbor)) == "white"
     set_vertex_color(get_graph_vertex(neighbor), "gray")
     set_vertex_distance(get_graph_vertex(neighbor), get_vertex_distance(get_graph_vertex(current_vertex)) + 1)
     set_vertex_predecessor(get_graph_vertex(neighbor), get_graph_vertex(current_vertex))
     queue.enqueue(get_graph_vertex(neighbor))
   end
   set_vertex_color(get_graph_vertex(current_vertex), "black")
 end
	end
    # Random walk to a given distance and no goal state
    elsif !neighbor_function.nil? and goal_state.nil? and !search_depth.nil?
	neighbors = get_graph_vertex(current_vertex).send(neighbor_function)
	neighbors.each do |neighbor|
 unless self.include? neighbor
   self.add_vertex(neighbor)
   self.add_edge(current_vertex, neighbor)
   if count == search_depth
     return_goal_state = neighbor
     goal_not_reached = false
     break
   end
   if get_vertex_color(get_graph_vertex(neighbor)) == "white"
     set_vertex_color(get_graph_vertex(neighbor), "gray")
     set_vertex_distance(get_graph_vertex(neighbor), get_vertex_distance(get_graph_vertex(current_vertex)) + 1)
     set_vertex_predecessor(get_graph_vertex(neighbor), get_graph_vertex(current_vertex))
     queue.enqueue(get_graph_vertex(neighbor))
   end
   set_vertex_color(get_graph_vertex(current_vertex), "black")
 end
	end
    else
	# Other possible prototypes
    end	
  end
puts "return_goal_state: #{return_goal_state}"
  return return_goal_state, count
end

#set_vertex_color(v, color) ⇒ Object 



148
149
150
 
# File 'lib/mvGraph.rb', line 148

def set_vertex_color(v, color)
  get_graph_vertex(v).color = color
end

#set_vertex_distance(v, distance) ⇒ Object 



156
157
158
 
# File 'lib/mvGraph.rb', line 156

def set_vertex_distance(v, distance)
  get_graph_vertex(v).distance = distance
end

#set_vertex_predecessor(v, predecessor) ⇒ Object 



164
165
166
 
# File 'lib/mvGraph.rb', line 164

def set_vertex_predecessor(v, predecessor)
  get_graph_vertex(v).predecessor = get_graph_vertex(predecessor) unless predecessor.nil?
end

#shortest_path(start_vertex, end_vertex) ⇒ Object

Precondition: BFS has been run on the graph



135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/mvGraph.rb', line 135

def shortest_path(start_vertex, end_vertex)
  @ret_array ||= []
  predecessor = get_vertex_predecessor(get_graph_vertex(end_vertex))
  if start_vertex == end_vertex
    @ret_array << get_graph_vertex(start_vertex)
  elsif predecessor.nil?
    "No path."
  else
    shortest_path(get_graph_vertex(start_vertex), predecessor)
    @ret_array << get_graph_vertex(end_vertex)
  end
end

#update_vertex(v) ⇒ Object 



37
38
39
 
# File 'lib/mvGraph.rb', line 37

def update_vertex(v)
  @adj_matrix[v] = @adj_matrix[vertex(v)]
end

#vertex(v) ⇒ Object 



22
23
24
 
# File 'lib/mvGraph.rb', line 22

def vertex(v)
  @adj_matrix.find { |vertex| vertex[0] == v }[0]
end

#walk_n_steps(start_state, neighbor_function, depth) ⇒ Object

Performs depth-first search to the given depth, starting at the vertex start_state.



128
129
130
 
# File 'lib/mvGraph.rb', line 128

def walk_n_steps(start_state, neighbor_function, depth)
  search(start_state, "lifo", neighbor_function, nil, depth)
end