Version bump to 0.4.0

[graph.njae.git] / lib / graph.njae / graph.rb

diff --git a/lib/graph.njae/graph.rb b/lib/graph.njae/graph.rb
index 3029cebd6c403d69d97aa9bf465d50c176d4af56..eb2ddc6e3e55b296720e400cba6aea87296f38a5 100644 (file)
--- a/lib/graph.njae/graph.rb
+++ b/lib/graph.njae/graph.rb
@@ -1,5 +1,3 @@
-require 'ostruct'
-
 require 'logger'
 $log = Logger.new(STDERR)
 $log.level = Logger::WARN
@@ -38,6 +36,31 @@ module GraphNjae
       edge << vertex1 << vertex2
     end
     
+    def to_dot(opts = {})
+      vertex_args = opts[:vertex_args] || {}
+      vertex_block = opts[:vertex_block] || nil
+      edge_args = opts[:edge_args] || {}
+      edge_block = opts[:edge_block] || nil
+      dot = "graph {\n"
+      self.vertices.each do |v|
+        if vertex_block.nil?
+          dot << v.to_dot(vertex_args)
+        else
+          dot << v.to_dot(&vertex_block)
+        end
+        dot << "\n"
+      end
+      self.edges.each do |e|
+        if edge_block.nil?
+          dot << e.to_dot(edge_args)
+        else
+          dot << e.to_dot(&edge_block)
+        end
+        dot << "\n"
+      end
+      dot << '}'
+    end
+    
     # Form a product graph of this graph and the other.
     # Return the product graph.
     def product(other)
@@ -66,6 +89,10 @@ module GraphNjae
     end
     
     
+    # Calculates the initial similarity of each vertex in a product graph.
+    # If passed an optional block, that block is used to find the 
+    # initial similarity. If no block is given, every vertex is given
+    # an initial similarity of 1.0.
     def initial_similarity
       self.vertices.each do |v|
         if block_given?
@@ -77,8 +104,16 @@ module GraphNjae
       end
     end
     
-    # Performs similarity flooding on a graph
+    # Performs similarity flooding on a graph, as described by 
+    # Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm, 
+    # "Similarity Flooding: A Versatile Graph Matching Algorithm 
+    #    and its Application to Schema Matching", Proceedings of 
+    # the 18th International Conference on Data Engineering (ICDE’02)
+    #
     # Assumes that the initial similarity has already been calculated
+    # If passed an optional block, it uses that block to update the 
+    # similarity on each iteration. If no block is passed, it uses the 
+    # default similarity updating method from the paper.
     def similarity_flood(opts = {})
       max_iterations = opts[:iterations] || 100
       max_residual = opts[:max_residual] || 0.001
@@ -105,12 +140,6 @@ module GraphNjae
             end
           end
         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.map {|v| v.similarity}.max
         self.vertices.each do |v|
           v.similarity = v.similarity / max_similarity