spec/graph/graph_spec.rb

   1 require File.expand_path(File.dirname(__FILE__) + '/../spec_helper')
   2
   3 module GraphNjae
   4
   5   class SVertex < Vertex
   6   end
   7
   8   class SEdge < Edge
   9   end
  10
  11   describe Graph do
  12     let (:g) { Graph.new }
  13     describe '#initialize' do
  14       it 'creates an empty graph' do
  15         g = Graph.new
  16         g.edges.should be_empty
  17         g.vertices.should be_empty
  18       end
  19
  20       it 'creates a graph with some parameters' do
  21         g = Graph.new :value1 => 1, :value2 => 'value2', :value3 => :v3
  22         g.value1.should == 1
  23         g.value2.should == 'value2'
  24         g.value3.should == :v3
  25         g.value4.should be_nil
  26       end
  27
  28     end # #initialize
  29
  30     describe 'adds attributes' do
  31       it 'adds then reports arbitrary attributes' do
  32         g.score = 15
  33         g.score.should == 15
  34       end
  35     end # adds attributes
  36
  37     describe '#<<' do
  38       it 'adds a set of vertices' do
  39         g.vertices.should be_empty
  40         v1 = Vertex.new
  41         v2 = Vertex.new
  42         g << v1 << v2
  43         g.should have(2).vertices
  44         g.vertices.should include(v1)
  45         g.vertices.should include(v2)
  46       end
  47
  48       it 'adds a set of edges' do
  49         g.edges.should be_empty
  50         e1 = Edge.new
  51         e2 = Edge.new
  52         g << e1 << e2
  53         g.should have(2).edges
  54         g.edges.should include(e1)
  55         g.edges.should include(e2)
  56       end
  57
  58       it 'adds a mixed set of vertices and edges' do
  59         g.vertices.should be_empty
  60         g.edges.should be_empty
  61         v1 = Vertex.new
  62         v2 = Vertex.new
  63         e1 = Edge.new
  64         e2 = Edge.new
  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)
  72       end
  73
  74       it 'adds a subclass of Vertex' do
  75         g.vertices.should be_empty
  76         v1 = SVertex.new
  77         v2 = SVertex.new
  78         g << v1 << v2
  79         g.should have(2).vertices
  80         g.vertices.should include(v1)
  81         g.vertices.should include(v2)
  82       end
  83     end # #<<
  84
  85     describe 'connect' do
  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)
  91         g.connect(v1, v2)
  92
  93         g.should have(2).vertices
  94         g.vertices.should include(v1)
  95         g.vertices.should include(v2)
  96         g.should have(1).edges
  97       end
  98
  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)
 105
 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
 111       end
 112     end # #connect
 113
 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}"
 120       end
 121
 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}"
 128       end
 129
 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}"
 136       end
 137
 138     end # #to_dot
 139
 140     describe 'product' do
 141       it 'finds a product graph of a pair of one-vertex graphs' do
 142         g1 = Graph.new
 143         g2 = Graph.new
 144         g1v1 = Vertex.new
 145         g1 << g1v1
 146         g2v1 = Vertex.new
 147         g2 << g2v1
 148         product = g1.product g2
 149
 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
 154       end
 155
 156       it 'finds a product graph of a pair of simple graphs' do
 157         g1 = Graph.new
 158         g2 = Graph.new
 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)
 165         pg = g1.product g2
 166
 167         pg.should have(4).vertices
 168         pg.should have(2).edges
 169       end
 170
 171       it 'finds a product graph of not-quite-simple graph' do
 172         g1 = Graph.new
 173         g2 = Graph.new
 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)
 184         pg = g1.product g2
 185
 186         pg.should have(9).vertices
 187         pg.should have(8).edges
 188       end
 189
 190       it 'finds a product graph of a simple graph with edge types' do
 191         g1 = Graph.new
 192         g2 = Graph.new
 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)
 203         pg = g1.product g2
 204
 205         pg.should have(7).vertices
 206         pg.should have(4).edges
 207       end
 208
 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'
 211         g1 = Graph.new
 212         g2 = Graph.new
 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)
 225         pg = g1.product g2
 226
 227         pg.should have(4).edges
 228         pg.should have(6).vertices
 229       end
 230     end #product
 231
 232     describe 'initial_similarity' do
 233       before(:each) do
 234         g1 = Graph.new
 235         g2 = Graph.new
 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)
 242         @pg = g1.product g2
 243       end
 244
 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
 247       end
 248
 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)
 254         end
 255       end
 256
 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 )
 262         end
 263
 264       end
 265     end #initial similarity
 266
 267     describe 'similarity flood' do
 268       it 'similarity floods a graph of two nodes' do
 269         g1 = Graph.new
 270         g2 = Graph.new
 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)
 277         pg = g1.product g2
 278
 279         pg.initial_similarity
 280         pg.similarity_flood
 281         pg.vertices.each do |v|
 282           v.similarity.should be_within(0.001).of(1.0)
 283         end
 284       end
 285
 286       it 'similarity floods a graph of three nodes, a -- b -- c' do
 287         g1 = Graph.new
 288         g2 = Graph.new
 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)
 299         pg = g1.product g2
 300
 301         pg.initial_similarity
 302         pg.similarity_flood
 303         expected_similarities = {
 304           'g1v1:g2v1' => 0.5,
 305           'g1v1:g2v2' => 0.6666666666666666,
 306           'g1v2:g2v1' => 0.6666666666666666,
 307           'g1v2:g2v2' => 1.0,
 308           'g1v2:g2v3' => 0.6666666666666666,
 309           'g1v3:g2v2' => 0.6666666666666666,
 310           'g1v3:g2v3' => 0.5}
 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])
 314         end
 315       end
 316
 317       it 'simialrity floods the sample graph from the paper' do
 318         pg = Graph.new
 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
 330         pg.similarity_flood
 331
 332         expected_similarities = {
 333           'a:b' => 1.0,
 334           'a2:b1' => 0.92,
 335           'a1:b2' => 0.71,
 336           'a1:b1' => 0.38,
 337           'a1:b' => 0.0,
 338           'a2:b2' => 0.0}
 339         pg.vertices.each do |v|
 340           v.similarity.should be_within(0.02).of(expected_similarities[v.name])
 341         end
 342       end
 343
 344       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update' do
 345         g1 = Graph.new
 346         g2 = Graph.new
 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)
 357         pg = g1.product g2
 358
 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|
 363             n = edges.length
 364             edges.each do |e|
 365               e.other_end(v).similarity += v.last_similarity / n
 366             end
 367           end
 368           v.similarity
 369         end
 370         expected_similarities = {
 371           'g1v1:g2v1' => 0.5,
 372           'g1v1:g2v2' => 0.6666666666666666,
 373           'g1v2:g2v1' => 0.6666666666666666,
 374           'g1v2:g2v2' => 1.0,
 375           'g1v2:g2v3' => 0.6666666666666666,
 376           'g1v3:g2v2' => 0.6666666666666666,
 377           'g1v3:g2v3' => 0.5}
 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])
 381         end
 382       end
 383
 384       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method A)' do
 385         g1 = Graph.new
 386         g2 = Graph.new
 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)
 397         pg = g1.product g2
 398
 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|
 404             n = edges.length
 405             edges.each do |e|
 406               e.other_end(v).similarity += v.last_similarity / n
 407             end
 408           end
 409           v.similarity
 410         end
 411         expected_similarities = {
 412           'g1v1:g2v1' => 0.9269662921348315,
 413           'g1v1:g2v2' => 1.0,
 414           'g1v2:g2v1' => 0.6179775280898876,
 415           'g1v2:g2v2' => 1.0,
 416           'g1v2:g2v3' => 1.0,
 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])
 422         end
 423       end
 424
 425       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method B)' do
 426         g1 = Graph.new
 427         g2 = Graph.new
 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)
 438         pg = g1.product g2
 439
 440         pg.initial_similarity
 441         pg.similarity_flood do |v|
 442           v.similarity = 0.0
 443           edge_groups = v.edges.group_by {|e| e.type }
 444           edge_groups.each do |type, edges|
 445             n = edges.length
 446             edges.each do |e|
 447               e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
 448             end
 449           end
 450           v.similarity
 451         end
 452         expected_similarities = {
 453           'g1v1:g2v1' => 1.0,
 454           'g1v1:g2v2' => 1.0,
 455           'g1v2:g2v1' => 0.0,
 456           'g1v2:g2v2' => 1.0,
 457           'g1v2:g2v3' => 1.0,
 458           'g1v3:g2v2' => 0.0,
 459           'g1v3:g2v3' => 0.0}
 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])
 463         end
 464       end
 465
 466       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method C)' do
 467         g1 = Graph.new
 468         g2 = Graph.new
 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)
 479         pg = g1.product g2
 480
 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|
 486             n = edges.length
 487             edges.each do |e|
 488               e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
 489             end
 490           end
 491           v.similarity
 492         end
 493         expected_similarities = {
 494           'g1v1:g2v1' => 0.8282781862745098,
 495           'g1v1:g2v2' => 1.0,
 496           'g1v2:g2v1' => 0.41421568627450983,
 497           'g1v2:g2v2' => 1.0,
 498           'g1v2:g2v3' => 1.0,
 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])
 504         end
 505       end
 506     end # similarity_flood
 507
 508   end
 509 end