Class: RGL::BFSIterator

Inherits:
Object
  • Object
show all
Includes:
GraphIterator, GraphVisitor
Defined in:
lib/rgl/traversal.rb

Overview

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 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 Also:

Instance Attribute Summary collapse

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods included from GraphVisitor

#attach_distance_map, #finished_vertex?, #follow_edge?, included, #reset

Methods included from GraphVisitor::ClassMethods

#def_event_handlers

Methods included from GraphIterator

#length

Constructor Details

#initialize(graph, start = graph.detect { |x| true }) ⇒ BFSIterator

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



44
45
46
47
48
 
# File 'lib/rgl/traversal.rb', line 44

def initialize(graph, start = graph.detect { |x| true })
  super(graph)
  @start_vertex = start
  set_to_begin
end

Instance Attribute Details

#start_vertex ⇒ Object

Returns the vertex where the search starts.

Returns:

  • the vertex where the search starts



40
41
42
 
# File 'lib/rgl/traversal.rb', line 40

def start_vertex
  @start_vertex
end

Instance Method Details

#at_beginning? ⇒ Boolean

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

Returns:

  • (Boolean) 


52
53
54
 
# File 'lib/rgl/traversal.rb', line 52

def at_beginning?
  @color_map.size == 1
end

#at_end? ⇒ Boolean

Returns true if @waiting is empty.

Returns:

  • (Boolean) 


58
59
60
 
# File 'lib/rgl/traversal.rb', line 58

def at_end?
  @waiting.empty?
end

#basic_forward ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/rgl/traversal.rb', line 74

def basic_forward
  u = next_vertex
  handle_examine_vertex(u)

  graph.each_adjacent(u) do |v|
    handle_examine_edge(u, v)
    if follow_edge?(u, v) # (u,v) is a tree edge
      handle_tree_edge(u, v) # also discovers v
      color_map[v] = :GRAY   # color of v was :WHITE
      @waiting.push(v)
    else # (u,v) is a non tree edge
      if color_map[v] == :GRAY
        handle_back_edge(u, v) # (u,v) has gray target
      else
        handle_forward_edge(u, v) # (u,v) has black target
      end
    end
  end

  color_map[u] = :BLACK
  handle_finish_vertex(u) # finish vertex
  u
end

#set_to_begin ⇒ Object

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



64
65
66
67
68
69
70
71
 
# File 'lib/rgl/traversal.rb', line 64

def set_to_begin
  # Reset color_map
  @color_map = Hash.new(:WHITE)
  color_map[@start_vertex] = :GRAY
  @waiting = [@start_vertex]           # a queue
  handle_tree_edge(nil, @start_vertex) # discovers start vertex
  self
end