lib/graph.njae/graph.rb

   1 require 'ostruct'
   2
   3 # A simple graph library
   4
   5 module GraphNjae
   6
   7   # A container for all the parts of a graph.  The graph can have arbitrary attributes,
   8   # treated as method names.
   9   class Graph < OpenStruct
  10     def initialize(values = {})
  11       super(values)
  12       self.edges = Array.new
  13       self.vertices = Array.new
  14       self
  15     end
  16
  17     # Add a Vertex or Edge to the graph.
  18     def <<(other)
  19       if other.class.ancestors.include? Vertex
  20         self.vertices << other
  21       elsif other.class.ancestors.include? Edge
  22         self.edges << other
  23       end
  24       self
  25     end
  26
  27     # Connects two vertices, creating and storing a new edge
  28     # Also adds the vertices, unless they're already in the graph
  29     def connect(vertex1, vertex2, edge_attributes = {})
  30       self.vertices << vertex1 unless self.vertices.include? vertex1
  31       self.vertices << vertex2 unless self.vertices.include? vertex2
  32       edge = Edge.new(edge_attributes)
  33       self.edges << edge
  34       edge << vertex1 << vertex2
  35     end
  36
  37     # Form a product graph of this graph and the other.
  38     # Return the product graph.
  39     def product(other)
  40       product_graph = Graph.new
  41       self.vertices.each do |v1|
  42         other.vertices.each do |v2|
  43           product_graph << Vertex.new({:g1_vertex => v1, :g2_vertex => v2})
  44         end
  45       end
  46       self.edges.each do |e1|
  47         e1_vertices = e1.vertices
  48         other.edges.each do |e2|
  49           if e1.type == e2.type
  50             e2_vertices = e2.vertices
  51             source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[0]}
  52             destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[1]}
  53             product_graph.connect source, destination
  54             source = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[0] and v.g2_vertex == e2_vertices[1]}
  55             destination = product_graph.vertices.find {|v| v.g1_vertex == e1_vertices[1] and v.g2_vertex == e2_vertices[0]}
  56             product_graph.connect source, destination
  57           end
  58         end
  59       end
  60       product_graph.vertices.reject! {|v| v.neighbours.empty?}
  61       product_graph
  62     end
  63
  64
  65     def initial_similarity
  66       self.vertices.each do |v|
  67         if block_given?
  68           v.initial_similarity = yield v
  69         else
  70           v.initial_similarity = 1.0
  71         end
  72         v.similarity = v.initial_similarity
  73       end
  74     end
  75
  76     # Performs similarity flooding on a graph
  77     # Assumes that the initial similarity has already been calculated
  78     def similarity_flood(opts = {})
  79       max_iterations = opts[:iterations] || 100
  80       max_residual = opts[:max_residual] || 0.001
  81       iteration = 1
  82       residual = max_residual + 1
  83       while residual > max_residual and iteration <= max_iterations
  84 # puts "Starting iteration #{iteration}"
  85         self.vertices.each do |v|
  86           v.last_similarity = v.similarity
  87         end
  88         self.vertices.each do |v|
  89 # puts "Processing vertex #{v.name}"
  90           edge_groups = v.edges.group_by {|e| e.type }
  91 # puts "  Edge groups {#{edge_groups.keys.map {|t| t.to_s + ' => {' + edge_groups[t].map {|e| e.to_s}.join(', ')}.join('; ')}}"
  92           edge_groups.each do |type, edges|
  93 # puts "    Processing group type #{type}"
  94             n = edges.length
  95             edges.each do |e|
  96               e.other_end(v).similarity += v.last_similarity / n
  97             end
  98           end
  99         end
 100 #         self.vertices.each do |v|
 101 #           n = v.neighbours.length
 102 #           v.neighbours.each do |neighbour|
 103 #             neighbour.similarity += v.last_similarity / n
 104 #           end
 105 #         end
 106         max_similarity = vertices.map {|v| v.similarity}.max
 107         self.vertices.each do |v|
 108           v.similarity = v.similarity / max_similarity
 109         end
 110         residual = Math.sqrt(self.vertices.reduce(0) {|a, v| a += (v.similarity - v.last_similarity) ** 2})
 111 # puts "Residual = #{residual.round(3)}, sims = #{self.vertices.map {|v| v.name + " = " + v.similarity.round(2).to_s}}"
 112         iteration += 1
 113       end
 114
 115     end
 116
 117   end # class
 118 end