7da0bb9c599275ed94e9fdcd04a4df427cf3bd3f
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
})
135 gdot
.should
== "graph {\n#{v1.name};\n#{v2.name};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s};\n}"
140 describe
'product' do
141 it
'finds a product graph of a pair of one-vertex graphs' do
148 product
= g1
.product g2
150 product
.vertices
.should be_empty
151 #product.vertices.first.g1_vertex.should == g1v1
152 #product.vertices.first.g2_vertex.should == g2v1
153 product
.edges
.should be_empty
156 it
'finds a product graph of a pair of simple graphs' do
159 g1v1
= Vertex
.new(:name => :g1v1)
160 g1v2
= Vertex
.new(:name => :g1v2)
161 g1
.connect(g1v1
, g1v2
)
162 g2v1
= Vertex
.new(:name => :g2v1)
163 g2v2
= Vertex
.new(:name => :g2v2)
164 g2
.connect(g2v1
, g2v2
)
167 pg
.should
have(4).vertices
168 pg
.should
have(2).edges
171 it
'finds a product graph of not-quite-simple graph' do
174 g1v1
= Vertex
.new(:name => :g1v1)
175 g1v2
= Vertex
.new(:name => :g1v2)
176 g1v3
= Vertex
.new(:name => :g1v3)
177 g1
.connect(g1v1
, g1v2
)
178 g1
.connect(g1v2
, g1v3
)
179 g2v1
= Vertex
.new(:name => :g2v1)
180 g2v2
= Vertex
.new(:name => :g2v2)
181 g2v3
= Vertex
.new(:name => :g2v3)
182 g2
.connect(g2v1
, g2v2
)
183 g2
.connect(g2v2
, g2v3
)
186 pg
.should
have(9).vertices
187 pg
.should
have(8).edges
190 it
'finds a product graph of a simple graph with edge types' do
193 g1v1
= Vertex
.new(:name => :g1v1)
194 g1v2
= Vertex
.new(:name => :g1v2)
195 g1v3
= Vertex
.new(:name => :g1v3)
196 g1
.connect(g1v1
, g1v2
, :type => :t1)
197 g1
.connect(g1v2
, g1v3
, :type => :t2)
198 g2v1
= Vertex
.new(:name => :g2v1)
199 g2v2
= Vertex
.new(:name => :g2v2)
200 g2v3
= Vertex
.new(:name => :g2v3)
201 g2
.connect(g2v1
, g2v2
, :type => :t1)
202 g2
.connect(g2v2
, g2v3
, :type => :t2)
205 pg
.should
have(7).vertices
206 pg
.should
have(4).edges
209 it
'finds a product graph of the example graph from paper' do
210 pending
'implementation of directed graphs as operands of the product graph'
213 a
= Vertex
.new(:name => :a)
214 a1
= Vertex
.new(:name => :a1)
215 a2
= Vertex
.new(:name => :a2)
216 g1
.connect(a
, a1
, :type => :l1)
217 g1
.connect(a
, a2
, :type => :l1)
218 g1
.connect(a1
, a2
, :type => :l2)
219 b
= Vertex
.new(:name => :b)
220 b1
= Vertex
.new(:name => :b1)
221 b2
= Vertex
.new(:name => :b2)
222 g2
.connect(b
, b1
, :type => :l1)
223 g2
.connect(b
, b2
, :type => :l2)
224 g2
.connect(b1
, b2
, :type => :l2)
227 pg
.should
have(4).edges
228 pg
.should
have(6).vertices
232 describe
'initial_similarity' do
236 g1v1
= Vertex
.new(:name => :g1v1)
237 g1v2
= Vertex
.new(:name => :g1v2)
238 g1
.connect(g1v1
, g1v2
)
239 g2v1
= Vertex
.new(:name => :g2v1)
240 g2v2
= Vertex
.new(:name => :g2v2)
241 g2
.connect(g2v1
, g2v2
)
245 def simple_name_similarity(n1
, n2
)
246 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
249 it
'should give all nodes an initial similarity of 1 if no block is given' do
250 @pg.initial_similarity
251 @pg.vertices
.each
do |v
|
252 v
.initial_similarity
.should
be_within(0.001).of(1.0)
253 v
.similarity
.should
be_within(0.001).of(1.0)
257 it
'should give all nodes the similarity as defined by the given block' do
258 @pg.initial_similarity
{|v
| simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
}
259 @pg.vertices
.each
do |v
|
260 v
.initial_similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
261 v
.similarity
.should
be_within(0.001).of( simple_name_similarity v
.g1_vertex
.name
, v
.g2_vertex
.name
)
265 end #initial similarity
267 describe
'similarity flood' do
268 it
'similarity floods a graph of two nodes' do
271 g1v1
= Vertex
.new(:name => :g1v1)
272 g1v2
= Vertex
.new(:name => :g1v2)
273 g1
.connect(g1v1
, g1v2
)
274 g2v1
= Vertex
.new(:name => :g2v1)
275 g2v2
= Vertex
.new(:name => :g2v2)
276 g2
.connect(g2v1
, g2v2
)
279 pg
.initial_similarity
281 pg
.vertices
.each
do |v
|
282 v
.similarity
.should
be_within(0.001).of(1.0)
286 it
'similarity floods a graph of three nodes, a -- b -- c' do
289 g1v1
= Vertex
.new(:name => :g1v1)
290 g1v2
= Vertex
.new(:name => :g1v2)
291 g1v3
= Vertex
.new(:name => :g1v3)
292 g1
.connect(g1v1
, g1v2
, :type => :t1)
293 g1
.connect(g1v2
, g1v3
, :type => :t2)
294 g2v1
= Vertex
.new(:name => :g2v1)
295 g2v2
= Vertex
.new(:name => :g2v2)
296 g2v3
= Vertex
.new(:name => :g2v3)
297 g2
.connect(g2v1
, g2v2
, :type => :t1)
298 g2
.connect(g2v2
, g2v3
, :type => :t2)
301 pg
.initial_similarity
303 expected_similarities
= {
305 'g1v1:g2v2' => 0.6666666666666666,
306 'g1v2:g2v1' => 0.6666666666666666,
308 'g1v2:g2v3' => 0.6666666666666666,
309 'g1v3:g2v2' => 0.6666666666666666,
311 pg
.vertices
.each
do |v
|
312 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
313 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
317 it
'simialrity floods the sample graph from the paper' do
319 ab
= Vertex
.new(:name => 'a:b')
320 a1b1
= Vertex
.new(:name => 'a1:b1')
321 a2b1
= Vertex
.new(:name => 'a2:b1')
322 a1b2
= Vertex
.new(:name => 'a1:b2')
323 a1b
= Vertex
.new(:name => 'a1:b')
324 a2b2
= Vertex
.new(:name => 'a2:b2')
325 pg
.connect(ab
, a1b1
, :type => :l1)
326 pg
.connect(ab
, a2b1
, :type => :l1)
327 pg
.connect(a2b1
, a1b2
, :type => :l2)
328 pg
.connect(a1b
, a2b2
, :type => :l2)
329 pg
.initial_similarity
332 expected_similarities
= {
339 pg
.vertices
.each
do |v
|
340 v
.similarity
.should
be_within(0.02).of(expected_similarities
[v
.name
])
344 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update' do
347 g1v1
= Vertex
.new(:name => :g1v1)
348 g1v2
= Vertex
.new(:name => :g1v2)
349 g1v3
= Vertex
.new(:name => :g1v3)
350 g1
.connect(g1v1
, g1v2
, :type => :t1)
351 g1
.connect(g1v2
, g1v3
, :type => :t2)
352 g2v1
= Vertex
.new(:name => :g2v1)
353 g2v2
= Vertex
.new(:name => :g2v2)
354 g2v3
= Vertex
.new(:name => :g2v3)
355 g2
.connect(g2v1
, g2v2
, :type => :t1)
356 g2
.connect(g2v2
, g2v3
, :type => :t2)
359 pg
.initial_similarity
360 pg
.similarity_flood
do |v
|
361 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
362 edge_groups
.each
do |type
, edges
|
365 e
.other_end(v
).similarity
+= v
.last_similarity
/ n
370 expected_similarities
= {
372 'g1v1:g2v2' => 0.6666666666666666,
373 'g1v2:g2v1' => 0.6666666666666666,
375 'g1v2:g2v3' => 0.6666666666666666,
376 'g1v3:g2v2' => 0.6666666666666666,
378 pg
.vertices
.each
do |v
|
379 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
380 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
384 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method A)' do
387 g1v1
= Vertex
.new(:name => :g1v1)
388 g1v2
= Vertex
.new(:name => :g1v2)
389 g1v3
= Vertex
.new(:name => :g1v3)
390 g1
.connect(g1v1
, g1v2
, :type => :t1)
391 g1
.connect(g1v2
, g1v3
, :type => :t2)
392 g2v1
= Vertex
.new(:name => :g2v1)
393 g2v2
= Vertex
.new(:name => :g2v2)
394 g2v3
= Vertex
.new(:name => :g2v3)
395 g2
.connect(g2v1
, g2v2
, :type => :t1)
396 g2
.connect(g2v2
, g2v3
, :type => :t2)
399 pg
.initial_similarity
400 pg
.similarity_flood
do |v
|
401 v
.similarity
= v
.initial_similarity
402 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
403 edge_groups
.each
do |type
, edges
|
406 e
.other_end(v
).similarity
+= v
.last_similarity
/ n
411 expected_similarities
= {
412 'g1v1:g2v1' => 0.9269662921348315,
414 'g1v2:g2v1' => 0.6179775280898876,
417 'g1v3:g2v2' => 0.6179775280898876,
418 'g1v3:g2v3' => 0.6179775280898876}
419 pg
.vertices
.each
do |v
|
420 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
421 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
425 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method B)' do
428 g1v1
= Vertex
.new(:name => :g1v1)
429 g1v2
= Vertex
.new(:name => :g1v2)
430 g1v3
= Vertex
.new(:name => :g1v3)
431 g1
.connect(g1v1
, g1v2
, :type => :t1)
432 g1
.connect(g1v2
, g1v3
, :type => :t2)
433 g2v1
= Vertex
.new(:name => :g2v1)
434 g2v2
= Vertex
.new(:name => :g2v2)
435 g2v3
= Vertex
.new(:name => :g2v3)
436 g2
.connect(g2v1
, g2v2
, :type => :t1)
437 g2
.connect(g2v2
, g2v3
, :type => :t2)
440 pg
.initial_similarity
441 pg
.similarity_flood
do |v
|
443 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
444 edge_groups
.each
do |type
, edges
|
447 e
.other_end(v
).similarity
+= (v
.initial_similarity
+ v
.last_similarity
) / n
452 expected_similarities
= {
460 pg
.vertices
.each
do |v
|
461 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
462 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
466 it
'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method C)' do
469 g1v1
= Vertex
.new(:name => :g1v1)
470 g1v2
= Vertex
.new(:name => :g1v2)
471 g1v3
= Vertex
.new(:name => :g1v3)
472 g1
.connect(g1v1
, g1v2
, :type => :t1)
473 g1
.connect(g1v2
, g1v3
, :type => :t2)
474 g2v1
= Vertex
.new(:name => :g2v1)
475 g2v2
= Vertex
.new(:name => :g2v2)
476 g2v3
= Vertex
.new(:name => :g2v3)
477 g2
.connect(g2v1
, g2v2
, :type => :t1)
478 g2
.connect(g2v2
, g2v3
, :type => :t2)
481 pg
.initial_similarity
482 pg
.similarity_flood
do |v
|
483 v
.similarity
= v
.initial_similarity
+ v
.last_similarity
484 edge_groups
= v
.edges
.group_by
{|e
| e
.type
}
485 edge_groups
.each
do |type
, edges
|
488 e
.other_end(v
).similarity
+= (v
.initial_similarity
+ v
.last_similarity
) / n
493 expected_similarities
= {
494 'g1v1:g2v1' => 0.8282781862745098,
496 'g1v2:g2v1' => 0.41421568627450983,
499 'g1v3:g2v2' => 0.41421568627450983,
500 'g1v3:g2v3' => 0.41421568627450983}
501 pg
.vertices
.each
do |v
|
502 name
= "#{v.g1_vertex.name.to_s}:#{v.g2_vertex.name.to_s}"
503 v
.similarity
.should
be_within(0.001).of(expected_similarities
[name
])
506 end # similarity_flood