X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=lib%2Fgraph.njae%2Fgraph.rb;h=011dd8625720dd601cd4868257ae7224273fb133;hb=32518a2c5089dbd3b9f74aad780ded127e3040ea;hp=acfc9e07e998ee3843aa19e990f7670d38a8bcce;hpb=e3fe1f33fea019106289edfae4e7a32f3ba3e03b;p=graph.njae.git

diff --git a/lib/graph.njae/graph.rb b/lib/graph.njae/graph.rb
index acfc9e0..011dd86 100644
--- a/lib/graph.njae/graph.rb
+++ b/lib/graph.njae/graph.rb
@@ -35,7 +35,7 @@ module GraphNjae
     end
     
     # Form a product graph of this graph and the other.
-    # Return the new graph.
+    # Return the product graph.
     def product(other)
       product_graph = Graph.new
       self.vertices.each do |v1|
@@ -58,5 +58,44 @@ module GraphNjae
       product_graph
     end
     
+    
+    def initial_similarity
+      self.vertices.each do |v|
+        if block_given?
+          v.initial_similarity = yield v
+        else
+          v.initial_similarity = 1.0
+        end
+        v.similarity = v.initial_similarity
+      end
+    end
+    
+    # Performs similarity flooding on a graph
+    # Assumes that the initial similarity has already been calculated
+    def similarity_flood(opts = {})
+      max_iterations = opts[:iterations] || 100
+      max_residual = opts[:max_residual] || 0.001
+      iteration = 1
+      residual = max_residual + 1
+      while residual > max_residual and iteration <= max_iterations
+        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
+        end
+        max_similarity = vertices.max {|v, w| v.similarity <=> w.similarity}.similarity
+        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})
+        iteration += 1
+      end
+      
+    end
+    
   end # class
 end