clusters.rb

# coding: utf-8

require 'csv'

# todo: document
module Clusters
  VERSION     = '0.0.1'
  EPS         = 1.7
  MIN_POINTS  = 2

  # Precondition checking
  class Preconditions
    def self.check_argument(exp, msg = nil, *fmt)
      unless exp
        raise_exception(ArgumentError, msg, *fmt)
      end
      exp
    end

    def self.raise_exception(e, msg, *fmt)
      message = ''
      message = sprintf(msg, *fmt) unless fmt.empty?
      message = msg                unless msg.nil?

      raise e, message
    end
  end

  # TODO
  class Operations
    def self.inner_product(vector_a, vector_b)
      product = 0.0
      vector_a.zip(vector_b) do |x, y|
        product += x * y
      end
      product
    end

    def self.plus(a, b)
      n = a.size - 1
      v = []
      (0..n).each { |i|
        v[i] = a[i] + b[i]
      }
      v
    end

    def self.sum(vector)
      vector.inject(0.0) { |result, element| result + element }
    end

    def self.sum_square(vector)
      vector.inject(0.0) { |result, element| result + element**2 }
    end

    def self.sqrt_sum_square(vector)
      Math.sqrt(sum_square(vector))
    end

    def self.sum_diff_square(vector_a, vector_b)
      sum = 0.0
      vector_a.zip(vector_b) do |x, y|
        sum += (x - y)**2
      end
      sum
    end
  end

  # TODO
  class Distances
    def check_preconditions(a, b)
      are_arrays        = (is_array?(a) && is_array?(b))
      same_dimension    = have_same_dimension?(a, b)
      non_null_vectors  = !(is_null_vector(a) || is_null_vector(b))
      Preconditions.check_argument(are_arrays, 'You have entered non array vectors')
      Preconditions.check_argument(same_dimension, 'You have entered two vectors with diff dimensions')
      Preconditions.check_argument(non_null_vectors, 'You have entered a null vector')
    end

    def euclid_distance(vector_a, vector_b)
      Math::sqrt(Operations.sum_diff_square(vector_a, vector_b))
    end

    def euclid_similarity(vector_a, vector_b)
      1.0 / (1.0 + euclid_distance(vector_a, vector_b))
    end

    def is_array?(vector)
      vector.instance_of?(Array)
    end


    def have_same_dimension?(vector_a, vector_b)
      vector_a.size == vector_b.size
    end

    def is_null_vector(vector)
      vector.empty?
    end

    def calculate(vector_a, vector_b)
      check_preconditions(vector_a, vector_b)
      euclid_distance(vector_a, vector_b)
    end
  end

  # Single Link Clustering
  class SingleLink
    INFINITY = +1.0/0.0

    # m: measurer
    # k: k clusters
    # data: an array of feature vectors
    def cluster(s, k, data)

      distance = EPS

      while true
        # loop with increasing distance until
        # cluster size is correct
        distance    *= 1.1 # TODO: this may need tuning/parameterization
        clusters    = []
        all_vectors = data

        until all_vectors.empty?
          # build clusters at this distance
          p = all_vectors[0]
          others = all_vectors[1..data.length - 1]

          close = []
          far = []

          others.to_a.each do |i|
            #puts s.calculate(p, i)
            if p != i && s.calculate(p, i) < distance
              close << i unless i.nil?
            else
              far << i unless i.nil?
            end
          end

          close << p
          clusters << close
          all_vectors = far
        end

        if clusters.size <= k
         return clusters
        end
      end
    end


  end

  # TODO
  class DensityBasedScan
    # todo: document
    def initialize(eps, min_pts)
      @distance   = Distances.new
      @eps        = eps
      @min_pts    = min_pts
    end

    def cluster(data)
      clusters = []
      visited  = Hash.new
      eps      = @eps
      min_pts  = @min_pts

      data.each do |vector|
        if visited[vector] != :visited
          visited[vector] = :visited
          neighbors = find_neighbors(data, vector, eps)
          if neighbors.size < min_pts
            visited[vector] = :noise
          else
            cluster = [vector]
            clusters.push(cluster)
            neighbors.each do |neighbor|
              # not contained in the cluster
              unless clusters.map { |val| val.include?(neighbor) }.include?(true)
                expand(data, visited, neighbor, cluster, clusters, eps, min_pts)
              end
            end
          end
        end
      end
      clusters
    end

    def expand(data, visited, vector, cluster, clusters, eps, min_pts)
      cluster.push(vector)
      if visited[vector] != :visited
        visited[vector] = :visited
        neighbors       = find_neighbors(data, vector, eps)
        if neighbors.size >= min_pts
          neighbors.each do |neighbor|
            unless clusters.map {|val| val.include?(neighbor)}.include?(true)
              expand(data, visited, neighbor, cluster, clusters, eps, min_pts)
            end
          end
        end
      end
    end

    def find_neighbors(data, a, eps)
      hood = []
      data.each do |b|
        if alike?(a, b, eps)  # dbscan is < eps
          hood.push(b)
        end
      end
      hood
    end

    # alike, but no the same
    def alike?(a, b, eps)
      distance = @distance.calculate(a, b)
      a != b && distance < eps
    end

  end

  # TODO
  class Plot
    # TODO
    # 1. plot frequency distribution of loops in bind
    # 2. plot clusters
    # 3. build a table (taxonomy)
    # 4. create a document for presentation
  end

  def self.of(data, eps = EPS, min_pts = MIN_POINTS)
    cluster_maker = DensityBasedScan.new(eps, min_pts)
    cluster_maker.cluster(data)
  end


  def self.generate_features(path)
    output   = []

    CSV.foreach(path, :headers => true) do |row|
      features = []

      # loop field
      loop = row['loop']

      features << loop.scan(/update/m).size               # state update
      features << [loop.scan(/while/m).size - 1, 0].max   # inner while
      features << [loop.scan(/for/m).size   - 1, 0].max   # inner for
      features << [loop.scan(/do/m).size    - 1, 0].max   # inner do-while
      features << loop.scan(/if\s*(.*?)/m).size +
                  loop.scan(/switch\s*(.*?)/m).size       # conditionals

      # structs field
      features << row['structs'].split(' ').reject {|s| s == 'none' }.size

      # types field
      features << row['types'].split(' ').reject {|s| s == 'none' }.size

      # number of terms in loop invariant (include those cases where you
      features << row['loopinv'].split( /\s+|\b/ )
                  .reject {|each|
                      each.match(/([\[\]\{\\}\*\?\\])/) # remove [] and () and {}
                  }.size

      output << features
    end
    output
  end

  def self.prune(data)
    output = []
    data.each do |e|
      unless e == []
        ref = output.include?(e)
        if ref
          #nothing
        else
          output << e
        end
      end
    end

  end

  def self.find_distinct(field, path)
    output = []

    CSV.foreach(path, :headers => true) do |row|
      structs = row[field].split(' ')
      structs.each do |e|
        unless e == 'none'
          ref = output.include?(e)
          if ref
            #nothing
          else
            output << e
          end
        end
      end
    end

    output.size
  end

  def self.echo(data)
    puts 'All feature vectors'
    puts '-----------------------------'

    index = 0
    data.each do |feature_vector|
      print "#{index += 1}. " + feature_vector.to_s
      print "\n"
    end
    print "\n"
  end

  def self.dbscan(path)
    # F = [ #updates, #inner_whiles,
    #       #inner_fors, #inner_dowhiles,
    #       #conditionals, #structs,
    #       #user_types, #terms_in_loop_invariant
    # ]
    data = generate_features(path)
    echo(data)
    clusters = of(prune(data))
    overview(data, clusters, 'Using Density based Scan Clustering')
  end

  def self.single_link(path, k)
    data        = generate_features(path)
    single_link = SingleLink.new
    s           = Distances.new
    clusters    = single_link.cluster(s, k, prune(data))
    overview(data, clusters, 'Single Link Clustering')
  end

  def self.min_distance(clusters)
    d   = Distances.new
    max = 0.0

    clusters.each do |cluster|
      clusters.each do |cluster_prime|
        val = d.calculate(cluster, cluster_prime)
        if val > max
          max = val
        end
      end
    end

    max

  end

  def self.overview(data, clusters, msg)
    indexes  = {}
    data.each_with_index { |key, index| indexes[key] = index }

    puts "All clusters (using #{msg})"
    puts "Dimensionality: #{clusters.size}"
    puts '-----------------------------'

    clusters.each_index do |dim|

      puts
      puts "Cluster #{dim + 1} of size #{clusters[dim].size} "
      puts "Cluster's distance between its elements is #{min_distance(clusters[dim])} "

      clusters[dim].each do |cluster|
        print cluster
        print '@('
        print indexes[cluster]
        print ')'
        print "\n"
      end
    end
    print "\n"
  end

end

# Build clusters from collected data in csv file
Clusters.dbscan('structs_and_types.csv')
Clusters.single_link('structs_and_types.csv', 4)