Module: RandomGraph::GraphAlgorithms

Included in:
Graph
Defined in:
lib/random_graph/graph_algorithms.rb

Overview

module implements graph algorithms

Instance Method Summary collapse

Instance Method Details

#average_case_diameter ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/random_graph/graph_algorithms.rb', line 60

def average_case_diameter
  real_bad = number_of_components > 1 ? Float::INFINITY : 0
  total = 0
  if real_bad == 0
    (0...size).each do |i|
      distances = bfs_distance(i)
      average = distances.inject(:+).to_f / (size - 1)
      total += average
    end
  end
  total / size
end

#bfs_distance(root) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/random_graph/graph_algorithms.rb', line 5

def bfs_distance(root)
  distance = Array.new(@size).fill(Float::INFINITY)
  queue = [root]
  distance[root] = 0

  until queue.empty?

    current = queue.pop
    adj = adjacent_nodes(current)
    adj.each do |a|
      if distance[a] == Float::INFINITY
        distance[a] = distance[current] + 1
        queue.unshift(a)
      end
    end
  end
  distance
end

#clustering_coefficient ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/random_graph/graph_algorithms.rb', line 73

def clustering_coefficient
  total_cluster = 0
  (0...size).each do |i|
    neighbors = adjacent_nodes(i)
    k = neighbors.size
    possible_connections = k.to_f * (k - 1) / 2
    actual_connections = 0
    (0...k).each do |l|
      (i + 1...k).each do |j|
        actual_connections += 1 if edge?(neighbors[l], neighbors[j])
      end
    end
    if possible_connections == 0 then clustering = 0
    else clustering = actual_connections.to_f / possible_connections
    end
    total_cluster += clustering
  end
  total_cluster / size
end

#connected_component(root) ⇒ Object 



24
25
26
27
28
29
30
31
 
# File 'lib/random_graph/graph_algorithms.rb', line 24

def connected_component(root)
  distances = bfs_distance(root)
  adjacent = []
  (0...distances.size).each do |i|
    adjacent << i unless distances[i] == Float::INFINITY
  end
  adjacent
end

#number_of_components ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/random_graph/graph_algorithms.rb', line 33

def number_of_components
  visited = Array.new(size)
  visited.fill(false)
  counter = 0
  (0...size).each do |i|
    next if visited[i] == true
    counter += 1
    comp = connected_component(i)
    comp.each do |reachable|
      visited[reachable] = true
    end
  end
  counter
end

#worst_case_diameter ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/random_graph/graph_algorithms.rb', line 48

def worst_case_diameter
  real_bad = number_of_components > 1 ? Float::INFINITY : 0
  worst = 0
  if real_bad == 0
    (0...size).each do |i|
      distances = bfs_distance(i)
      worst = [distances.max, worst].max
    end
  end
  [worst, real_bad].max
end