1 require File
.expand_path(File
.dirname(__FILE__
) + '/../spec_helper')
12 let (:g) { Graph
.new
}
13 describe
"#initialize" do
14 it
"creates an empty graph" do
16 g
.edges
.should be_empty
17 g
.vertices
.should be_empty
20 it
"creates a graph with some parameters" do
21 g
= Graph
.new
:value1 => 1, :value2 => "value2", :value3 => :v3
23 g
.value2
.should
== "value2"
24 g
.value3
.should
== :v3
25 g
.value4
.should be_nil
30 describe
"adds attributes" do
31 it
"adds then reports arbitrary attributes" do
38 it
"adds a set of vertices" do
39 g
.vertices
.should be_empty
43 g
.should
have(2).vertices
44 g
.vertices
.should
include(v1
)
45 g
.vertices
.should
include(v2
)
48 it
"adds a set of edges" do
49 g
.edges
.should be_empty
53 g
.should
have(2).edges
54 g
.edges
.should
include(e1
)
55 g
.edges
.should
include(e2
)
58 it
"adds a mixed set of vertices and edges" do
59 g
.vertices
.should be_empty
60 g
.edges
.should be_empty
65 g
<< v1
<< e1
<< v2
<< e2
66 g
.should
have(2).vertices
67 g
.vertices
.should
include(v1
)
68 g
.vertices
.should
include(v2
)
69 g
.should
have(2).edges
70 g
.edges
.should
include(e1
)
71 g
.edges
.should
include(e2
)
74 it
"adds a subclass of Vertex" do
75 g
.vertices
.should be_empty
79 g
.should
have(2).vertices
80 g
.vertices
.should
include(v1
)
81 g
.vertices
.should
include(v2
)
86 it
"adds and records an edge between vertices" do
87 g
.vertices
.should be_empty
88 g
.edges
.should be_empty
89 v1
= Vertex
.new(:name => :v1)
90 v2
= Vertex
.new(:name => :v2)
93 g
.should
have(2).vertices
94 g
.vertices
.should
include(v1
)
95 g
.vertices
.should
include(v2
)
96 g
.should
have(1).edges
99 it
"adds and records an edge with attributes between vertices" do
100 g
.vertices
.should be_empty
101 g
.edges
.should be_empty
102 v1
= Vertex
.new(:name => :v1)
103 v2
= Vertex
.new(:name => :v2)
104 g
.connect(v1
, v2
, :type => :edge_type)
106 g
.should
have(2).vertices
107 g
.vertices
.should
include(v1
)
108 g
.vertices
.should
include(v2
)
109 g
.should
have(1).edges
110 g
.edges
[0].type
.should
== :edge_type
114 describe
"product" do
115 it
"finds a product graph of a pair of one-vertex graphs" do
122 product
= g1
.product g2
124 product
.vertices
.should be_empty
125 #product.vertices.first.g1_vertex.should == g1v1
126 #product.vertices.first.g2_vertex.should == g2v1
127 product
.edges
.should be_empty
130 it
"finds a product graph of a pair of simple graphs" do
133 g1v1
= Vertex
.new(:name => :g1v1)
134 g1v2
= Vertex
.new(:name => :g1v2)
135 g1
.connect(g1v1
, g1v2
)
136 g2v1
= Vertex
.new(:name => :g2v1)
137 g2v2
= Vertex
.new(:name => :g2v2)
138 g2
.connect(g2v1
, g2v2
)
141 pg
.should
have(4).vertices
142 pg
.should
have(2).edges
145 it
"finds a product graph of not-quite-simple graph" do
148 g1v1
= Vertex
.new(:name => :g1v1)
149 g1v2
= Vertex
.new(:name => :g1v2)
150 g1v3
= Vertex
.new(:name => :g1v3)
151 g1
.connect(g1v1
, g1v2
)
152 g1
.connect(g1v2
, g1v3
)
153 g2v1
= Vertex
.new(:name => :g2v1)
154 g2v2
= Vertex
.new(:name => :g2v2)
155 g2v3
= Vertex
.new(:name => :g2v3)
156 g2
.connect(g2v1
, g2v2
)
157 g2
.connect(g2v2
, g2v3
)
160 pg
.should
have(9).vertices
161 pg
.should
have(8).edges
164 it
"finds a product graph of a simple graph with edge types" do
167 g1v1
= Vertex
.new(:name => :g1v1)
168 g1v2
= Vertex
.new(:name => :g1v2)
169 g1v3
= Vertex
.new(:name => :g1v3)
170 g1
.connect(g1v1
, g1v2
, :type => :t1)
171 g1
.connect(g1v2
, g1v3
, :type => :t2)
172 g2v1
= Vertex
.new(:name => :g2v1)
173 g2v2
= Vertex
.new(:name => :g2v2)
174 g2v3
= Vertex
.new(:name => :g2v3)
175 g2
.connect(g2v1
, g2v2
, :type => :t1)
176 g2
.connect(g2v2
, g2v3
, :type => :t2)
179 pg
.should
have(7).vertices
180 pg
.should
have(4).edges
183 it
"finds a product graph of the example graph from paper" do
184 pending
"implementation of directed graphs as operands of the product graph"
187 a
= Vertex
.new(:name => :a)
188 a1
= Vertex
.new(:name => :a1)
189 a2
= Vertex
.new(:name => :a2)
190 g1
.connect(a
, a1
, :type => :l1)
191 g1
.connect(a
, a2
, :type => :l1)
192 g1
.connect(a1
, a2
, :type => :l2)
193 b
= Vertex
.new(:name => :b)
194 b1
= Vertex
.new(:name => :b1)
195 b2
= Vertex
.new(:name => :b2)
196 g2
.connect(b
, b1
, :type => :l1)
197 g2
.connect(b
, b2
, :type => :l2)
198 g2
.connect(b1
, b2
, :type => :l2)
201 pg
.should
have(4).edges
202 pg
.should
have(6).vertices
208 describe
"initial_similarity" do
212 g1v1
= Vertex
.new(:name => :g1v1)
213 g1v2
= Vertex
.new(:name => :g1v2)
214 g1
.connect(g1v1
, g1v2
)
215 g2v1
= Vertex
.new(:name => :g2v1)
216 g2v2
= Vertex
.new(:name => :g2v2)
217 g2
.connect(g2v1
, g2v2
)
221 def simple_name_similarity(n1
, n2
)
222 1 - n1
.to_s
.codepoints
.to_a
.delete_if
{|c
| n2
.to_s
.codepoints
.to_a
.include? c
}.length
/ n1
.to_s
.length
.to_f
225 it
"should give all nodes an initial similarity of 1 if no block is given" do
226 @pg.initial_similarity
227 @pg.vertices
.each
do |v
|
228 v
.initial_similarity
.should
be_within(0.001).of(1.0)
229 v
.similarity
.should
be_within(0.001).of(1.0)
233 it
"should give all nodes the similarity as defined by the given block" do
234 @pg.initial_similarity
{|v
| simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
}
235 @pg.vertices
.each
do |v
|
236 v
.initial_similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
237 v
.similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
241 end #initial similarity
243 describe
"similarity flood" do
244 it
"similarity floods a graph of two nodes" do
247 g1v1
= Vertex
.new(:name => :g1v1)
248 g1v2
= Vertex
.new(:name => :g1v2)
249 g1
.connect(g1v1
, g1v2
)
250 g2v1
= Vertex
.new(:name => :g2v1)
251 g2v2
= Vertex
.new(:name => :g2v2)
252 g2
.connect(g2v1
, g2v2
)
255 pg
.initial_similarity
257 pg
.vertices
.each
do |v
|
258 v
.similarity
.should
be_within(0.001).of(1.0)
262 it
"similarity floods a graph of three nodes, a -- b -- c" do
265 g1v1
= Vertex
.new(:name => :g1v1)
266 g1v2
= Vertex
.new(:name => :g1v2)
267 g1v3
= Vertex
.new(:name => :g1v3)
268 g1
.connect(g1v1
, g1v2
, :type => :t1)
269 g1
.connect(g1v2
, g1v3
, :type => :t2)
270 g2v1
= Vertex
.new(:name => :g2v1)
271 g2v2
= Vertex
.new(:name => :g2v2)
272 g2v3
= Vertex
.new(:name => :g2v3)
273 g2
.connect(g2v1
, g2v2
, :type => :t1)
274 g2
.connect(g2v2
, g2v3
, :type => :t2)
277 pg
.initial_similarity
279 expected_similarities
= {
281 "g1v1:g2v2" => 0.6666666666666666,
282 "g1v2:g2v1" => 0.6666666666666666,
284 "g1v2:g2v3" => 0.6666666666666666,
285 "g1v3:g2v2" => 0.6666666666666666,
287 pg
.vertices
.each
do |v
|
288 name
= v
.g1_vertex
.name
.to_s
+ ':' + v
.g2_vertex
.name
.to_s
289 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
293 it
"simialrity floods the sample graph from the paper" do
295 ab
= Vertex
.new(:name => "a:b")
296 a1b1
= Vertex
.new(:name => "a1:b1")
297 a2b1
= Vertex
.new(:name => "a2:b1")
298 a1b2
= Vertex
.new(:name => "a1:b2")
299 a1b
= Vertex
.new(:name => "a1:b")
300 a2b2
= Vertex
.new(:name => "a2:b2")
301 pg
.connect(ab
, a1b1
, :type => :l1)
302 pg
.connect(ab
, a2b1
, :type => :l1)
303 pg
.connect(a2b1
, a1b2
, :type => :l2)
304 pg
.connect(a1b
, a2b2
, :type => :l2)
305 pg
.initial_similarity
308 expected_similarities
= {
315 pg
.vertices
.each
do |v
|
316 v
.similarity
.should
be_within(0.02).of(expected_similarities
[v
.name
])
320 it
"similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update" do
323 g1v1
= Vertex
.new(:name => :g1v1)
324 g1v2
= Vertex
.new(:name => :g1v2)
325 g1v3
= Vertex
.new(:name => :g1v3)
326 g1
.connect(g1v1
, g1v2
, :type => :t1)
327 g1
.connect(g1v2
, g1v3
, :type => :t2)
328 g2v1
= Vertex
.new(:name => :g2v1)
329 g2v2
= Vertex
.new(:name => :g2v2)
330 g2v3
= Vertex
.new(:name => :g2v3)
331 g2
.connect(g2v1
, g2v2
, :type => :t1)
332 g2
.connect(g2v2
, g2v3
, :type => :t2)
335 pg
.initial_similarity
336 pg
.similarity_flood
do |v
|
337 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
338 edge_groups
.each
do |type
, edges
|
341 e
.other_end(v
).similarity
+= v
.last_similarity
/ n
346 expected_similarities
= {
348 "g1v1:g2v2" => 0.6666666666666666,
349 "g1v2:g2v1" => 0.6666666666666666,
351 "g1v2:g2v3" => 0.6666666666666666,
352 "g1v3:g2v2" => 0.6666666666666666,
354 pg
.vertices
.each
do |v
|
355 name
= v
.g1_vertex
.name
.to_s
+ ':' + v
.g2_vertex
.name
.to_s
356 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
360 it
"similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method A)" do
363 g1v1
= Vertex
.new(:name => :g1v1)
364 g1v2
= Vertex
.new(:name => :g1v2)
365 g1v3
= Vertex
.new(:name => :g1v3)
366 g1
.connect(g1v1
, g1v2
, :type => :t1)
367 g1
.connect(g1v2
, g1v3
, :type => :t2)
368 g2v1
= Vertex
.new(:name => :g2v1)
369 g2v2
= Vertex
.new(:name => :g2v2)
370 g2v3
= Vertex
.new(:name => :g2v3)
371 g2
.connect(g2v1
, g2v2
, :type => :t1)
372 g2
.connect(g2v2
, g2v3
, :type => :t2)
375 pg
.initial_similarity
376 pg
.similarity_flood
do |v
|
377 v
.similarity
= v
.initial_similarity
378 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
379 edge_groups
.each
do |type
, edges
|
382 e
.other_end(v
).similarity
+= v
.last_similarity
/ n
387 expected_similarities
= {
388 "g1v1:g2v1" => 0.9269662921348315,
390 "g1v2:g2v1" => 0.6179775280898876,
393 "g1v3:g2v2" => 0.6179775280898876,
394 "g1v3:g2v3" => 0.6179775280898876}
395 pg
.vertices
.each
do |v
|
396 name
= v
.g1_vertex
.name
.to_s
+ ':' + v
.g2_vertex
.name
.to_s
397 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
401 it
"similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method B)" do
404 g1v1
= Vertex
.new(:name => :g1v1)
405 g1v2
= Vertex
.new(:name => :g1v2)
406 g1v3
= Vertex
.new(:name => :g1v3)
407 g1
.connect(g1v1
, g1v2
, :type => :t1)
408 g1
.connect(g1v2
, g1v3
, :type => :t2)
409 g2v1
= Vertex
.new(:name => :g2v1)
410 g2v2
= Vertex
.new(:name => :g2v2)
411 g2v3
= Vertex
.new(:name => :g2v3)
412 g2
.connect(g2v1
, g2v2
, :type => :t1)
413 g2
.connect(g2v2
, g2v3
, :type => :t2)
416 pg
.initial_similarity
417 pg
.similarity_flood
do |v
|
419 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
420 edge_groups
.each
do |type
, edges
|
423 e
.other_end(v
).similarity
+= (v
.initial_similarity
+ v
.last_similarity
) / n
428 expected_similarities
= {
436 pg
.vertices
.each
do |v
|
437 name
= v
.g1_vertex
.name
.to_s
+ ':' + v
.g2_vertex
.name
.to_s
438 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
442 it
"similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method C)" do
445 g1v1
= Vertex
.new(:name => :g1v1)
446 g1v2
= Vertex
.new(:name => :g1v2)
447 g1v3
= Vertex
.new(:name => :g1v3)
448 g1
.connect(g1v1
, g1v2
, :type => :t1)
449 g1
.connect(g1v2
, g1v3
, :type => :t2)
450 g2v1
= Vertex
.new(:name => :g2v1)
451 g2v2
= Vertex
.new(:name => :g2v2)
452 g2v3
= Vertex
.new(:name => :g2v3)
453 g2
.connect(g2v1
, g2v2
, :type => :t1)
454 g2
.connect(g2v2
, g2v3
, :type => :t2)
457 pg
.initial_similarity
458 pg
.similarity_flood
do |v
|
459 v
.similarity
= v
.initial_similarity
+ v
.last_similarity
460 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
461 edge_groups
.each
do |type
, edges
|
464 e
.other_end(v
).similarity
+= (v
.initial_similarity
+ v
.last_similarity
) / n
469 expected_similarities
= {
470 "g1v1:g2v1" => 0.8282781862745098,
472 "g1v2:g2v1" => 0.41421568627450983,
475 "g1v3:g2v2" => 0.41421568627450983,
476 "g1v3:g2v3" => 0.41421568627450983}
477 pg
.vertices
.each
do |v
|
478 name
= v
.g1_vertex
.name
.to_s
+ ':' + v
.g2_vertex
.name
.to_s
479 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
482 end # similarity_flood