+ it "should give all nodes an initial similarity of 1 if no block is given" do
+ @pg.initial_similarity
+ @pg.vertices.each do |v|
+ v.initial_similarity.should be_within(0.001).of(1.0)
+ v.similarity.should be_within(0.001).of(1.0)
+ end
+ end
+
+ it "should give all nodes the similarity as defined by the given block" do
+ @pg.initial_similarity {|v| simple_name_similarity v.g1_vertex.name, v.g2_vertex.name}
+ @pg.vertices.each do |v|
+ v.initial_similarity.should be_within(0.001).of( simple_name_similarity v.g1_vertex.name, v.g2_vertex.name )
+ v.similarity.should be_within(0.001).of( simple_name_similarity v.g1_vertex.name, v.g2_vertex.name )
+ end
+
+ end
+ end #initial similarity
+
+ describe "similarity flood" do
+ it "similarity floods a graph of two nodes" do
+ g1 = Graph.new
+ g2 = Graph.new
+ g1v1 = Vertex.new(:name => :g1v1)
+ g1v2 = Vertex.new(:name => :g1v2)
+ g1.connect(g1v1, g1v2)
+ g2v1 = Vertex.new(:name => :g2v1)
+ g2v2 = Vertex.new(:name => :g2v2)
+ g2.connect(g2v1, g2v2)
+ pg = g1.product g2
+
+ pg.initial_similarity
+ pg.similarity_flood
+ pg.vertices.each do |v|
+ v.similarity.should be_within(0.001).of(1.0)
+ end
+ end
+
+ it "similarity floods a graph of three nodes, a -- b -- c" do
+ g1 = Graph.new
+ g2 = Graph.new
+ g1v1 = Vertex.new(:name => :g1v1)
+ g1v2 = Vertex.new(:name => :g1v2)
+ g1v3 = Vertex.new(:name => :g1v3)
+ g1.connect(g1v1, g1v2, :type => :t1)
+ g1.connect(g1v2, g1v3, :type => :t2)
+ g2v1 = Vertex.new(:name => :g2v1)
+ g2v2 = Vertex.new(:name => :g2v2)
+ g2v3 = Vertex.new(:name => :g2v3)
+ g2.connect(g2v1, g2v2, :type => :t1)
+ g2.connect(g2v2, g2v3, :type => :t2)
+ pg = g1.product g2
+
+ pg.initial_similarity
+ pg.similarity_flood
+ expected_similarities = {
+ "g1v1:g2v1" => 0.5,
+ "g1v1:g2v2" => 0.6666666666666666,
+ "g1v2:g2v1" => 0.6666666666666666,
+ "g1v2:g2v2" => 1.0,
+ "g1v2:g2v3" => 0.6666666666666666,
+ "g1v3:g2v2" => 0.6666666666666666,
+ "g1v3:g2v3" => 0.5}
+ pg.vertices.each do |v|
+ name = v.g1_vertex.name.to_s + ':' + v.g2_vertex.name.to_s
+ v.similarity.should be_within(0.001).of(expected_similarities[name])
+ end
+ end
+
+ it "simialrity floods the sample graph from the paper" do
+ pg = Graph.new
+ ab = Vertex.new(:name => "a:b")
+ a1b1 = Vertex.new(:name => "a1:b1")
+ a2b1 = Vertex.new(:name => "a2:b1")
+ a1b2 = Vertex.new(:name => "a1:b2")
+ a1b = Vertex.new(:name => "a1:b")
+ a2b2 = Vertex.new(:name => "a2:b2")
+ pg.connect(ab, a1b1, :type => :l1)
+ pg.connect(ab, a2b1, :type => :l1)
+ pg.connect(a2b1, a1b2, :type => :l2)
+ pg.connect(a1b, a2b2, :type => :l2)
+ pg.initial_similarity
+ pg.similarity_flood
+
+ expected_similarities = {
+ "a:b" => 1.0,
+ "a2:b1" => 0.92,
+ "a1:b2" => 0.71,
+ "a1:b1" => 0.38,
+ "a1:b" => 0.0,
+ "a2:b2" => 0.0}
+ pg.vertices.each do |v|
+ v.similarity.should be_within(0.02).of(expected_similarities[v.name])
+ end
+ end
+ end # similarity_flood