Class: Rbgraph::Traverser::BfsTraverser

Inherits:
Object
  • Object
show all
Defined in:
lib/rbgraph/traverser/bfs_traverser.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ BfsTraverser

Returns a new instance of BfsTraverser.



12
13
14
15
16
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 12

def initialize(graph)
  self.graph = graph
  self.connected_subgraphs = []
  self.unvisited_nodes = Set.new [*graph.nodes.values]
end

Instance Attribute Details

#connected_subgraphs ⇒ Object

Returns the value of attribute connected_subgraphs.



7
8
9
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 7

def connected_subgraphs
  @connected_subgraphs
end

#graph ⇒ Object

Returns the value of attribute graph.



6
7
8
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 6

def graph
  @graph
end

#queue ⇒ Object

Returns the value of attribute queue.



10
11
12
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 10

def queue
  @queue
end

#unvisited_nodes ⇒ Object

Returns the value of attribute unvisited_nodes.



9
10
11
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 9

def unvisited_nodes
  @unvisited_nodes
end

#visited_nodes ⇒ Object

Returns the value of attribute visited_nodes.



8
9
10
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 8

def visited_nodes
  @visited_nodes
end

Instance Method Details

#bfs_from_root(root, options = {}) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 30

def bfs_from_root(root, options = {})
  subgraph = graph.class.new
  visited_nodes.add(root)
  queue.enq(root)
  while !queue.empty? do
    t = queue.deq
    unvisited_nodes.delete(t)
    yield(t) if block_given? # do sth on current node
    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)
      end
    end
  end
  subgraph
end

#connected_components(options = {}) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/rbgraph/traverser/bfs_traverser.rb', line 18

def connected_components(options = {})
  self.visited_nodes = Set.new
  self.queue = Queue.new

  while !unvisited_nodes.empty? do
    root = unvisited_nodes.to_a.first
    unvisited_nodes.delete(unvisited_nodes.to_a.first)
    self.connected_subgraphs << bfs_from_root(root, options)
  end
  connected_subgraphs
end