#encoding: utf-8
require 'csv'
require_relative '../../lib/rgraph/link'
require_relative '../../lib/rgraph/node'

class Graph
  attr_accessor :nodes, :links, :infinity

  def self.new_from_string(string)
    csv = CSV.new(string, headers: true)
    new(csv)
  end

  def initialize(csv)
    @nodes = []
    @links = []
    @distance = nil
    @infinity = 100_000

    csv = CSV.new(File.open(csv), headers: true) if csv.is_a?(String)

    csv.each do |row|
      #last because CSV#delete returns [column,value]
      source_id = row.delete('source').last
      target_id = row.delete('target').last
      type = row.delete('type').last || 'undirected'
      weight = row.delete('weight').last || 1

      source = get_node_by_id(source_id) || Node.new(id: source_id)
      target = get_node_by_id(target_id) || Node.new(id: target_id)

      maybe_add_to_nodes(source, target)

      @links << Link.new(source: source, target: target, weight: weight, type: type)
    end
  end

  def each_node(&block)
    @nodes.each(&block)
  end

  def each_link(&block)
    @links.each(&block)
  end

  def degrees
    @nodes.map{|node| node.degree}
  end

  def average_degree
    degrees.inject(:+) / @nodes.size.to_f
  end

  def cumulative_degree
    cached_degrees = degrees
    out = []

    0.upto(degrees.max - 1) do |i|
      out[i] = cached_degrees.select{|degree| degree > i}.count
    end
    out.map{|a| a / out.max.to_f}
  end

  def idistance
    dist = Array.new(@nodes.size) { Array.new(@nodes.size, 0) }

    @nodes.sort{|a,b| a.id <=> b.id}.each_with_index do |n1, i|
      @nodes.sort{|a,b| a.id <=> b.id}.each_with_index do |n2, j|
        if i != j
          dist[i][j] = n1.neighbours.include?(n2) ? @links.select{ |link| (link.source == n1 || link.source == n2) && (link.target == n1 || link.target == n2) }.first.weight.to_i : @infinity
          end
      end
    end
    dist
  end

  def distances
    @path = Array.new(@nodes.size) { Array.new(@nodes.size, nil) }

    @distance = idistance
    @distance.each_index do |k|
      @distance.each_index do |i|
        @distance.each_index do |j|
          new_dist = @distance[i][k] + @distance[k][j]
          if @distance[i][j] > new_dist
            @distance[i][j] = new_dist
            @path[i][j] = k
          end
        end
      end
    end
    @distance
  end

  def mdistance
    distances unless @distance

    fdistance = @distance.flatten.select{|d| d != @infinity}
    fdistance.inject(:+) / fdistance.count.to_f
  end

  def shortest_paths
    tmp = []

    distances unless @my_shortest_paths

    0.upto(@nodes.size - 1).each do |i|
      i.upto(@nodes.size - 1).each do |j|
        next if i == j
        sp = shortest_path(i, j)
        tmp << sp unless sp.empty?
      end
    end

    @shortest_paths = tmp
  end

  def shortest_path(i, j)

    return [] if @distance[i][j] == @infinity

    k = @path[i][j]

    case k
    when @infinity
      []
    when nil
      [i,j]
    else
      #We need to do this or k will appear three times
      shortest_path(i, k)[0..-2] + [k] + shortest_path(k, j)[1..-1]
    end
  end

  def between(i)
    shortest_paths unless @shortest_paths

    n = @shortest_paths.select{|c| c[1..-2].include?(i)}.size.to_f
    m = @shortest_paths.size.to_f
    n / m
  end

  def betweenness(args = {})
    cumulative = args[:cumulative] || false

    #If we ask cumulative, normalized must be true
    normalized = args[:normalized] || cumulative || false

    bts = 0.upto(@nodes.size - 1).map { |i| between(i) }

    if normalized
      max = bts.max
      min = bts.min

      bts.map!{|bt| (bt - min) / (max - min)}
    end

    if cumulative
      bts.uniq.sort.map{ |bt1| [bts.select{|bt2| bt2 >= bt1}.count, bt1] }
    else
      bts
    end
  end

  def diameter
    distances unless @distance

    (distances.flatten - [@infinity]).max
  end

  def single_clustering(node)
    possible = possible_connections(node)
    return 0 if possible == 0

    existent = node.neighbours.combination(2).select{ |t| t[0].neighbours.include?(t[1]) }.count
    existent / possible.to_f
  end

  def clustering
    nodes.map{ |node| single_clustering(node) }.inject(:+) / nodes.size.to_f
  end

  def page_rank(d = 0.85, e = 0.01)
    n = @nodes.count

    #Initial values
    @page_rank = Array.new(n, 1 / n.to_f)

    while true
      return @page_rank if @page_rank.inject(:+) - step_page_rank(d, e).inject(:+) < e
    end
  end

  private

  def step_page_rank(d = 0.85, e = 0.01)
    n = @nodes.count
    tmp = Array.new(n, 0)

    @nodes.each_with_index do |node,i|
      #How much 'node' will give to its neighbours
      to_neighbours = @page_rank[i] / node.neighbours.count

      #Give 'to_neighbours' to each neighbour
      node.neighbours.each do |ne|
        j = @nodes.index(ne)
        tmp[j] += to_neighbours
      end
    end

    #Calculates the final value
    @page_rank = tmp.map{|t| ((1 - d) / n) + t * d}
  end

  def get_node_by_id(node_id)
    @nodes.select{|n| n.id == node_id}.first
  end

  def maybe_add_to_nodes(*nodes)
    nodes.each do |node|
      @nodes << node unless get_node_by_id(node.id)
    end
  end

  def possible_connections(node)
    total = node.neighbours.count
    total * (total - 1) / 2
  end
end