Fixed #1021 -- the problem was that my method of determining

the in-degree sometimes resulted in a lower number than the
number of in-edges.

3 files changed, 24 insertions, 6 deletions

diff --git a/CHANGELOG b/CHANGELOG
index ff65331cb..635aabf25 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,3 +1,7 @@
+    Fixed #1021 -- the problem was that my method of determining
+    the in-degree sometimes resulted in a lower number than the
+    number of in-edges.
+
     Fixed #997 -- virtual defined types are no longer evaluated.
     NOTE: This introduces a behaviour change, in that you previously
     could realize a resource within a virtual defined resource, and now
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 503e4814c..48f393f77 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -51,10 +51,12 @@ class Puppet::SimpleGraph
 
         # Create methods for returning the degree and edges.
         [:in, :out].each do |direction|
-            define_method("%s_degree" % direction) do
-                @adjacencies[direction].length
-            end
-
+            # LAK:NOTE If you decide to create methods for directly
+            # testing the degree, you'll have to get the values and flatten
+            # the results -- you might have duplicate edges, which can give
+            # a false impression of what the degree is.  That's just
+            # as expensive as just getting the edge list, so I've decided
+            # to only add this method.
             define_method("%s_edges" % direction) do
                 @adjacencies[direction].values.flatten
             end
@@ -126,8 +128,9 @@ class Puppet::SimpleGraph
 
         # Collect each of our vertices, with the number of in-edges each has.
         @vertices.each do |name, wrapper|
-            zeros << wrapper if wrapper.in_degree == 0
-            degree[wrapper.vertex] = wrapper.in_edges
+            edges = wrapper.in_edges
+            zeros << wrapper if edges.length == 0
+            degree[wrapper.vertex] = edges
         end
 
         # Iterate over each 0-degree vertex, decrementing the degree of
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index c8fe14cf3..e1e42e40f 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -266,4 +266,15 @@ describe Puppet::SimpleGraph, " when sorting the graph" do
         add_edges :a => :b, :b => :e, :c => :a, :d => :c
         proc { @graph.topsort }.should_not raise_error
     end
+
+    # Our graph's add_edge method is smart enough not to add
+    # duplicate edges, so we use the objects, which it doesn't
+    # check.
+    it "should be able to sort graphs with duplicate edges" do
+        one = Puppet::Relationship.new(:a, :b)
+        @graph.add_edge(one)
+        two = Puppet::Relationship.new(:a, :b)
+        @graph.add_edge(two)
+        proc { @graph.topsort }.should_not raise_error
+    end
 end