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 



63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/random_graph/graph_algorithms.rb', line 63

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 



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

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

    queue = []

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

    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 



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

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 



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

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 



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

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 



51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/random_graph/graph_algorithms.rb', line 51

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