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 "product" do
 115       it "finds a product graph of a pair of one-vertex graphs" do
 116         g1 = Graph.new
 117         g2 = Graph.new
 118         g1v1 = Vertex.new
 119         g1 << g1v1
 120         g2v1 = Vertex.new
 121         g2 << g2v1
 122         product = g1.product g2
 123
 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
 128       end
 129
 130       it "finds a product graph of a pair of simple graphs" do
 131         g1 = Graph.new
 132         g2 = Graph.new
 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)
 139         pg = g1.product g2
 140
 141         pg.should have(4).vertices
 142         pg.should have(2).edges
 143       end
 144
 145       it "finds a product graph of not-quite-simple graph" do
 146         g1 = Graph.new
 147         g2 = Graph.new
 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)
 158         pg = g1.product g2
 159
 160         pg.should have(9).vertices
 161         pg.should have(8).edges
 162       end
 163
 164       it "finds a product graph of a simple graph with edge types" do
 165         g1 = Graph.new
 166         g2 = Graph.new
 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)
 177         pg = g1.product g2
 178
 179         pg.should have(7).vertices
 180         pg.should have(4).edges
 181       end
 182
 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"
 185         g1 = Graph.new
 186         g2 = Graph.new
 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)
 199         pg = g1.product g2
 200
 201         pg.should have(4).edges
 202         pg.should have(6).vertices
 203       end
 204
 205
 206     end #product
 207
 208     describe "initial_similarity" do
 209       before(:each) do
 210         g1 = Graph.new
 211         g2 = Graph.new
 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)
 218         @pg = g1.product g2
 219       end
 220
 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
 223       end
 224
 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)
 230         end
 231       end
 232
 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 )
 238         end
 239
 240       end
 241     end #initial similarity
 242
 243     describe "similarity flood" do
 244       it "similarity floods a graph of two nodes" do
 245         g1 = Graph.new
 246         g2 = Graph.new
 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)
 253         pg = g1.product g2
 254
 255         pg.initial_similarity
 256         pg.similarity_flood
 257         pg.vertices.each do |v|
 258           v.similarity.should be_within(0.001).of(1.0)
 259         end
 260       end
 261
 262       it "similarity floods a graph of three nodes, a -- b -- c" do
 263         g1 = Graph.new
 264         g2 = Graph.new
 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)
 275         pg = g1.product g2
 276
 277         pg.initial_similarity
 278         pg.similarity_flood
 279         expected_similarities = {
 280           "g1v1:g2v1" => 0.5,
 281           "g1v1:g2v2" => 0.6666666666666666,
 282           "g1v2:g2v1" => 0.6666666666666666,
 283           "g1v2:g2v2" => 1.0,
 284           "g1v2:g2v3" => 0.6666666666666666,
 285           "g1v3:g2v2" => 0.6666666666666666,
 286           "g1v3:g2v3" => 0.5}
 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])
 290         end
 291       end
 292
 293       it "simialrity floods the sample graph from the paper" do
 294         pg = Graph.new
 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
 306         pg.similarity_flood
 307
 308         expected_similarities = {
 309           "a:b" => 1.0,
 310           "a2:b1" => 0.92,
 311           "a1:b2" => 0.71,
 312           "a1:b1" => 0.38,
 313           "a1:b" => 0.0,
 314           "a2:b2" => 0.0}
 315         pg.vertices.each do |v|
 316           v.similarity.should be_within(0.02).of(expected_similarities[v.name])
 317         end
 318       end
 319     end # similarity_flood
 320
 321   end
 322 end