← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/puppet/oneiric-security

« back to all changes in this revision

Viewing changes to spec/unit/simple_graph.rb

  • Committer: Bazaar Package Importer
  • Author(s): Micah Anderson
  • Date: 2008-07-26 15:43:45 UTC
  • mto: (3.1.1 lenny) (1.3.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20080726154345-1fmgo76b4l72ulvc
Import upstream version 0.24.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
spec/unit/simple_graph.rb
 
1
#!/usr/bin/env ruby
 
2
#
 
3
#  Created by Luke Kanies on 2007-11-1.
 
4
#  Copyright (c) 2006. All rights reserved.
 
5
 
 
6
require File.dirname(__FILE__) + '/../spec_helper'
 
7
require 'puppet/simple_graph'
 
8
 
 
9
describe Puppet::SimpleGraph do
 
10
    it "should return the number of its vertices as its length" do
 
11
        @graph = Puppet::SimpleGraph.new
 
12
        @graph.add_vertex("one")
 
13
        @graph.add_vertex("two")
 
14
        @graph.size.should == 2
 
15
    end
 
16
 
 
17
    it "should consider itself a directed graph" do
 
18
        Puppet::SimpleGraph.new.directed?.should be_true
 
19
    end
 
20
 
 
21
    it "should provide a method for reversing the graph" do
 
22
        @graph = Puppet::SimpleGraph.new
 
23
        @graph.add_edge(:one, :two)
 
24
        @graph.reversal.edge?(:two, :one).should be_true
 
25
    end
 
26
 
 
27
    it "should be able to produce a dot graph" do
 
28
        @graph = Puppet::SimpleGraph.new
 
29
        @graph.add_edge(:one, :two)
 
30
 
 
31
        proc { @graph.to_dot_graph }.should_not raise_error
 
32
    end
 
33
end
 
34
 
 
35
describe Puppet::SimpleGraph, " when managing vertices" do
 
36
    before do
 
37
        @graph = Puppet::SimpleGraph.new
 
38
    end
 
39
 
 
40
    it "should provide a method to add a vertex" do
 
41
        @graph.add_vertex(:test)
 
42
        @graph.vertex?(:test).should be_true
 
43
    end
 
44
 
 
45
    it "should ignore already-present vertices when asked to add a vertex" do
 
46
        @graph.add_vertex(:test)
 
47
        proc { @graph.add_vertex(:test) }.should_not raise_error
 
48
    end
 
49
 
 
50
    it "should return true when asked if a vertex is present" do
 
51
        @graph.add_vertex(:test)
 
52
        @graph.vertex?(:test).should be_true
 
53
    end
 
54
 
 
55
    it "should return false when asked if a non-vertex is present" do
 
56
        @graph.vertex?(:test).should be_false
 
57
    end
 
58
 
 
59
    it "should return all set vertices when asked" do
 
60
        @graph.add_vertex(:one)
 
61
        @graph.add_vertex(:two)
 
62
        @graph.vertices.length.should == 2
 
63
        @graph.vertices.should include(:one)
 
64
        @graph.vertices.should include(:two)
 
65
    end
 
66
 
 
67
    it "should remove a given vertex when asked" do
 
68
        @graph.add_vertex(:one)
 
69
        @graph.remove_vertex!(:one)
 
70
        @graph.vertex?(:one).should be_false
 
71
    end
 
72
 
 
73
    it "should do nothing when a non-vertex is asked to be removed" do
 
74
        proc { @graph.remove_vertex!(:one) }.should_not raise_error
 
75
    end
 
76
end
 
77
 
 
78
describe Puppet::SimpleGraph, " when managing edges" do
 
79
    before do
 
80
        @graph = Puppet::SimpleGraph.new
 
81
    end
 
82
 
 
83
    it "should provide a method to test whether a given vertex pair is an edge" do
 
84
        @graph.should respond_to(:edge?)
 
85
    end
 
86
 
 
87
    it "should provide a method to add an edge as an instance of the edge class" do
 
88
        edge = Puppet::Relationship.new(:one, :two)
 
89
        @graph.add_edge(edge)
 
90
        @graph.edge?(:one, :two).should be_true
 
91
    end
 
92
 
 
93
    it "should provide a method to add an edge by specifying the two vertices" do
 
94
        @graph.add_edge(:one, :two)
 
95
        @graph.edge?(:one, :two).should be_true
 
96
    end
 
97
 
 
98
    it "should provide a method to add an edge by specifying the two vertices and a label" do
 
99
        @graph.add_edge(:one, :two, :stuff => :awesome)
 
100
        @graph.edge?(:one, :two).should be_true
 
101
    end
 
102
 
 
103
    it "should provide a method for retrieving an edge label" do
 
104
        edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome)
 
