gistfile1.rb

require 'digest/sha2'
require 'base64'

module Digraph
  def identifier(*args)
    args.join('|')
    Base64.encode64(Digest::SHA2.hexdigest(args.join))
  end

  class Node
    attr_accessor :id, :name, :attributes

    def initialize(name, attributes = {})
      @id, @name, @attributes = identifier(name), name, attributes
    end
  end

  class Edge
    attr_accessor :id, :source, :target

    def initialize(source, target)
      @id = identifier(source.id, target.id)
      @source, @target = source, target
    end
  end

  class Graph
    attr_accessor :nodeset, :adjacency
    attr_accessor :nodes, :edges

    def initialize
      @nodeset, @adjacency = {}, {}
      @nodes, @edges = [], []
    end

    def self.load(filename)
      Marshal.load(File.open(filename, 'r'))
    end

    def save(filename)
      File.open(filename, 'w') do |f|
        f << Marshal.dump(self)
      end
    end

    def add_node(node)
      @nodes << node unless @nodeset[node.id]
      @nodeset[node.id] = node
      node
    end

    def add_edge(edge)
      @edges << edge unless @edges.any? { |e| e.id == edge.id }

      unless @adjacency[edge.source.id]
        @adjacency[edge.source.id] = {}
      end

      unless @adjacency[edge.source.id][edge.target.id]
        @adjacency[edge.source.id][edge.target.id] = []
      end

      unless @adjacency[edge.source.id][edge.target.id].any? { |e| e.id == edge.id }
        @adjacency[edge.source.id][edge.target.id] << edge
      end

      edge
    end
    
    def get_edges(node1, node2)
      if @adjacency[node1.id] && @adjacency[node1.id][node2.id]
        @adjacency[node1.id][node2.id]
      else
        []
      end
    end
  end
end


include Digraph

def related_words(node, graph)
  graph.adjacency[node.id].collect { |n| n[1][0].target.name }.join(',')
end

g = Graph.new
words = [ 'apple', 'iphone', 'macbook', 'ipad', 'itunes', 'ipod', 'steve jobs' ]
words.each { |w| g.add_node(Node.new(w)) }
edges = words.flat_map { |j| words.map { |k| ([ j, k ] unless j == k) }}.compact.uniq
edges.each { |e| g.add_edge(Edge.new(Node.new(e[0]), Node.new(e[1]))) }
g.save('/tmp/graph.g')

g = Graph.load('/tmp/graph.g')
words.each do |w|
  puts "Related words for '#{w}':"
  puts related_words(Node.new(w), g)
  puts "\n"
end