Class: Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/rgraph/graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(csv) ⇒ Graph

Returns a new instance of Graph.

Raises:

  • (Exception) 


9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/rgraph/graph.rb', line 9

def initialize(csv)
  @nodes = []
  @links = []
  @distance = nil
  @infinity = 100_000
  raise Exception.new("the file must be a .csv") unless File.extname(csv) == ".csv"

  CSV.foreach(csv, headers: true) do |row|
    #last because CSV#delete returns [column,value]
    source_id = row.delete('source').last
    target_id = row.delete('target').last

    source = get_node_by_id(source_id) || Node.new(id: source_id)
    target = get_node_by_id(target_id) || Node.new(id: target_id)

    maybe_add_to_nodes(source, target)

    @links << Link.new(source: source, target: target, weight: row['weight'], year: row['year'])
  end
end

Instance Attribute Details

#infinity ⇒ Object

Returns the value of attribute infinity.



7
8
9
 
# File 'lib/rgraph/graph.rb', line 7

def infinity
  @infinity
end

#links ⇒ Object

Returns the value of attribute links.



7
8
9
 
# File 'lib/rgraph/graph.rb', line 7

def links
  @links
end

#nodes ⇒ Object

Returns the value of attribute nodes.



7
8
9
 
# File 'lib/rgraph/graph.rb', line 7

def nodes
  @nodes
end

Instance Method Details

#average_degree ⇒ Object 



42
43
44
 
# File 'lib/rgraph/graph.rb', line 42

def average_degree
  degrees.inject(:+) / @nodes.size.to_f
end

#between(i) ⇒ Object 



120
121
122
123
124
125
126
 
# File 'lib/rgraph/graph.rb', line 120

def between(i)
  shortest_paths unless @shortest_paths

  n = @shortest_paths.select{|c| c[1..-2].include?(i)}.size.to_f
  m = @shortest_paths.size.to_f
  n / m
end

#betweenness(normalized = false) ⇒ Object 



128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/rgraph/graph.rb', line 128

def betweenness(normalized = false)
  bts = 0.upto(@nodes.size - 1).map { |i| between(i) }

  if normalized
    max = bts.max
    min = bts.min

    bts.map{|bt| (bt - min) / (max - min)}
  else
    bts
  end
end

#cumulative_degree ⇒ Object 



46
47
48
49
50
51
52
53
54
 
# File 'lib/rgraph/graph.rb', line 46

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.map{|a| a / out.max.to_f}
end

#degrees ⇒ Object 



38
39
40
 
# File 'lib/rgraph/graph.rb', line 38

def degrees
  @nodes.map{|node| node.degree}
end

#diameter ⇒ Object 



141
142
143
144
145
 
# File 'lib/rgraph/graph.rb', line 141

def diameter
  distances unless @distance

  (distances.flatten - [@infinity]).max
end

#distances ⇒ Object 



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/rgraph/graph.rb', line 69

def distances
  @path = Array.new(@nodes.size) { Array.new(@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
      end
    end
  end
  @distance
end

#each_link(&block) ⇒ Object 



34
35
36
 
# File 'lib/rgraph/graph.rb', line 34

def each_link(&block)
  @links.each(&block)
end

#each_node(&block) ⇒ Object 



30
31
32
 
# File 'lib/rgraph/graph.rb', line 30

def each_node(&block)
  @nodes.each(&block)
end

#idistance ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/rgraph/graph.rb', line 56

def idistance
  dist = Array.new(@nodes.size) { Array.new(@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
    end
  end
  dist
end

#shortest_path(i, j) ⇒ Object 



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/rgraph/graph.rb', line 103

def shortest_path(i, j)

  return [] if @distance[i][j] == @infinity

  k = @path[i][j]

  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]
  end
end

#shortest_paths ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/rgraph/graph.rb', line 87

def shortest_paths
  tmp = []

  distances unless @my_shortest_paths

  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 if sp
    end
  end

  @shortest_paths = tmp
end