lib/rgraph/graph.rb in rgraph-0.0.15 vs lib/rgraph/graph.rb in rgraph-0.1.1

@@ -1,7 +1,8 @@
 #encoding: utf-8
 require 'csv'
+require 'fw'
 require_relative '../../lib/rgraph/link'
 require_relative '../../lib/rgraph/node'
 
 class Graph
   attr_accessor :nodes, :links, :infinity
@@ -10,11 +11,11 @@
     csv = CSV.new(string, headers: true)
     new(csv)
   end
 
   def initialize(csv)
-    @nodes = []
+    @nodes = {}
     @links = []
     @distance = nil
     @infinity = 100_000
 
     csv = CSV.new(File.open(csv), headers: true) if csv.is_a?(String)
@@ -34,19 +35,19 @@
       @links << Link.new(source: source, target: target, weight: weight, type: type)
     end
   end
 
   def each_node(&block)
-    @nodes.each(&block)
+    @nodes.each_value(&block)
   end
 
   def each_link(&block)
     @links.each(&block)
   end
 
   def degrees
-    @nodes.map{|node| node.degree}
+    @nodes.values.map{|node| node.degree}
   end
 
   def average_degree
     degrees.inject(:+) / @nodes.size.to_f
   end
@@ -57,40 +58,22 @@
   end
 
   def idistance
     dist = matrix(@nodes.size, 0)
 
-    sorted = @nodes.sort { |a,b| a.id <=> b.id}
-
-    sorted.each_with_index do |n1, i|
-      sorted.each_with_index do |n2, j|
+    @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
+        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
-    @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
-          if @distance[i][j] == new_dist && !(@path[i][j].include? k) && ! [i,j].include?(k)
-            @path[i][j] << k
-          end
-        end
-      end
-    end
-    @distance
+    @distance = idistance.fw!(@path)
   end
 
   def mdistance
     distances unless @distance
 
@@ -105,11 +88,11 @@
     @shortest_paths = []
 
     distances
     giant_component
 
-    nodes = giant ? @giant_component : @nodes
+    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
@@ -117,11 +100,11 @@
 
     @shortest_paths
   end
 
   def shortest_path(i, j, multiples = false, giant = false)
-    nodes = giant ? @giant_component : @nodes
+    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 = []
@@ -202,20 +185,20 @@
     existent = node.neighbours.combination(2).select{ |t| t[0].neighbours.include?(t[1]) }.count
     existent / possible.to_f
   end
 
   def clustering
-    nodes.map{ |node| single_clustering(node) }.inject(:+) / nodes.size.to_f
+    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)
 
-    while true
+    loop do
       return @page_rank if @page_rank.inject(:+) - step_page_rank(d, e).inject(:+) < e
     end
   end
 
   def components
@@ -223,11 +206,11 @@
 
     @components = []
 
     @distance.each do |d|
       same = []
-      d.each_with_index { |dist, i| same << @nodes[i] if dist != @infinity}
+      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
@@ -250,31 +233,31 @@
 
   def step_page_rank(d = 0.85, e = 0.01)
     n = @nodes.count
     tmp = Array.new(n, 0)
 
-    @nodes.each_with_index do |node,i|
+    @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.index(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.select{|n| n.id == node_id}.first
+    @nodes[node_id]
   end
 
   def maybe_add_to_nodes(*nodes)
     nodes.each do |node|
-      @nodes << node unless get_node_by_id(node.id)
+      @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