class Graph
Attributes
infinity[RW]
links[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_link(&block)
click to toggle source
# File lib/rgraph/graph.rb, line 43 def each_link(&block) @links.each(&block) 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
link_between(n1, n2)
click to toggle source
# File lib/rgraph/graph.rb, line 263 def link_between(n1, n2) @links.select{ |l| (l.source == n1 && l.target == n2) || (l.source == n2 && l.target == n1) }.first 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