lib/rgraph/graph.rb in rgraph-0.0.6 vs lib/rgraph/graph.rb in rgraph-0.0.8

@@ -1,32 +1,30 @@
+#encoding: utf-8
 require 'csv'
 require_relative '../../lib/rgraph/link'
 require_relative '../../lib/rgraph/node'
 
-
 class Graph
-  attr_accessor :nodes, :links
+  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
 
-      unless source = get_node_by_id(source_id)
-        source = Node.new(id: source_id)
-        @nodes << source
-      end
-      unless target = get_node_by_id(target_id)
-        target = Node.new(id: target_id)
-        @nodes << target
-      end
+      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)
@@ -45,19 +43,116 @@
     degrees.inject(:+) / @nodes.size.to_f
   end
 
   def cumulative_degree
     cached_degrees = degrees
-    cum = []
+    out = []
 
     0.upto(degrees.max - 1) do |i|
-      cum[i] = cached_degrees.select{|degree| degree > i}.count
+      out[i] = cached_degrees.select{|degree| degree > i}.count
     end
-    cum.map{|a| a / cum.max.to_f}
+    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