Module: RandomGraph::GraphAlgorithms

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

Instance Method Summary collapse

Instance Method Details

#average_case_diameter ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/random_graph/graph_algorithms.rb', line 66

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 



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

def BFS_distance(root)
    distance = Array.new(@size)
    distance.fill(Float::INFINITY)

    queue = []

    distance[root] = 0
    queue.unshift(root)

    while !queue.empty? do

      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 



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/random_graph/graph_algorithms.rb', line 79

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 



29
30
31
32
33
34
35
36
 
# File 'lib/random_graph/graph_algorithms.rb', line 29

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 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/random_graph/graph_algorithms.rb', line 38

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 



54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/random_graph/graph_algorithms.rb', line 54

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