#encoding: utf-8
require 'csv'
require 'fw'
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_value(&block)
  end

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

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

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

  def cumulative_degree
    out = (0..(degrees.max - 1)).map { |i| degrees.select{|degree| degree > i}.count }
    out.map{|a| a / out.max.to_f}
  end

  def idistance
    dist = matrix(@nodes.size, 0)

    @nodes.values.each_with_index do |n1, i|
      @nodes.values.each_with_index do |n2, j|
        next if i == j
        dist[i][j] = n1.has_neighbour?(n2) ? link_between(n1, n2)[:weight].to_i : @infinity
      end
    end
    dist
  end

  def distances
    @path = matrix(@nodes.size, [nil])
    @distance = idistance.fw!(@path)
  end

  def mdistance
    distances unless @distance

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

  def shortest_paths(args = {})
    multiples = args[:multiples] || false
    giant = args[:giant] || false

    @shortest_paths = []

    distances
    giant_component

    nodes = giant ? @giant_component : @nodes.values

    0.upto(nodes.size - 1).each do |i|
      (i + 1).upto(nodes.size - 1).each do |j|
        @shortest_paths += shortest_path(i, j, multiples, giant)
      end
    end

    @shortest_paths
  end

  def shortest_path(i, j, multiples = false, giant = false)
    nodes = giant ? @giant_component : @nodes.values

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

    path = @path[i][j].count == 1 || multiples ? @path[i][j] : [@path[i][j].first]
    out = []

    path.each do |k|

      case k
      when @infinity
        out << []
      when nil
        out << [i,j]
      else
        i_k = shortest_path(i, k)
        k_j = shortest_path(k, j)

        i_k.each do |ik|
          k_j.each do |kj|
            out << ik[0..-2] + [k] + kj[1..-1]
          end
        end
      end
    end
    out
  end

  def between(i, args = {})
    giant = args[:giant] || false
    shortest_paths(multiples: true, giant: giant)

    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
    giant = args[:giant] || false

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

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

    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 farness
    distances unless @distance

    @distance.map{ |line| line.select{|l| l != @infinity }.inject(:+) }
  end

  def closeness
    farness.map{|f| 1.0 / f }
  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.values.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)

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

  def components
    distances unless @distance

    @components = []

    @distance.each do |d|
      same = []
      d.each_with_index { |dist, i| same << @nodes.values[i] if dist != @infinity}

      #its a new component
      if @components.select{ |c| c.include?(same.first) }.size == 0
        @components << same
      end
    end
    @components
  end

  def giant_component
    components unless @components

    @giant_component = []
    @components.each do |c|
      @giant_component = c if c.size > @giant_component.size
    end

    @giant_component
  end

  private

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

    @nodes.values.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.values.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[node_id]
  end

  def maybe_add_to_nodes(*nodes)
    nodes.each do |node|
      @nodes[node[:id]] = node unless get_node_by_id(node[:id])
    end
  end

  def link_between(n1, n2)
    @links.select{ |l| (l.source == n1 && l.target == n2) || (l.source == n2 && l.target == n1) }.first
  end

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

  def matrix(size, value)
    Array.new(size) { Array.new(size, value) }
  end
end