Class: RGL::BFSIterator

Inherits:
Object
  • Object
show all
Includes:
GraphIterator, GraphVisitor
Defined in:
lib/laser/third_party/rgl/traversal.rb

Overview

A BFSIterator can be used to traverse a graph from a given start vertex in breath first search order. Since the Iterator also mixins the GraphVisitor, it provides all event points defined there.

The vertices which are not yet visited are held in the queue @waiting. During the traversal, vertices are colored using the colors :GRAY (when waiting) and :BLACK when finished. All other vertices are :WHITE.

For more doc see the BGL BFS Visitor Concept .

See the implementation of bfs_search_tree_from for an example usage.

Direct Known Subclasses

DFSIterator

Instance Attribute Summary collapse

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods included from GraphVisitor

#attach_distance_map, def_event_handler, #finished_vertex?, #follow_edge?, #reset

Constructor Details

#initialize(graph, start = graph.detect{ |x| true }) ⇒ BFSIterator

Create a new BFSIterator on graph, starting at vertex start.



168
169
170
171
172
# File 'lib/laser/third_party/rgl/traversal.rb', line 168

def initialize (graph, start=graph.detect{ |x| true })
  super(graph)
  @start_vertex = start
  set_to_begin
end

Instance Attribute Details

#start_vertexObject

Returns the value of attribute start_vertex



164
165
166
# File 'lib/laser/third_party/rgl/traversal.rb', line 164

def start_vertex
  @start_vertex
end

Instance Method Details

#at_beginning?Boolean

Returns true if the @color_map has only one entry (for the start vertex).

Returns:

  • (Boolean)


176
177
178
# File 'lib/laser/third_party/rgl/traversal.rb', line 176

def at_beginning?				# :nodoc:
  @color_map.size == 1
end

#at_end?Boolean

Returns true if @waiting is empty.

Returns:

  • (Boolean)


182
183
184
# File 'lib/laser/third_party/rgl/traversal.rb', line 182

def at_end?
  @waiting.empty?
end

#basic_forwardObject

:nodoc:



194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
# File 'lib/laser/third_party/rgl/traversal.rb', line 194

def basic_forward				# :nodoc:
  u = next_vertex
  handle_examine_vertex(u)
  graph.each_adjacent(u) { |v|
    handle_examine_edge(u, v)
    if follow_edge?(u, v)			# (u,v) is a tree edge
      handle_tree_edge(u, v)		# also discovers v
      color_map[v] = :GRAY			# color of v was :WHITE
      @waiting.push(v)
    else					# (u,v) is a non tree edge
      if color_map[v] == :GRAY
        handle_back_edge(u, v)		# (u,v) has gray target
      else
        handle_forward_edge(u, v)		# (u,v) has black target
      end
    end
  }
  color_map[u] = :BLACK
  handle_finish_vertex(u)                       # finish vertex
  u
end

#set_to_beginObject

Reset the iterator to the initial state (i.e. at_beginning? == true).



188
189
190
191
192
# File 'lib/laser/third_party/rgl/traversal.rb', line 188

def set_to_begin
  color_map[@start_vertex] = :GRAY
  @waiting = [@start_vertex]		# a queue
  handle_tree_edge(nil, @start_vertex)	# discovers start vertex 
end