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
'#to_dot' do
115 it
'gives the dot notation of a simple graph' do
116 v1
= Vertex
.new(:name => :v1)
117 v2
= Vertex
.new(:name => :v2)
118 g
.connect(v1
, v2
, :type => :edge_type)
119 g
.to_dot
.should
== "graph {\n#{v1.object_id.to_s};\n#{v2.object_id.to_s};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s};\n}"
122 it
"gives the dot notation of a simple graph, with vertex attributes" do
123 v1
= Vertex
.new(:name => :v1)
124 v2
= Vertex
.new(:name => :v2)
125 g
.connect(v1
, v2
, :type => :edge_type)
126 gdot
= g
.to_dot(:vertex_args => {:label => :name})
127 gdot
.should
== "graph {\n#{v1.object_id.to_s} {label = \"#{v1.name}\"};\n#{v2.object_id.to_s} {label = \"#{v2.name}\"};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s};\n}"
130 it
"gives the dot notation of a simple graph, with vertices generated by a block" do
131 v1
= Vertex
.new(:name => :v1)
132 v2
= Vertex
.new(:name => :v2)
133 g
.connect(v1
, v2
, :type => :edge_type)
134 gdot
= g
.to_dot(:vertex_block => lambda
{|v
| v
.name
.to_s
+ ';'})
135 gdot
.should
== "graph {\n#{v1.name};\n#{v2.name};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s};\n}"
138 it
"gives the dot notation of a simple graph, with vertex and edge attributes" do
139 v1
= Vertex
.new(:name => :v1)
140 v2
= Vertex
.new(:name => :v2)
141 g
.connect(v1
, v2
, :type => :edge_type)
142 gdot
= g
.to_dot(:edge_args => {:label => :type}, :vertex_args => {:label => :name})
143 gdot
.should
== "graph {\n#{v1.object_id.to_s} {label = \"#{v1.name}\"};\n#{v2.object_id.to_s} {label = \"#{v2.name}\"};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s} {label = \"#{g.edges[0].type}\"};\n}"
146 it
"gives the dot notation of a simple graph, with vertices and edges generated by a block" do
147 v1
= Vertex
.new(:name => :v1)
148 v2
= Vertex
.new(:name => :v2)
149 g
.connect(v1
, v2
, :type => :edge_type)
150 gdot
= g
.to_dot(:vertex_block => lambda
{|v
| v
.name
.to_s
+ ';'},
151 :edge_block => lambda
{|e
| "#{e.vertices[0].name.to_s} -- #{e.vertices[1].name.to_s} {label = \"#{e.type.to_s}\"};"})
152 gdot
.should
== "graph {\n#{v1.name};\n#{v2.name};\n#{v1.name} -- #{v2.name} {label = \"#{g.edges[0].type}\"};\n}"
157 describe
'product' do
158 it
'finds a product graph of a pair of one-vertex graphs' do
165 product
= g1
.product g2
167 product
.vertices
.should be_empty
168 #product.vertices.first.g1_vertex.should == g1v1
169 #product.vertices.first.g2_vertex.should == g2v1
170 product
.edges
.should be_empty
173 it
'finds a product graph of a pair of simple graphs' do
176 g1v1
= Vertex
.new(:name => :g1v1)
177 g1v2
= Vertex
.new(:name => :g1v2)
178 g1
.connect(g1v1
, g1v2
)
179 g2v1
= Vertex
.new(:name => :g2v1)
180 g2v2
= Vertex
.new(:name => :g2v2)
181 g2
.connect(g2v1
, g2v2
)
184 pg
.should
have(4).vertices
185 pg
.should
have(2).edges
188 it
'finds a product graph of not-quite-simple graph' do
191 g1v1
= Vertex
.new(:name => :g1v1)
192 g1v2
= Vertex
.new(:name => :g1v2)
193 g1v3
= Vertex
.new(:name => :g1v3)
194 g1
.connect(g1v1
, g1v2
)
195 g1
.connect(g1v2
, g1v3
)
196 g2v1
= Vertex
.new(:name => :g2v1)
197 g2v2
= Vertex
.new(:name => :g2v2)
198 g2v3
= Vertex
.new(:name => :g2v3)
199 g2
.connect(g2v1
, g2v2
)
200 g2
.connect(g2v2
, g2v3
)
203 pg
.should
have(9).vertices
204 pg
.should
have(8).edges
207 it
'finds a product graph of a simple graph with edge types' do
210 g1v1
= Vertex
.new(:name => :g1v1)
211 g1v2
= Vertex
.new(:name => :g1v2)
212 g1v3
= Vertex
.new(:name => :g1v3)
213 g1
.connect(g1v1
, g1v2
, :type => :t1)
214 g1
.connect(g1v2
, g1v3
, :type => :t2)
215 g2v1
= Vertex
.new(:name => :g2v1)
216 g2v2
= Vertex
.new(:name => :g2v2)
217 g2v3
= Vertex
.new(:name => :g2v3)
218 g2
.connect(g2v1
, g2v2
, :type => :t1)
219 g2
.connect(g2v2
, g2v3
, :type => :t2)
222 pg
.should
have(7).vertices
223 pg
.should
have(4).edges
226 it
'finds a product graph of the example graph from paper' do
227 pending
'implementation of directed graphs as operands of the product graph'
230 a
= Vertex
.new(:name => :a)
231 a1
= Vertex
.new(:name => :a1)
232 a2
= Vertex
.new(:name => :a2)
233 g1
.connect(a
, a1
, :type => :l1)
234 g1
.connect(a
, a2
, :type => :l1)
235 g1
.connect(a1
, a2
, :type => :l2)
236 b
= Vertex
.new(:name => :b)
237 b1
= Vertex
.new(:name => :b1)
238 b2
= Vertex
.new(:name => :b2)
239 g2
.connect(b
, b1
, :type => :l1)
240 g2
.connect(b
, b2
, :type => :l2)
241 g2
.connect(b1
, b2
, :type => :l2)
244 pg
.should
have(4).edges
245 pg
.should
have(6).vertices
249 describe
'initial_similarity' do
253 g1v1
= Vertex
.new(:name => :g1v1)
254 g1v2
= Vertex
.new(:name => :g1v2)
255 g1
.connect(g1v1
, g1v2
)
256 g2v1
= Vertex
.new(:name => :g2v1)
257 g2v2
= Vertex
.new(:name => :g2v2)
258 g2
.connect(g2v1
, g2v2
)
262 def simple_name_similarity(n1
, n2
)
263 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
266 it
'should give all nodes an initial similarity of 1 if no block is given' do
267 @pg.initial_similarity
268 @pg.vertices
.each
do |v
|
269 v
.initial_similarity
.should
be_within(0.001).of(1.0)
270 v
.similarity
.should
be_within(0.001).of(1.0)
274 it
'should give all nodes the similarity as defined by the given block' do
275 @pg.initial_similarity
{|v
| simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
}
276 @pg.vertices
.each
do |v
|
277 v
.initial_similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
278 v
.similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
282 end #initial similarity
284 describe
'similarity flood' do
285 it
'similarity floods a graph of two nodes' do
288 g1v1
= Vertex
.new(:name => :g1v1)
289 g1v2
= Vertex
.new(:name => :g1v2)
290 g1
.connect(g1v1
, g1v2
)
291 g2v1
= Vertex
.new(:name => :g2v1)
292 g2v2
= Vertex
.new(:name => :g2v2)
293 g2
.connect(g2v1
, g2v2
)
296 pg
.initial_similarity
298 pg
.vertices
.each
do |v
|
299 v
.similarity
.should
be_within(0.001).of(1.0)
303 it
'similarity floods a graph of three nodes, a -- b -- c' do
306 g1v1
= Vertex
.new(:name => :g1v1)
307 g1v2
= Vertex
.new(:name => :g1v2)
308 g1v3
= Vertex
.new(:name => :g1v3)
309 g1
.connect(g1v1
, g1v2
, :type => :t1)
310 g1
.connect(g1v2
, g1v3
, :type => :t2)
311 g2v1
= Vertex
.new(:name => :g2v1)
312 g2v2
= Vertex
.new(:name => :g2v2)
313 g2v3
= Vertex
.new(:name => :g2v3)
314 g2
.connect(g2v1
, g2v2
, :type => :t1)
315 g2
.connect(g2v2
, g2v3
, :type => :t2)
318 pg
.initial_similarity
320 expected_similarities
= {
322 'g1v1:g2v2' => 0.6666666666666666,
323 'g1v2:g2v1' => 0.6666666666666666,
325 'g1v2:g2v3' => 0.6666666666666666,
326 'g1v3:g2v2' => 0.6666666666666666,
328 pg
.vertices
.each
do |v
|
329 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
330 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
334 it
'simialrity floods the sample graph from the paper' do
336 ab
= Vertex
.new(:name => 'a:b')
337 a1b1
= Vertex
.new(:name => 'a1:b1')
338 a2b1
= Vertex
.new(:name => 'a2:b1')
339 a1b2
= Vertex
.new(:name => 'a1:b2')
340 a1b
= Vertex
.new(:name => 'a1:b')
341 a2b2
= Vertex
.new(:name => 'a2:b2')
342 pg
.connect(ab
, a1b1
, :type => :l1)
343 pg
.connect(ab
, a2b1
, :type => :l1)
344 pg
.connect(a2b1
, a1b2
, :type => :l2)
345 pg
.connect(a1b
, a2b2
, :type => :l2)
346 pg
.initial_similarity
349 expected_similarities
= {
356 pg
.vertices
.each
do |v
|
357 v
.similarity
.should
be_within(0.02).of(expected_similarities
[v
.name
])
361 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update' do
364 g1v1
= Vertex
.new(:name => :g1v1)
365 g1v2
= Vertex
.new(:name => :g1v2)
366 g1v3
= Vertex
.new(:name => :g1v3)
367 g1
.connect(g1v1
, g1v2
, :type => :t1)
368 g1
.connect(g1v2
, g1v3
, :type => :t2)
369 g2v1
= Vertex
.new(:name => :g2v1)
370 g2v2
= Vertex
.new(:name => :g2v2)
371 g2v3
= Vertex
.new(:name => :g2v3)
372 g2
.connect(g2v1
, g2v2
, :type => :t1)
373 g2
.connect(g2v2
, g2v3
, :type => :t2)
376 pg
.initial_similarity
377 pg
.similarity_flood
do |v
|
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
= {
389 'g1v1:g2v2' => 0.6666666666666666,
390 'g1v2:g2v1' => 0.6666666666666666,
392 'g1v2:g2v3' => 0.6666666666666666,
393 'g1v3:g2v2' => 0.6666666666666666,
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 A)' 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
|
418 v
.similarity
= v
.initial_similarity
419 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
420 edge_groups
.each
do |type
, edges
|
423 e
.other_end(v
).similarity
+= v
.last_similarity
/ n
428 expected_similarities
= {
429 'g1v1:g2v1' => 0.9269662921348315,
431 'g1v2:g2v1' => 0.6179775280898876,
434 'g1v3:g2v2' => 0.6179775280898876,
435 'g1v3:g2v3' => 0.6179775280898876}
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 B)' 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
|
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
= {
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
])
483 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method C)' do
486 g1v1
= Vertex
.new(:name => :g1v1)
487 g1v2
= Vertex
.new(:name => :g1v2)
488 g1v3
= Vertex
.new(:name => :g1v3)
489 g1
.connect(g1v1
, g1v2
, :type => :t1)
490 g1
.connect(g1v2
, g1v3
, :type => :t2)
491 g2v1
= Vertex
.new(:name => :g2v1)
492 g2v2
= Vertex
.new(:name => :g2v2)
493 g2v3
= Vertex
.new(:name => :g2v3)
494 g2
.connect(g2v1
, g2v2
, :type => :t1)
495 g2
.connect(g2v2
, g2v3
, :type => :t2)
498 pg
.initial_similarity
499 pg
.similarity_flood
do |v
|
500 v
.similarity
= v
.initial_similarity
+ v
.last_similarity
501 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
502 edge_groups
.each
do |type
, edges
|
505 e
.other_end(v
).similarity
+= (v
.initial_similarity
+ v
.last_similarity
) / n
510 expected_similarities
= {
511 'g1v1:g2v1' => 0.8282781862745098,
513 'g1v2:g2v1' => 0.41421568627450983,
516 'g1v3:g2v2' => 0.41421568627450983,
517 'g1v3:g2v3' => 0.41421568627450983}
518 pg
.vertices
.each
do |v
|
519 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
520 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
523 end # similarity_flood