class Graph

Attributes

infinity[RW]
nodes[RW]

Public Class Methods

new(csv) click to toggle source
# File lib/rgraph/graph.rb, line 15
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
new_from_string(string) click to toggle source
# File lib/rgraph/graph.rb, line 10
def self.new_from_string(string)
  csv = CSV.new(string, headers: true)
  new(csv)
end

Public Instance Methods

average_degree() click to toggle source
# File lib/rgraph/graph.rb, line 51
def average_degree
  degrees.inject(:+) / @nodes.size.to_f
end
between(i, args = {}) click to toggle source
# File lib/rgraph/graph.rb, line 133
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
betweenness(args = {}) click to toggle source
# File lib/rgraph/graph.rb, line 142
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
closeness() click to toggle source
# File lib/rgraph/graph.rb, line 177
def closeness
  farness.map{|f| 1.0 / f }
end
clustering() click to toggle source
# File lib/rgraph/graph.rb, line 189
def clustering
  nodes.values.map{ |node| single_clustering(node) }.inject(:+) / nodes.size.to_f
end
components() click to toggle source
# File lib/rgraph/graph.rb, line 204
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
cumulative_degree() click to toggle source
# File lib/rgraph/graph.rb, line 55
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
degrees() click to toggle source
# File lib/rgraph/graph.rb, line 47
def degrees
  @nodes.values.map{|node| node.degree}
end
diameter() click to toggle source
# File lib/rgraph/graph.rb, line 165
def diameter
  distances unless @distance

  (@distance.flatten - [@infinity]).max
end
distances() click to toggle source
# File lib/rgraph/graph.rb, line 72
def distances
  @path = matrix(@nodes.size, [nil])
  @distance = idistance.fw!(@path)
end
each_node(&block) click to toggle source
# File lib/rgraph/graph.rb, line 39
def each_node(&block)
  @nodes.each_value(&block)
end
farness() click to toggle source
# File lib/rgraph/graph.rb, line 171
def farness
  distances unless @distance

  @distance.map{ |line| line.select{|l| l != @infinity }.inject(:+) }
end
giant_component() click to toggle source
# File lib/rgraph/graph.rb, line 221
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
idistance() click to toggle source
# File lib/rgraph/graph.rb, line 60
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
mdistance() click to toggle source
# File lib/rgraph/graph.rb, line 77
def mdistance
  distances unless @distance

  fdistance = @distance.flatten.select{|d| d != @infinity}
  fdistance.inject(:+) / fdistance.count.to_f
end
page_rank(d = 0.85, e = 0.01) click to toggle source
# File lib/rgraph/graph.rb, line 193
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
shortest_path(i, j, multiples = false, giant = false) click to toggle source
# File lib/rgraph/graph.rb, line 104
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
shortest_paths(args = {}) click to toggle source
# File lib/rgraph/graph.rb, line 84
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
single_clustering(node) click to toggle source
# File lib/rgraph/graph.rb, line 181
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

Private Instance Methods

get_node_by_id(node_id) click to toggle source
# File lib/rgraph/graph.rb, line 253
def get_node_by_id(node_id)
  @nodes[node_id]
end
matrix(size, value) click to toggle source
# File lib/rgraph/graph.rb, line 272
def matrix(size, value)
  Array.new(size) { Array.new(size, value) }
end
maybe_add_to_nodes(*nodes) click to toggle source
# File lib/rgraph/graph.rb, line 257
def maybe_add_to_nodes(*nodes)
  nodes.each do |node|
    @nodes[node[:id]] = node unless get_node_by_id(node[:id])
  end
end
possible_connections(node) click to toggle source
# File lib/rgraph/graph.rb, line 267
def possible_connections(node)
  total = node.neighbours.count
  total * (total - 1) / 2
end
step_page_rank(d = 0.85, e = 0.01) click to toggle source
# File lib/rgraph/graph.rb, line 234
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