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.to_s + ';'})
 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       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}"
 144       end
 145
 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}"
 153       end
 154
 155     end # #to_dot
 156
 157     describe 'product' do
 158       it 'finds a product graph of a pair of one-vertex graphs' do
 159         g1 = Graph.new
 160         g2 = Graph.new
 161         g1v1 = Vertex.new
 162         g1 << g1v1
 163         g2v1 = Vertex.new
 164         g2 << g2v1
 165         product = g1.product g2
 166
 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
 171       end
 172
 173       it 'finds a product graph of a pair of simple graphs' do
 174         g1 = Graph.new
 175         g2 = Graph.new
 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)
 182         pg = g1.product g2
 183
 184         pg.should have(4).vertices
 185         pg.should have(2).edges
 186       end
 187
 188       it 'finds a product graph of not-quite-simple graph' do
 189         g1 = Graph.new
 190         g2 = Graph.new
 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)
 201         pg = g1.product g2
 202
 203         pg.should have(9).vertices
 204         pg.should have(8).edges
 205       end
 206
 207       it 'finds a product graph of a simple graph with edge types' do
 208         g1 = Graph.new
 209         g2 = Graph.new
 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)
 220         pg = g1.product g2
 221
 222         pg.should have(7).vertices
 223         pg.should have(4).edges
 224       end
 225
 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'
 228         g1 = Graph.new
 229         g2 = Graph.new
 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)
 242         pg = g1.product g2
 243
 244         pg.should have(4).edges
 245         pg.should have(6).vertices
 246       end
 247     end #product
 248
 249     describe 'initial_similarity' do
 250       before(:each) do
 251         g1 = Graph.new
 252         g2 = Graph.new
 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)
 259         @pg = g1.product g2
 260       end
 261
 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
 264       end
 265
 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)
 271         end
 272       end
 273
 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 )
 279         end
 280
 281       end
 282     end #initial similarity
 283
 284     describe 'similarity flood' do
 285       it 'similarity floods a graph of two nodes' do
 286         g1 = Graph.new
 287         g2 = Graph.new
 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)
 294         pg = g1.product g2
 295
 296         pg.initial_similarity
 297         pg.similarity_flood
 298         pg.vertices.each do |v|
 299           v.similarity.should be_within(0.001).of(1.0)
 300         end
 301       end
 302
 303       it 'similarity floods a graph of three nodes, a -- b -- c' do
 304         g1 = Graph.new
 305         g2 = Graph.new
 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)
 316         pg = g1.product g2
 317
 318         pg.initial_similarity
 319         pg.similarity_flood
 320         expected_similarities = {
 321           'g1v1:g2v1' => 0.5,
 322           'g1v1:g2v2' => 0.6666666666666666,
 323           'g1v2:g2v1' => 0.6666666666666666,
 324           'g1v2:g2v2' => 1.0,
 325           'g1v2:g2v3' => 0.6666666666666666,
 326           'g1v3:g2v2' => 0.6666666666666666,
 327           'g1v3:g2v3' => 0.5}
 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])
 331         end
 332       end
 333
 334       it 'simialrity floods the sample graph from the paper' do
 335         pg = Graph.new
 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
 347         pg.similarity_flood
 348
 349         expected_similarities = {
 350           'a:b' => 1.0,
 351           'a2:b1' => 0.92,
 352           'a1:b2' => 0.71,
 353           'a1:b1' => 0.38,
 354           'a1:b' => 0.0,
 355           'a2:b2' => 0.0}
 356         pg.vertices.each do |v|
 357           v.similarity.should be_within(0.02).of(expected_similarities[v.name])
 358         end
 359       end
 360
 361       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update' do
 362         g1 = Graph.new
 363         g2 = Graph.new
 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)
 374         pg = g1.product g2
 375
 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|
 380             n = edges.length
 381             edges.each do |e|
 382               e.other_end(v).similarity += v.last_similarity / n
 383             end
 384           end
 385           v.similarity
 386         end
 387         expected_similarities = {
 388           'g1v1:g2v1' => 0.5,
 389           'g1v1:g2v2' => 0.6666666666666666,
 390           'g1v2:g2v1' => 0.6666666666666666,
 391           'g1v2:g2v2' => 1.0,
 392           'g1v2:g2v3' => 0.6666666666666666,
 393           'g1v3:g2v2' => 0.6666666666666666,
 394           'g1v3:g2v3' => 0.5}
 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])
 398         end
 399       end
 400
 401       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method A)' do
 402         g1 = Graph.new
 403         g2 = Graph.new
 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)
 414         pg = g1.product g2
 415
 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|
 421             n = edges.length
 422             edges.each do |e|
 423               e.other_end(v).similarity += v.last_similarity / n
 424             end
 425           end
 426           v.similarity
 427         end
 428         expected_similarities = {
 429           'g1v1:g2v1' => 0.9269662921348315,
 430           'g1v1:g2v2' => 1.0,
 431           'g1v2:g2v1' => 0.6179775280898876,
 432           'g1v2:g2v2' => 1.0,
 433           'g1v2:g2v3' => 1.0,
 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])
 439         end
 440       end
 441
 442       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method B)' do
 443         g1 = Graph.new
 444         g2 = Graph.new
 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)
 455         pg = g1.product g2
 456
 457         pg.initial_similarity
 458         pg.similarity_flood do |v|
 459           v.similarity = 0.0
 460           edge_groups = v.edges.group_by {|e| e.type }
 461           edge_groups.each do |type, edges|
 462             n = edges.length
 463             edges.each do |e|
 464               e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
 465             end
 466           end
 467           v.similarity
 468         end
 469         expected_similarities = {
 470           'g1v1:g2v1' => 1.0,
 471           'g1v1:g2v2' => 1.0,
 472           'g1v2:g2v1' => 0.0,
 473           'g1v2:g2v2' => 1.0,
 474           'g1v2:g2v3' => 1.0,
 475           'g1v3:g2v2' => 0.0,
 476           'g1v3:g2v3' => 0.0}
 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])
 480         end
 481       end
 482
 483       it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method C)' do
 484         g1 = Graph.new
 485         g2 = Graph.new
 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)
 496         pg = g1.product g2
 497
 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|
 503             n = edges.length
 504             edges.each do |e|
 505               e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
 506             end
 507           end
 508           v.similarity
 509         end
 510         expected_similarities = {
 511           'g1v1:g2v1' => 0.8282781862745098,
 512           'g1v1:g2v2' => 1.0,
 513           'g1v2:g2v1' => 0.41421568627450983,
 514           'g1v2:g2v2' => 1.0,
 515           'g1v2:g2v3' => 1.0,
 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])
 521         end
 522       end
 523     end # similarity_flood
 524
 525   end
 526 end