[Pkg-puppet-devel] [facter] 171/352: (FACT-237) Add directed graph for handling dependencies

[Stig Sandbeck Mathisen]

This is an automated email from the git hooks/post-receive script.

ssm pushed a commit to branch master
in repository facter.

commit 3431c2dda7e3e0d75d46e58f34b8b8c6335f9601
Author: Adrien Thebo <git at somethingsinistral.net>
Date:   Tue Jan 7 13:58:11 2014 -0800

    (FACT-237) Add directed graph for handling dependencies
---
 lib/facter/core/directed_graph.rb     | 45 ++++++++++++++++++++
 spec/unit/core/directed_graph_spec.rb | 79 +++++++++++++++++++++++++++++++++++
 2 files changed, 124 insertions(+)

diff --git a/lib/facter/core/directed_graph.rb b/lib/facter/core/directed_graph.rb
new file mode 100644
index 0000000..bbdd5db
--- /dev/null
+++ b/lib/facter/core/directed_graph.rb
@@ -0,0 +1,45 @@
+require 'set'
+
+module Facter
+  module Core
+    class DirectedGraph < Hash
+      include TSort
+
+      def acyclic?
+        cycles.empty?
+      end
+
+      def cycles
+        cycles = []
+        each_strongly_connected_component do |component|
+          cycles << component if component.size > 1
+        end
+        cycles
+      end
+
+      alias tsort_each_node each_key
+
+      def tsort_each_child(node)
+        fetch(node, []).each do |child|
+          yield child
+        end
+      end
+
+      def tsort
+        missing = Set.new(self.values.flatten) - Set.new(self.keys)
+
+        if not missing.empty?
+          raise MissingVertex, "Cannot sort elements; cannot depend on missing elements #{missing.to_a}"
+        end
+
+        super
+
+      rescue TSort::Cyclic
+        raise CycleError, "Cannot sort elements; found the following cycles: #{cycles.inspect}"
+      end
+
+      class CycleError < StandardError; end
+      class MissingVertex < StandardError; end
+    end
+  end
+end
diff --git a/spec/unit/core/directed_graph_spec.rb b/spec/unit/core/directed_graph_spec.rb
new file mode 100644
index 0000000..1b68237
--- /dev/null
+++ b/spec/unit/core/directed_graph_spec.rb
@@ -0,0 +1,79 @@
+require 'spec_helper'
+require 'facter/core/directed_graph'
+
+describe Facter::Core::DirectedGraph do
+  subject(:graph) { described_class.new }
+
+  describe "detecting cycles" do
+    it "is acyclic if the graph is empty" do
+      expect(graph).to be_acyclic
+    end
+
+    it "is acyclic if the graph has no edges" do
+      graph[:one] = []
+      graph[:two] = []
+
+      expect(graph).to be_acyclic
+    end
+
+    it "is acyclic if a vertex has an edge to itself" do
+      graph[:one] = [:one]
+      expect(graph).to be_acyclic
+    end
+
+    it "is acyclic if there are no loops in the graph" do
+      graph[:one] = [:two, :three]
+      graph[:two] = [:four]
+      graph[:three] = [:four]
+      graph[:four] = []
+
+      expect(graph).to be_acyclic
+    end
+
+    it "is cyclic if there is a loop in the graph" do
+      graph[:one] = [:two]
+      graph[:two] = [:one]
+      expect(graph).to_not be_acyclic
+    end
+
+    it "can return the cycles in the graph" do
+      graph[:one] = [:two]
+      graph[:two] = [:one]
+
+      graph[:three] = [:four]
+      graph[:four] = [:three]
+
+      first_cycle = graph.cycles.find { |cycle| cycle.include? :one }
+      second_cycle = graph.cycles.find { |cycle| cycle.include? :three }
+
+      expect(first_cycle).to include :two
+      expect(second_cycle).to include :four
+    end
+  end
+
+  describe "sorting" do
+    it "returns the vertices in topologically sorted order" do
+      graph[:one] = [:two, :three]
+      graph[:two] = [:three]
+      graph[:three] = []
+      expect(graph.tsort).to eq [:three, :two, :one]
+    end
+
+    it "raises an error if there is a cycle in the graph" do
+      graph[:one] = [:two]
+      graph[:two] = [:one]
+
+      expect {
+        graph.tsort
+      }.to raise_error(Facter::Core::DirectedGraph::CycleError, /found the following cycles:/)
+    end
+
+    it "raises an error if there is an edge to a non-existent vertex" do
+      graph[:one] = [:two, :three]
+      graph[:two] = [:three]
+      expect {
+        graph.tsort
+      }.to raise_error(Facter::Core::DirectedGraph::MissingVertex, /missing elements.*three/)
+    end
+  end
+end

-- 
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-puppet/facter.git