graph.rb in rgraph-0.0.14

- old
+ new

@@ -50,44 +50,43 @@
   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 = (0..(degrees.max - 1)).map { |i| degrees.select{|degree| degree > i}.count }
     out.map{|a| a / out.max.to_f}
   end
 
   def idistance
-    dist = Array.new(@nodes.size) { Array.new(@nodes.size, 0) }
+    dist = matrix(@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
+    sorted = @nodes.sort { |a,b| a.id <=> b.id}
+
+    sorted.each_with_index do |n1, i|
+      sorted.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
 
   def distances
-    @path = Array.new(@nodes.size) { Array.new(@nodes.size, nil) }
+    @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
+            @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
   end
@@ -97,45 +96,55 @@
 
     fdistance = @distance.flatten.select{|d| d != @infinity}
     fdistance.inject(:+) / fdistance.count.to_f
   end
 
-  def shortest_paths
-    tmp = []
+  def shortest_paths(args = {})
+    multiples = args[:multiples] || false
+    @shortest_paths = []
 
-    distances unless @my_shortest_paths
+    distances
 
     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 unless sp.empty?
+      (i + 1).upto(@nodes.size - 1).each do |j|
+        @shortest_paths += shortest_path(i, j, multiples)
       end
     end
 
-    @shortest_paths = tmp
+    @shortest_paths
   end
 
-  def shortest_path(i, j)
+  def shortest_path(i, j, multiples = false)
 
     return [] if @distance[i][j] == @infinity
 
-    k = @path[i][j]
+    path = @path[i][j].count == 1 || multiples ? @path[i][j] : [@path[i][j].first]
+    out = []
 
-    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]
+    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
 
   def between(i)
-    shortest_paths unless @shortest_paths
+    shortest_paths(multiples: true)
 
     n = @shortest_paths.select{|c| c[1..-2].include?(i)}.size.to_f
     m = @shortest_paths.size.to_f
     n / m
   end
@@ -247,10 +256,18 @@
     nodes.each do |node|
       @nodes << 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
+  end
+
   def possible_connections(node)
     total = node.neighbours.count
     total * (total - 1) / 2
+  end
+
+  def matrix(size, value)
+    Array.new(size) { Array.new(size, value) }
   end
 end