105
        @graph.add_edge(edge)
 
106
        @graph.edge_label(:one, :two).should == {:stuff => :awesome}
 
107
    end
 
108
 
 
109
    it "should provide a method for retrieving an edge" do
 
110
        edge = Puppet::Relationship.new(:one, :two)
 
111
        @graph.add_edge(edge)
 
112
        @graph.edge(:one, :two).should equal(edge)
 
113
    end
 
114
 
 
115
    it "should add the edge source as a vertex if it is not already" do
 
116
        edge = Puppet::Relationship.new(:one, :two)
 
117
        @graph.add_edge(edge)
 
118
        @graph.vertex?(:one).should be_true
 
119
    end
 
120
 
 
121
    it "should add the edge target as a vertex if it is not already" do
 
122
        edge = Puppet::Relationship.new(:one, :two)
 
123
        @graph.add_edge(edge)
 
124
        @graph.vertex?(:two).should be_true
 
125
    end
 
126
 
 
127
    it "should return all edges as edge instances when asked" do
 
128
        one = Puppet::Relationship.new(:one, :two)
 
129
        two = Puppet::Relationship.new(:two, :three)
 
130
        @graph.add_edge(one)
 
131
        @graph.add_edge(two)
 
132
        edges = @graph.edges
 
133
        edges.length.should == 2
 
134
        edges.should include(one)
 
135
        edges.should include(two)
 
136
    end
 
137
 
 
138
    it "should remove an edge when asked" do
 
139
        edge = Puppet::Relationship.new(:one, :two)
 
140
        @graph.add_edge(edge)
 
141
        @graph.remove_edge!(edge)
 
142
        @graph.edge?(edge.source, edge.target).should be_false
 
143
    end
 
144
 
 
145
    it "should remove all related edges when a vertex is removed" do
 
146
        one = Puppet::Relationship.new(:one, :two)
 
147
        two = Puppet::Relationship.new(:two, :three)
 
148
        @graph.add_edge(one)
 
149
        @graph.add_edge(two)
 
150
        @graph.remove_vertex!(:two)
 
151
        @graph.edge?(:one, :two).should be_false
 
152
        @graph.edge?(:two, :three).should be_false
 
153
        @graph.edges.length.should == 0
 
154
    end
 
155
end
 
156
 
 
157
describe Puppet::SimpleGraph, " when finding adjacent vertices" do
 
158
    before do
 
159
        @graph = Puppet::SimpleGraph.new
 
160
        @one_two = Puppet::Relationship.new(:one, :two)
 
161
        @two_three = Puppet::Relationship.new(:two, :three)
 
162
        @one_three = Puppet::Relationship.new(:one, :three)
 
163
        @graph.add_edge(@one_two)
 
164
        @graph.add_edge(@one_three)
 
165
        @graph.add_edge(@two_three)
 
166
    end
 
167
 
 
168
    it "should return adjacent vertices" do
 
169
        adj = @graph.adjacent(:one)
 
170
        adj.should be_include(:three)
 
171
        adj.should be_include(:two)
 
172
    end
 
173
 
 
174
    it "should default to finding :out vertices" do
 
175
        @graph.adjacent(:two).should == [:three]
 
176
    end
 
177
 
 
178
    it "should support selecting :in vertices" do
 
179
        @graph.adjacent(:two, :direction => :in).should == [:one]
 
180
    end
 
