class 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.
Calls superclass method
RGL::GraphVisitor.new
# File lib/rgl/traversal.rb, line 40 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 54 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 60 def set_to_begin color_map[@start_vertex] = :GRAY @waiting = [@start_vertex] # a queue handle_tree_edge(nil, @start_vertex) # discovers start vertex end