class RGL::BFSIterator
File traversal.rb
defines the basic graph traversal algorithm for DFS and BFS search. They are implemented as a {GraphIterator}, which is a Stream
of vertices of a given graph. The streams are not reversable.
Beside being an iterator in the sense of the Stream mixin, {BFSIterator} and {DFSIterator} follow the {www.boost.org/libs/graph/doc/visitor_concepts.html BGL Visitor Concepts} in a slightly modified fashion (especially for the {DFSIterator}).
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 see the BGL BFS Visitor Concept.
See the implementation of {Graph#bfs_search_tree_from} for an example usage.
@see Graph#bfs_iterator
@see Graph#bfs_search_tree_from
Attributes
@return the vertex where the search starts
Public Class Methods
Source
# File lib/rgl/traversal.rb 44 def initialize(graph, start = graph.detect { |x| true }) 45 super(graph) 46 @start_vertex = start 47 set_to_begin 48 end
Create a new {BFSIterator} on graph, starting at vertex start.
RGL::GraphVisitor::new
Public Instance Methods
Source
# File lib/rgl/traversal.rb 52 def at_beginning? 53 @color_map.size == 1 54 end
Returns true if +@color_map+ has only one entry (for the start vertex).
Source
# File lib/rgl/traversal.rb 58 def at_end? 59 @waiting.empty? 60 end
Returns true if @waiting is empty.
Source
# File lib/rgl/traversal.rb 74 def basic_forward 75 u = next_vertex 76 handle_examine_vertex(u) 77 78 graph.each_adjacent(u) do |v| 79 handle_examine_edge(u, v) 80 if follow_edge?(u, v) # (u,v) is a tree edge 81 handle_tree_edge(u, v) # also discovers v 82 color_map[v] = :GRAY # color of v was :WHITE 83 @waiting.push(v) 84 else # (u,v) is a non tree edge 85 if color_map[v] == :GRAY 86 handle_back_edge(u, v) # (u,v) has gray target 87 else 88 handle_forward_edge(u, v) # (u,v) has black target 89 end 90 end 91 end 92 93 color_map[u] = :BLACK 94 handle_finish_vertex(u) # finish vertex 95 u 96 end
@private
Source
# File lib/rgl/traversal.rb 64 def set_to_begin 65 # Reset color_map 66 @color_map = Hash.new(:WHITE) 67 color_map[@start_vertex] = :GRAY 68 @waiting = [@start_vertex] # a queue 69 handle_tree_edge(nil, @start_vertex) # discovers start vertex 70 self 71 end
Reset the iterator to the initial state (i.e. at_beginning? == true).
Protected Instance Methods
Source
# File lib/rgl/traversal.rb 100 def next_vertex 101 # waiting is a queue 102 @waiting.shift 103 end