Method: Bio::Pathway#breadth_first_search

Defined in:
lib/bio/pathway.rb

#breadth_first_search(root) ⇒ Object Also known as: bfs

Breadth first search solves steps and path to the each node and forms a tree contains all reachable vertices from the root node. This method returns the result in 2 hashes - 1st one shows the steps from root node and 2nd hash shows the structure of the tree.

The weight of the edges are not considered in this method.



420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
 
# File 'lib/bio/pathway.rb', line 420

def breadth_first_search(root)
  visited = {}
  distance = {}
  predecessor = {}

  visited[root] = true
  distance[root] = 0
  predecessor[root] = nil

  queue = [ root ]

  while from = queue.shift
    next unless @graph[from]
    @graph[from].each_key do |to|
      unless visited[to]
        visited[to] = true
        distance[to] = distance[from] + 1
        predecessor[to] = from
        queue.push(to)
      end
    end
  end
  return distance, predecessor
end