From 95b8572d01c0b9c3aa8fc5a1e85a045c33d4ecf1 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 20 Apr 2012 19:15:20 +0100 Subject: [PATCH] End of the day --- lib/graph.njae/edge.rb | 14 ++++ lib/graph.njae/graph.rb | 45 ++++++---- lib/graph.njae/vertex.rb | 8 +- spec/graph/edge_spec.rb | 60 ++++++++++--- spec/graph/graph_spec.rb | 172 ++++++++++++++++++++++++++++++++------ spec/graph/vertex_spec.rb | 14 +++- 6 files changed, 259 insertions(+), 54 deletions(-) diff --git a/lib/graph.njae/edge.rb b/lib/graph.njae/edge.rb index 4a1ba79..f3efc91 100644 --- a/lib/graph.njae/edge.rb +++ b/lib/graph.njae/edge.rb @@ -34,6 +34,20 @@ module GraphNjae def connection_at(vertex) self.connections.find {|c| c.end.equal? vertex} end + + # Return the vertex at the other end of the one given. + # Self-loops should still return the vertex + def other_end(vertex) + if self.vertices[0] == vertex + self.vertices[1] + else + self.vertices[0] + end + end + + def to_s + '' + end end # A connection between an Edge and a Vertex.The connection can have arbitrary attributes, diff --git a/lib/graph.njae/graph.rb b/lib/graph.njae/graph.rb index 011dd86..288fc74 100644 --- a/lib/graph.njae/graph.rb +++ b/lib/graph.njae/graph.rb @@ -26,10 +26,10 @@ module GraphNjae # Connects two vertices, creating and storing a new edge # Also adds the vertices, unless they're already in the graph - def connect(vertex1, vertex2) + def connect(vertex1, vertex2, edge_attributes = {}) self.vertices << vertex1 unless self.vertices.include? vertex1 self.vertices << vertex2 unless self.vertices.include? vertex2 - edge = Edge.new + edge = Edge.new(edge_attributes) self.edges << edge edge << vertex1 << vertex2 end @@ -46,15 +46,18 @@ module GraphNjae self.edges.each do |e1| e1_vertices = e1.vertices other.edges.each do |e2| - e2_vertices = e2.vertices - source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[0]} - destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[1]} - product_graph.connect source, destination - source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[1]} - destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[0]} - product_graph.connect source, destination + if e1.type == e2.type + e2_vertices = e2.vertices + source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[0]} + destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[1]} + product_graph.connect source, destination + source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[1]} + destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[0]} + product_graph.connect source, destination + end end end + product_graph.vertices.reject! {|v| v.neighbours.empty?} product_graph end @@ -78,20 +81,34 @@ module GraphNjae iteration = 1 residual = max_residual + 1 while residual > max_residual and iteration <= max_iterations +# puts "Starting iteration #{iteration}" self.vertices.each do |v| v.last_similarity = v.similarity end self.vertices.each do |v| - n = v.neighbours.length - v.neighbours.each do |neighbour| - neighbour.similarity += v.last_similarity / n - end +# puts "Processing vertex #{v.name}" + edge_groups = v.edges.group_by {|e| e.type } +# puts " Edge groups {#{edge_groups.keys.map {|t| t.to_s + ' => {' + edge_groups[t].map {|e| e.to_s}.join(', ')}.join('; ')}}" + edge_groups.each do |type, edges| +# puts " Processing group type #{type}" + n = edges.length + edges.each do |e| + e.other_end(v).similarity += v.last_similarity / n + end + end end - max_similarity = vertices.max {|v, w| v.similarity <=> w.similarity}.similarity +# self.vertices.each do |v| +# n = v.neighbours.length +# v.neighbours.each do |neighbour| +# neighbour.similarity += v.last_similarity / n +# end +# end + max_similarity = vertices.map {|v| v.similarity}.max self.vertices.each do |v| v.similarity = v.similarity / max_similarity end residual = Math.sqrt(self.vertices.reduce(0) {|a, v| a += (v.similarity - v.last_similarity) ** 2}) +# puts "Residual = #{residual.round(3)}, sims = #{self.vertices.map {|v| v.name + " = " + v.similarity.round(2).to_s}}" iteration += 1 end diff --git a/lib/graph.njae/vertex.rb b/lib/graph.njae/vertex.rb index aeabe30..6e46dcb 100644 --- a/lib/graph.njae/vertex.rb +++ b/lib/graph.njae/vertex.rb @@ -14,8 +14,8 @@ module GraphNjae # Connect this vertex to another, creating an Edge to do so, and returning # the Edge - def connect(other) - e = Edge.new + def connect(other, edge_attributes = {}) + e = Edge.new edge_attributes e << self << other # self.edges << e # other.edges << e unless self === other @@ -39,5 +39,9 @@ module GraphNjae e.vertices.drop_while {|v| v != self}[1..-1]}.flatten end + def to_s + '' + end + end end diff --git a/spec/graph/edge_spec.rb b/spec/graph/edge_spec.rb index 8373864..8fc71ba 100644 --- a/spec/graph/edge_spec.rb +++ b/spec/graph/edge_spec.rb @@ -16,7 +16,6 @@ module GraphNjae e.value3.should == :v3 e.value4.should be_nil end - end # #initialize describe "adds attribues" do @@ -29,8 +28,8 @@ module GraphNjae describe "#<<" do it "adds a new vertex to an edge (with a connection)" do e.connections.should be_empty - v1 = Vertex.new - v2 = Vertex.new + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 e << v1 e.should have(1).connections e.should have(1).vertices @@ -46,8 +45,8 @@ module GraphNjae it "adds several vertices to an edge" do e.connections.should be_empty - v1 = Vertex.new - v2 = Vertex.new + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 e << v1 << v2 e.vertices.should include(v1) e.vertices.should include(v2) @@ -67,8 +66,8 @@ module GraphNjae describe "connection_at" do it "returns the connection that links to a vertex" do e.connections.should be_empty - v1 = Vertex.new - v2 = Vertex.new + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 e << v1 << v2 e.connection_at(v1).end.should be v1 @@ -77,9 +76,9 @@ module GraphNjae it "returns nil if there is no connection to that vertex" do e.connections.should be_empty - v1 = Vertex.new - v2 = Vertex.new - v3 = Vertex.new + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 + v3 = Vertex.new :name => :v3 e << v1 << v2 e.connection_at(v3).should be nil @@ -87,14 +86,49 @@ module GraphNjae it "returns the vertex for a self-loop" do e.connections.should be_empty - v1 = Vertex.new + v1 = Vertex.new :name => :v1 e << v1 << v1 e.connection_at(v1).end.should be v1 end - - end # #connection_at + + describe "other_end" do + it "returns the vertex at the other end of the given one" do + e.connections.should be_empty + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 + e << v1 << v2 + + e.other_end(v1).should be v2 + e.other_end(v2).should be v1 + end + + it "returns the same vertex in a self-loop" do + e.connections.should be_empty + v1 = Vertex.new :name => :v1 + e << v1 << v1 + + e.other_end(v1).should be v1 + end + + it "returns one of the connected edges if given a vertex not connected to it" do + e.connections.should be_empty + v1 = Vertex.new :name => :v1 + v2 = Vertex.new :name => :v2 + v3 = Vertex.new :name => :v3 + e << v1 << v2 + + [v1, v2].should include e.other_end(v3) + end + + it "returns nil if it can't return something sensible" do + v1 = Vertex.new :name => :v1 + e.other_end(v1).should be_nil + e << v1 + e.other_end(v1).should be_nil + end + end # other_end end # Edge describe Connection do diff --git a/spec/graph/graph_spec.rb b/spec/graph/graph_spec.rb index 8339946..cd143b1 100644 --- a/spec/graph/graph_spec.rb +++ b/spec/graph/graph_spec.rb @@ -27,7 +27,7 @@ module GraphNjae end # #initialize - describe "adds attribues" do + describe "adds attributes" do it "adds then reports arbitrary attributes" do g.score = 15 g.score.should == 15 @@ -95,6 +95,20 @@ module GraphNjae 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 "product" do @@ -107,9 +121,9 @@ module GraphNjae g2 << g2v1 product = g1.product g2 - product.should have(1).vertices - product.vertices.first.g1_vertex.should == g1v1 - product.vertices.first.g2_vertex.should == g2v1 + 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 @@ -129,9 +143,67 @@ module GraphNjae 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 + + end #product describe "initial_similarity" do before(:each) do @@ -166,33 +238,85 @@ module GraphNjae end 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 + 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 + 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 + 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 a sample graph" do + 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 + end # similarity_flood end end diff --git a/spec/graph/vertex_spec.rb b/spec/graph/vertex_spec.rb index b193bc8..e091289 100644 --- a/spec/graph/vertex_spec.rb +++ b/spec/graph/vertex_spec.rb @@ -85,9 +85,16 @@ module GraphNjae e.vertices.should include(v) e.vertices.should include(v1) - e.should have(2).connections + e.should have(2).connections end + it "connects two vertices by an edge with attributes" do + v1 = Vertex.new + v1.id = :v1 + e = v.connect(v1, {:type => :edge_type}) + e.type.should == :edge_type + end + it "creates a self-connection" do e = v.connect v @@ -104,6 +111,11 @@ module GraphNjae e.should have(2).connections end + it "creates a self-connection with an edge with attributes" do + e = v.connect(v, {:type => :edge_type}) + e.type.should == :edge_type + end + end # #connect describe "#neighbours" do -- 2.34.1