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 40 def initialize(graph, start = graph.detect { |x| true }) 41 super(graph) 42 @start_vertex = start 43 set_to_begin 44 end
Public Instance Methods
at_end?()
click to toggle source
Returns true if @waiting is empty.
# File lib/rgl/traversal.rb 54 def at_end? 55 @waiting.empty? 56 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 60 def set_to_begin 61 # Reset color_map 62 @color_map = Hash.new(:WHITE) 63 color_map[@start_vertex] = :GRAY 64 @waiting = [@start_vertex] # a queue 65 handle_tree_edge(nil, @start_vertex) # discovers start vertex 66 self 67 end