Class: Authorize::Graph::Traverser

Inherits:
Enumerable::Enumerator
  • Object
show all
Defined in:
lib/authorize/graph/traverser.rb

Overview

Traverse the graph by enumerating the encountered vertices.

Direct Known Subclasses

DirectedAcyclicGraphTraverser

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.traverse(start, *args, &block) ⇒ Object

Traverse the graph starting at the given vertex. A “bootstrap” enumerator is created from the starting vertex. The bootstrap enumerator is then passed through a recursive expander and finally, several filters. In ruby 1.9, bootstrapping could be simplified with an anonymous enumerator (Enumerator.new {})



10
11
12
 
# File 'lib/authorize/graph/traverser.rb', line 10

def self.traverse(start, *args, &block)
  self.new(start, :tap).traverse(*args).visit(&block)
end

Instance Method Details

#cost_collector(cost = 0, f = lambda{|e| 1}, &block) ⇒ Object

Return the accumulated cost of traversing the graph. The default accumulator is a simple transit counter.



40
41
42
43
44
45
46
 
# File 'lib/authorize/graph/traverser.rb', line 40

def cost_collector(cost = 0, f = lambda{|e| 1}, &block)
  return self.class.new(self, :cost_collector) unless block_given?
  inject(cost) do |total, (vertex, edge, depth)|
    yield vertex, edge, depth
    total + f.call(edge)
  end
end

#debugger(&block) ⇒ Object

Output the values yielded by the yielder as well as the return value of the supplied block.



28
29
30
31
32
33
34
35
36
37
 
# File 'lib/authorize/graph/traverser.rb', line 28

def debugger(&block)
  return self.class.new(self, :debugger) unless block_given?
  count = 0 # A transit counter that
  self.each do |*args|
    count += 1
    block.call(*args).tap do |result|
      print "#{count}\t#{result}\t" + args.join("\t") + "\n"
    end
  end
end

#pruner(&block) ⇒ Object

Prune the graph by accumulating a set of visited nodes. When a vertex has already been visited, interrupt the visit and signal the yielder.



16
17
18
19
20
21
22
23
24
25
 
# File 'lib/authorize/graph/traverser.rb', line 16

def pruner(&block)
  return self.class.new(self, :pruner) unless block_given?
  seen = ::Set.new
  self.each do |vertex, edge, depth|
    next false if seen.include?(vertex)
    seen << vertex
    yield vertex, edge, depth
    true # Don't let client block return value influence traversal
  end
end

#traverse(&block) ⇒ Object

Visit the yielded start vertex and traverse to its adjacencies. This operation effectively “expands” the enumerator.



59
60
61
62
63
64
65
66
 
# File 'lib/authorize/graph/traverser.rb', line 59

def traverse(&block)
  return self.class.new(self, :traverse).pruner.cost_collector unless block_given?
  each do |vertex, edge|
    depth = 0
    yield vertex, edge, depth
    _traverse(vertex, depth, &block)
  end
end

#visit(&block) ⇒ Object

Invoke callback on vertex. Strip the edge to be more conventional. This is typically the last filter in the traverse chain.



50
51
52
53
54
55
 
# File 'lib/authorize/graph/traverser.rb', line 50

def visit(&block)
  return self.class.new(self, :visit) unless block_given?
  self.each do |vertex, edge, depth|
    vertex.visit(edge, &block)
  end
end