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

start_vertex[RW]

@return the vertex where the search starts

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
44 def initialize(graph, start = graph.detect { |x| true })
45   super(graph)
46   @start_vertex = start
47   set_to_begin
48 end

Public Instance Methods

at_beginning?() click to toggle source

Returns true if +@color_map+ has only one entry (for the start vertex).

   # File lib/rgl/traversal.rb
52 def at_beginning?
53   @color_map.size == 1
54 end
at_end?() click to toggle source

Returns true if @waiting is empty.

   # File lib/rgl/traversal.rb
58 def at_end?
59   @waiting.empty?
60 end
basic_forward() click to toggle source

@private

   # 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
set_to_begin() click to toggle source

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

   # 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

Protected Instance Methods

next_vertex() click to toggle source
    # File lib/rgl/traversal.rb
100 def next_vertex
101   # waiting is a queue
102   @waiting.shift
103 end