class Rbgraph::Traverser::BfsTraverser

Attributes

graph[RW]

Public Class Methods

new(graph) click to toggle source
# File lib/rbgraph/traverser/bfs_traverser.rb, line 8
def initialize(graph)
  self.graph = graph
end

Public Instance Methods

bfs_between_a_and_b(a, b, options = {}) click to toggle source
# File lib/rbgraph/traverser/bfs_traverser.rb, line 60
def bfs_between_a_and_b(a, b, options = {})
  if graph.nodes[a.id].nil? || graph.nodes[b.id].nil?
    return nil
  end

  if a.id == b.id # a is the same as b
    return [a]
  end

  if !a.neighbors[b.id].nil? # a and b are just one step away
    return [a, b]
  end

  bfs_from_root(a, options) do |current_node|
    :break if current_node.id == b.id # destination node found! return ':break' in the block to stop traversing!
  end

  if b.data[:__bfs_prev_node].nil?
    return [] # no path found
  end

  path = [b]

  while path[-1].id != a.id do
    path << path[-1].data[:__bfs_prev_node]
  end

  path.reverse
end
bfs_from_root(root, options = {}) { |t| ... } click to toggle source
# File lib/rbgraph/traverser/bfs_traverser.rb, line 26
def bfs_from_root(root, options = {})
  if !options[:sticky]
    @unvisited_nodes = Set.new [*graph.nodes.values]
    @visited_nodes = Set.new
    @queue = Queue.new
  end

  clear_backtracking_info

  subgraph = graph.class.new
  @visited_nodes.add(root)
  @queue.enq(root)
  while !@queue.empty? do
    t = @queue.deq
    @unvisited_nodes.delete(t)
    yield_value = yield(t) if block_given? # do sth on current node
    break if yield_value == :break
    subgraph.nodes[t.id] ||= t
    t.edges.each do |eid, edge|
      next if graph.directed? && !edge.out_for?(t) unless options[:respect_direction] == false
      neighbor = edge.other_node(t)
      subgraph.edges[eid] ||= edge
      subgraph.nodes[neighbor.id] ||= neighbor
      if !@visited_nodes.include?(neighbor)
        @visited_nodes.add(neighbor)
        @queue.enq(neighbor)
        neighbor.data[:__bfs_prev_node] ||= t
        @__bfs_prev_node_dirty = true
      end
    end
  end
  subgraph
end
connected_components(options = {}) click to toggle source
# File lib/rbgraph/traverser/bfs_traverser.rb, line 12
def connected_components(options = {})
  @connected_subgraphs = []
  @unvisited_nodes = Set.new [*graph.nodes.values]
  @visited_nodes = Set.new
  @queue = Queue.new

  while !@unvisited_nodes.empty? do
    root = @unvisited_nodes.to_a.first
    @unvisited_nodes.delete(@unvisited_nodes.to_a.first)
    @connected_subgraphs << bfs_from_root(root, options.merge(sticky: true))
  end
  @connected_subgraphs
end

Private Instance Methods

clear_backtracking_info() click to toggle source
# File lib/rbgraph/traverser/bfs_traverser.rb, line 92
def clear_backtracking_info
  if @__bfs_prev_node_dirty
    graph.nodes.each do |node_id, node|
      node.data[:__bfs_prev_node] = nil
    end
  end
end