module Bosh::Director::CycleHelper
Copyright © 2009-2012 VMware, Inc.
Public Class Methods
check_for_cycle(vertices, options = {}, &block)
click to toggle source
# 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)
click to toggle source
# 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