X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=spec%2Fgraph%2Fgraph_spec.rb;h=88724a472066b9c8d5f656a35adc58df3000f08e;hb=1bd42608db15715f695d7dbaa95e6bf9429bcc2b;hp=d92562e139e46401ad19116f417fb41ed2f23e7a;hpb=c065008f95cd701f151e8f991caa3fb5dd019049;p=graph.njae.git

diff --git a/spec/graph/graph_spec.rb b/spec/graph/graph_spec.rb
index d92562e..88724a4 100644
--- a/spec/graph/graph_spec.rb
+++ b/spec/graph/graph_spec.rb
@@ -10,23 +10,32 @@ module GraphNjae
   
   describe Graph do
     let (:g) { Graph.new }
-    describe "#initialize" do
-      it "creates an empty graph" do
+    describe '#initialize' do
+      it 'creates an empty graph' do
         g = Graph.new
         g.edges.should be_empty
         g.vertices.should be_empty
       end
+      
+      it 'creates a graph with some parameters' do
+        g = Graph.new :value1 => 1, :value2 => 'value2', :value3 => :v3
+        g.value1.should == 1
+        g.value2.should == 'value2'
+        g.value3.should == :v3
+        g.value4.should be_nil
+      end
+
     end # #initialize
       
-    describe "adds attribues" do
-      it "adds then reports arbitrary attributes" do
+    describe 'adds attributes' do
+      it 'adds then reports arbitrary attributes' do
         g.score = 15
         g.score.should == 15
       end
     end # adds attributes
     
-    describe "#<<" do
-      it "adds a set of vertices" do
+    describe '#<<' do
+      it 'adds a set of vertices' do
         g.vertices.should be_empty
         v1 = Vertex.new
         v2 = Vertex.new
@@ -36,7 +45,7 @@ module GraphNjae
         g.vertices.should include(v2)
       end
       
-      it "adds a set of edges" do
+      it 'adds a set of edges' do
         g.edges.should be_empty
         e1 = Edge.new
         e2 = Edge.new
@@ -46,7 +55,7 @@ module GraphNjae
         g.edges.should include(e2)
       end
       
-      it "adds a mixed set of vertices and edges" do
+      it 'adds a mixed set of vertices and edges' do
         g.vertices.should be_empty
         g.edges.should be_empty
         v1 = Vertex.new
@@ -62,7 +71,7 @@ module GraphNjae
         g.edges.should include(e2)
       end
       
-      it "adds a subclass of Vertex" do
+      it 'adds a subclass of Vertex' do
         g.vertices.should be_empty
         v1 = SVertex.new
         v2 = SVertex.new
@@ -73,10 +82,445 @@ module GraphNjae
       end
     end # #<<
 
-    describe "connect" do
-      it "adds and records an edge between vertices" do
+    describe 'connect' do
+      it 'adds and records an edge between vertices' do
+        g.vertices.should be_empty
+        g.edges.should be_empty
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2)
+        
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+        g.should have(1).edges
+      end
+      
+      it 'adds and records an edge with attributes between vertices' do
+        g.vertices.should be_empty
+        g.edges.should be_empty
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        
+        g.should have(2).vertices
+        g.vertices.should include(v1)
+        g.vertices.should include(v2)
+        g.should have(1).edges
+        g.edges[0].type.should == :edge_type
       end
     end # #connect
     
