Module: BreadthFirstSearch

Included in:
Graph
Defined in:
lib/honey_mushroom/breadth_first_search.rb

Instance Method Summary collapse

Instance Method Details

#breadth_first_search_include?(node_id, target_node) ⇒ Boolean

Returns:

  • (Boolean) 


3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
# File 'lib/honey_mushroom/breadth_first_search.rb', line 3

def breadth_first_search_include?(node_id, target_node)
  queue = []
  visited_nodes = Hash.new(0)
  queue << node_id
  until queue.empty?
    id = queue.shift
    visited_nodes[id] += 1
    if id == target_node && visited_nodes[id] < 2
      return true
    else
      queue.concat(@nodes[id].edges) unless visited_nodes[id] >= 2
    end
  end
  false
end