Class: Authorize::Graph::DirectedAcyclicGraphTraverser

Inherits:
Traverser
  • Object
show all
Defined in:
lib/authorize/graph/directed_acyclic_graph_traverser.rb

Direct Known Subclasses

DirectedAcyclicGraphReverseTraverser

Instance Method Summary collapse

Methods inherited from Traverser

#cost_collector, #debugger, #pruner, traverse, #visit

Instance Method Details

#cycle_detector(&block) ⇒ Object

Detect cycles in the graph by recording the path taken (effectively an array of visited vertices indexed by depth). When a cycle is detected (by finding the current vertex earlier in the path), raise an exception.



18
19
20
21
22
23
24
25
26
27
 
# File 'lib/authorize/graph/directed_acyclic_graph_traverser.rb', line 18

def cycle_detector(&block)
  return self.class.new(self, :cycle_detector) unless block_given?
  seen = ::Array.new
  self.each do |vertex, edge, depth|
    found = seen.index(vertex)
    raise "Cycle detected at #{vertex} along #{edge} at depth #{found} and #{depth}" if found && (found < depth)
    seen[depth] = vertex
    yield vertex, edge, depth
  end
end

#traverse(check = false, &block) ⇒ Object 



6
7
8
9
10
11
12
13
14
 
# File 'lib/authorize/graph/directed_acyclic_graph_traverser.rb', line 6

def traverse(check = false, &block)
  super(&block) unless check
  t = self.class.new(self, :traverse)
  if check
    t.cycle_detector.pruner.cost_collector
  else
    t.pruner.cost_collector
  end
end