Method: GRATR::Graph::Search#bfs

Defined in:
lib/gratr/search.rb

#bfs(options = {}, &block) ⇒ Object

Options are mostly callbacks passed in as a hash. The following are valid, anything else is ignored :enter_vertex => Proc Called upon entry of a vertex :exit_vertex => Proc Called upon exit of a vertex :root_vertex => Proc Called when a vertex the a root of a tree :start_vertex => Proc Called for the first vertex of the search :examine_edge => Proc Called when an edge is examined :tree_edge => Proc Called when the edge is a member of the tree :back_edge => Proc Called when the edge is a back edge :forward_edge => Proc Called when the edge is a forward edge :adjacent => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms

:start => Vertex Specifies the vertex to start search from

If a &block is specified it defaults to :enter_vertex

Returns the list of vertexes as reached by enter_vertex This allows for calls like, g.bfs.each {|v| …}

Can also be called like bfs_examine_edge {|e| … } or dfs_back_edge {|e| … } for any of the callbacks

A full example usage is as follows:

ev = Proc.new {|x| puts "Enter Vertex #{x}"}
xv = Proc.new {|x| puts "Exit Vertex #{x}"}
sv = Proc.new {|x| puts "Start Vertex #{x}"}
ee = Proc.new {|x| puts "Examine Arc #{x}"}
te = Proc.new {|x| puts "Tree Arc #{x}"}
be = Proc.new {|x| puts "Back Arc #{x}"}
fe = Proc.new {|x| puts "Forward Arc #{x}"}
Digraph[1,2,2,3,3,4].dfs({ 
      :enter_vertex => ev, 
      :exit_vertex  => xv,
      :start_vertex => sv,
      :examine_edge => ee,
      :tree_edge    => te,
      :back_edge    => be,
      :forward_edge => fe })

Which outputs:

Start Vertex 1 Enter Vertex 1 Examine Arc (1=2) Tree Arc (1=2) Enter Vertex 2 Examine Arc (2=3) Tree Arc (2=3) Enter Vertex 3 Examine Arc (3=4) Tree Arc (3=4) Enter Vertex 4 Examine Arc (1=4) Back Arc (1=4) Exit Vertex 4 Exit Vertex 3 Exit Vertex 2 Exit Vertex 1



92
 
# File 'lib/gratr/search.rb', line 92

def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end