Module: Bosh::Director::CycleHelper

Defined in:
lib/bosh/director/cycle_helper.rb

Overview

Copyright © 2009-2012 VMware, Inc.

Class Method Summary collapse

Class Method Details

.check_for_cycle(vertices, options = {}, &block) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
 
# File 'lib/bosh/director/cycle_helper.rb', line 5

def self.check_for_cycle(vertices, options = {}, &block)
  result = {}
  result[:connected_vertices] = {} if options[:connected_vertices]
  vertices.each do |vertex|
    path = {}
    connected_vertices = options[:connected_vertices] ? Set.new : nil
    check_for_cycle_helper(path, vertices, vertex, connected_vertices, &block)
    result[:connected_vertices][vertex] = connected_vertices.to_a if connected_vertices
  end
  result
end

.check_for_cycle_helper(path, valid_vertices, vertex, connected_vertices, &block) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/bosh/director/cycle_helper.rb', line 17

def self.check_for_cycle_helper(path, valid_vertices, vertex, connected_vertices, &block)
  path[vertex] = path.size + 1
  connected_vertices << vertex if connected_vertices && path.size > 1
  edges = block.call(vertex)
  if edges
    edges.each do |edge|
      raise "Invalid edge: #{edge}" unless valid_vertices.include?(edge)
      if path.include?(edge)
        vertex_path = []
        path = path.invert
        path.size.times { |index| vertex_path << path[index + 1] }
        raise "Cycle: #{vertex_path.join("=>")}=>#{edge}"
      end
      check_for_cycle_helper(path, valid_vertices, edge, connected_vertices, &block)
    end
  end
  path.delete(vertex)
end