+    describe '#to_dot' do
+      it 'gives the dot notation of a simple graph' do
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        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}"
+      end
+      
+      it "gives the dot notation of a simple graph, with vertex attributes" do
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        gdot = g.to_dot(:vertex_args => {:label => :name})
+        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}"
+      end
+
+      it "gives the dot notation of a simple graph, with vertices generated by a block" do
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        gdot = g.to_dot(:vertex_block => lambda {|v| v.name.to_s + ';'})
+        gdot.should == "graph {\n#{v1.name};\n#{v2.name};\n#{v1.object_id.to_s} -- #{v2.object_id.to_s};\n}"
+      end
+
+      it "gives the dot notation of a simple graph, with vertex and edge attributes" do
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        gdot = g.to_dot(:edge_args => {:label => :type}, :vertex_args => {:label => :name})
+        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}"
+      end
+
+      it "gives the dot notation of a simple graph, with vertices and edges generated by a block" do
+        v1 = Vertex.new(:name => :v1)
+        v2 = Vertex.new(:name => :v2)
+        g.connect(v1, v2, :type => :edge_type)
+        gdot = g.to_dot(:vertex_block => lambda {|v| v.name.to_s + ';'}, 
+                        :edge_block => lambda {|e| "#{e.vertices[0].name.to_s} -- #{e.vertices[1].name.to_s} {label = \"#{e.type.to_s}\"};"})
+        gdot.should == "graph {\n#{v1.name};\n#{v2.name};\n#{v1.name} -- #{v2.name} {label = \"#{g.edges[0].type}\"};\n}"
+      end
+      
+    end # #to_dot
+    
+    describe 'product' do
+      it 'finds a product graph of a pair of one-vertex graphs' do
+        g1 = Graph.new
+        g2 = Graph.new
+        g1v1 = Vertex.new
+        g1 << g1v1
+        g2v1 = Vertex.new
+        g2 << g2v1
+        product = g1.product g2
+        
+        product.vertices.should be_empty
+        #product.vertices.first.g1_vertex.should == g1v1
+        #product.vertices.first.g2_vertex.should == g2v1
+        product.edges.should be_empty
+      end
+
+      it 'finds a product graph of a pair of simple graphs' 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.should have(4).vertices
+        pg.should have(2).edges
+      end
+      
+      it 'finds a product graph of not-quite-simple graph' 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)
+        g1.connect(g1v2, g1v3)
+        g2v1 = Vertex.new(:name => :g2v1)
+        g2v2 = Vertex.new(:name => :g2v2)
+        g2v3 = Vertex.new(:name => :g2v3)
+        g2.connect(g2v1, g2v2)
+        g2.connect(g2v2, g2v3)
+        pg = g1.product g2
+        
+        pg.should have(9).vertices
+        pg.should have(8).edges
+      end
+
+      it 'finds a product graph of a simple graph with edge types' 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.should have(7).vertices
+        pg.should have(4).edges
+      end
+
+      it 'finds a product graph of the example graph from paper' do
+        pending 'implementation of directed graphs as operands of the product graph'
+        g1 = Graph.new
+        g2 = Graph.new
+        a = Vertex.new(:name => :a)
+        a1 = Vertex.new(:name => :a1)
+        a2 = Vertex.new(:name => :a2)
+        g1.connect(a, a1, :type => :l1)
+        g1.connect(a, a2, :type => :l1)
+        g1.connect(a1, a2, :type => :l2)
+        b = Vertex.new(:name => :b)
+        b1 = Vertex.new(:name => :b1)
+        b2 = Vertex.new(:name => :b2)
+        g2.connect(b, b1, :type => :l1)
+        g2.connect(b, b2, :type => :l2)
+        g2.connect(b1, b2, :type => :l2)
+        pg = g1.product g2
+
+        pg.should have(4).edges
+        pg.should have(6).vertices
+      end
+    end #product
+    
+    describe 'initial_similarity' do
+      before(:each) 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
+      end
+      
+      def simple_name_similarity(n1, n2)
+        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
+      end
+
+      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
+      
+      it 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs the default update' 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 do |v|
+          edge_groups = v.edges.group_by {|e| e.type }
+          edge_groups.each do |type, edges|
+            n = edges.length
+            edges.each do |e|
+              e.other_end(v).similarity += v.last_similarity / n
+            end
+          end
+          v.similarity
+        end
+        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 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method A)' 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 do |v|
+          v.similarity = v.initial_similarity
+          edge_groups = v.edges.group_by {|e| e.type }
+          edge_groups.each do |type, edges|
+            n = edges.length
+            edges.each do |e|
+              e.other_end(v).similarity += v.last_similarity / n
+            end
+          end
+          v.similarity
+        end
+        expected_similarities = {
+          'g1v1:g2v1' => 0.9269662921348315,
+          'g1v1:g2v2' => 1.0,
+          'g1v2:g2v1' => 0.6179775280898876,
+          'g1v2:g2v2' => 1.0,
+          'g1v2:g2v3' => 1.0,
+          'g1v3:g2v2' => 0.6179775280898876,
+          'g1v3:g2v3' => 0.6179775280898876}
+        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 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method B)' 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 do |v|
+          v.similarity = 0.0
+          edge_groups = v.edges.group_by {|e| e.type }
+          edge_groups.each do |type, edges|
+            n = edges.length
+            edges.each do |e|
+              e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
+            end
+          end
+          v.similarity
+        end
+        expected_similarities = {
+          'g1v1:g2v1' => 1.0,
+          'g1v1:g2v2' => 1.0,
+          'g1v2:g2v1' => 0.0,
+          'g1v2:g2v2' => 1.0,
+          'g1v2:g2v3' => 1.0,
+          'g1v3:g2v2' => 0.0,
+          'g1v3:g2v3' => 0.0}
+        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 'similarity floods a graph of three nodes, a -- b -- c, given a block that performs a different update (method 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 do |v|
+          v.similarity = v.initial_similarity + v.last_similarity
+          edge_groups = v.edges.group_by {|e| e.type }
+          edge_groups.each do |type, edges|
+            n = edges.length
+            edges.each do |e|
+              e.other_end(v).similarity += (v.initial_similarity + v.last_similarity) / n
+            end
+          end
+          v.similarity
+        end
+        expected_similarities = {
+          'g1v1:g2v1' => 0.8282781862745098,
+          'g1v1:g2v2' => 1.0,
+          'g1v2:g2v1' => 0.41421568627450983,
+          'g1v2:g2v2' => 1.0,
+          'g1v2:g2v3' => 1.0,
+          'g1v3:g2v2' => 0.41421568627450983,
+          'g1v3:g2v3' => 0.41421568627450983}
+        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
+    end # similarity_flood
+    
   end
 end