Class: RGL::BFSIterator

Inherits:
Object
  • Object
show all
Includes:
GraphIterator, GraphVisitor
Defined in:
lib/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.



169
170
171
172
173
 
# File 'lib/rgl/traversal.rb', line 169

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

Instance Attribute Details

#start_vertex ⇒ Object

Returns the value of attribute start_vertex.



165
166
167
 
# File 'lib/rgl/traversal.rb', line 165

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) 


177
178
179
 
# File 'lib/rgl/traversal.rb', line 177

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

#at_end? ⇒ Boolean

Returns true if @waiting is empty.

Returns:

  • (Boolean) 


183
184
185
 
# File 'lib/rgl/traversal.rb', line 183

def at_end?
  @waiting.empty?
end

#basic_forward ⇒ Object

:nodoc:



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

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_begin ⇒ Object

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



189
190
191
192
193
 
# File 'lib/rgl/traversal.rb', line 189

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