181
 
 
182
    it "should default to returning the matching vertices as an array of vertices" do
 
183
        @graph.adjacent(:two).should == [:three]
 
184
    end
 
185
 
 
186
    it "should support returning an array of matching edges" do
 
187
        @graph.adjacent(:two, :type => :edges).should == [@two_three]
 
188
    end
 
189
end
 
190
 
 
191
describe Puppet::SimpleGraph, " when clearing" do
 
192
    before do
 
193
        @graph = Puppet::SimpleGraph.new
 
194
        one = Puppet::Relationship.new(:one, :two)
 
195
        two = Puppet::Relationship.new(:two, :three)
 
196
        @graph.add_edge(one)
 
197
        @graph.add_edge(two)
 
198
 
 
199
        @graph.clear
 
200
    end
 
201
 
 
202
    it "should remove all vertices" do
 
203
        @graph.vertices.should be_empty
 
204
    end
 
205
 
 
206
    it "should remove all edges" do
 
207
        @graph.edges.should be_empty
 
208
    end
 
209
end
 
210
 
 
211
describe Puppet::SimpleGraph, " when reversing graphs" do
 
212
    before do
 
213
        @graph = Puppet::SimpleGraph.new
 
214
    end
 
215
 
 
216
    it "should provide a method for reversing the graph" do
 
217
        @graph.add_edge(:one, :two)
 
218
        @graph.reversal.edge?(:two, :one).should be_true
 
219
    end
 
220
 
 
221
    it "should add all vertices to the reversed graph" do
 
222
        @graph.add_edge(:one, :two)
 
223
        @graph.vertex?(:one).should be_true
 
224
        @graph.vertex?(:two).should be_true
 
225
    end
 
226
    
 
227
    it "should retain labels on edges" do
 
228
        @graph.add_edge(:one, :two, :stuff => :awesome)
 
229
        edge = @graph.reversal.edge(:two, :one)
 
230
        edge.label.should == {:stuff => :awesome}
 
231
    end
 
232
end
 
233
 
 
234
describe Puppet::SimpleGraph, " when sorting the graph" do
 
235
    before do
 
236
        @graph = Puppet::SimpleGraph.new
 
237
    end
 
238
 
 
239
    def add_edges(hash)
 
240
        hash.each do |a,b|
 
241
            @graph.add_edge(a, b)
 
242
        end
 
243
    end
 
244
 
 
245
    it "should sort the graph topologically" do
 
246
        add_edges :a => :b, :b => :c
 
247
        @graph.topsort.should == [:a, :b, :c]
 
248
    end
 
249
 
 
250
    it "should fail on two-vertex loops" do
 
251
        add_edges :a => :b, :b => :a
 
252
        proc { @graph.topsort }.should raise_error(Puppet::Error)
 
253
    end
 
254
 
 
255
    it "should fail on multi-vertex loops" do
 
256
        add_edges :a => :b, :b => :c, :c => :a
 
257
        proc { @graph.topsort }.should raise_error(Puppet::Error)
 
258
    end
 
259
 
 
260
    it "should fail when a larger tree contains a small cycle" do
 
261
        add_edges :a => :b, :b => :a, :c => :a, :d => :c
 
262
        proc { @graph.topsort }.should raise_error(Puppet::Error)
 
263
    end
 
264
 
 
265
    it "should succeed on trees with no cycles" do
 
266
        add_edges :a => :b, :b => :e, :c => :a, :d => :c
 
267
        proc { @graph.topsort }.should_not raise_error
 
268
    end
 
269
 
 
270
    # Our graph's add_edge method is smart enough not to add
 
271
    # duplicate edges, so we use the objects, which it doesn't
 
272
    # check.
 
273
    it "should be able to sort graphs with duplicate edges" do
 
274
        one = Puppet::Relationship.new(:a, :b)
 
275
        @graph.add_edge(one)
 
276
        two = Puppet::Relationship.new(:a, :b)
 
277
        @graph.add_edge(two)
 
278
        proc { @graph.topsort }.should_not raise_error
 
279
    end
 
280
end