Class: RGL::BFSIterator

Inherits:

Object

Object
RGL::BFSIterator

show all

Includes:

GraphIterator, GraphVisitor

Defined in:

lib/laser/third_party/rgl/traversal.rb

Overview

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.

Direct Known Subclasses

DFSIterator

Instance Attribute Summary (collapse)

- (Object) start_vertex

Returns the value of attribute start_vertex.

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary (collapse)

- (Boolean) at_beginning?

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

Returns true if @waiting is empty.
- (Object) basic_forward

:nodoc:.
- (BFSIterator) initialize(graph, start = graph.detect{ |x| true }) constructor

Create a new BFSIterator on graph, starting at vertex start.
- (Object) set_to_begin

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

Methods included from GraphVisitor

#attach_distance_map, def_event_handler, #finished_vertex?, #follow_edge?, #reset

Constructor Details

- (`BFSIterator`) initialize(graph, start = graph.detect{ |x| true })

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

# File 'lib/laser/third_party/rgl/traversal.rb', line 168

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

Instance Attribute Details

- (`Object`) start_vertex

Returns the value of attribute start_vertex



164
165
166

# File 'lib/laser/third_party/rgl/traversal.rb', line 164

def start_vertex
  @start_vertex
end

Instance Method Details

- (`Boolean`) at_beginning?

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

Returns:

(Boolean)



176
177
178

# File 'lib/laser/third_party/rgl/traversal.rb', line 176

def at_beginning?				# :nodoc:
  @color_map.size == 1
end

- (`Boolean`) at_end?

Returns true if @waiting is empty.

Returns:

(Boolean)



182
183
184

# File 'lib/laser/third_party/rgl/traversal.rb', line 182

def at_end?
  @waiting.empty?
end

- (`Object`) basic_forward

:nodoc:

# File 'lib/laser/third_party/rgl/traversal.rb', line 194

def basic_forward				# :nodoc:
  u = next_vertex
  handle_examine_vertex(u)
  graph.each_adjacent(u) { |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
  }
  color_map[u] = :BLACK
  handle_finish_vertex(u)                       # finish vertex
  u
end

- (`Object`) set_to_begin

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

# File 'lib/laser/third_party/rgl/traversal.rb', line 188

def set_to_begin
  color_map[@start_vertex] = :GRAY
  @waiting = [@start_vertex]		# a queue
  handle_tree_edge(nil, @start_vertex)	# discovers start vertex 
end