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

class Graph
  attr_accessor :nodes, :links, :infinity

  def initialize(csv)
    @nodes = []
    @links = []
    @distance = nil
    @infinity = 100_000
    raise Exception.new("the file must be a .csv") unless File.extname(csv) == ".csv"

    CSV.foreach(csv, headers: true) do |row|
      #last because CSV#delete returns [column,value]
      source_id = row.delete('source').last
      target_id = row.delete('target').last

      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: row['weight'], year: row['year'])
    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 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 if sp
      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(normalized = 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)}
    else
      bts
    end
  end

  def diameter
    distances unless @distance

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

  private

  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
end