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

Instance Method Summary collapse

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

#color_map ⇒ Hash (readonly) Originally defined in module GraphVisitor

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

#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

#attach_distance_map(map = Hash.new(0)) ⇒ Object Originally defined in module GraphVisitor

Attach a map to the visitor which records the distance of a visited vertex to the start vertex.

This is similar to BGLs distance_recorder.

After the distance_map is attached, the visitor has a new method distance_to_root, which answers the distance to the start vertex.

#finished_vertex?(v) ⇒ Boolean Originally defined in module GraphVisitor

Returns true if vertex v is colored :BLACK (i.e. finished).

Returns:

  • (Boolean)

#follow_edge?(u, v) ⇒ Boolean Originally defined in module GraphVisitor

Shall we follow the edge (u,v); i.e. v has color :WHITE

Returns:

  • (Boolean)

#length ⇒ int Originally defined in module GraphIterator

Returns:

  • (int)

#reset ⇒ Object Originally defined in module GraphVisitor

Mark each vertex unvisited (i.e. :WHITE)

#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