Parent

Files

RGL::BFSIterator

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.

Attributes

start_vertex[RW]

Public Class Methods

new(graph, start=graph.detect{ |x| true }) click to toggle source

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

# File lib/rgl/traversal.rb, line 169
def initialize (graph, start=graph.detect{ |x| true })
  super(graph)
  @start_vertex = start
  set_to_begin
end

Public Instance Methods

at_end?() click to toggle source

Returns true if @waiting is empty.

# File lib/rgl/traversal.rb, line 183
def at_end?
  @waiting.empty?
end
set_to_begin() click to toggle source

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

# 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

[Validate]

Generated with the Darkfish Rdoc Generator 2.