Class: Rugraph

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

Overview

Rugraph class representing a Directed graph.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Rugraph

Returns an empty graph.



5
6
7
 
# File 'lib/rugraph.rb', line 5

def initialize
  @structure = {}
end

Class Method Details

.betweenness_centrality(graph) ⇒ Hash

Calculates the betweenness centrality for each node.

Based on Brandes algorithm : algo.uni-konstanz.de/publications/b-fabc-01.pdf

Parameters:

Returns:

  • (Hash) —

    a hash with the nodes as keys and their centrality as values



255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
 
# File 'lib/rugraph.rb', line 255

def self.betweenness_centrality(graph)
  cb = graph.vertices.map { |v| [v, 0] }.to_h
  graph.vertices.each do |source|
    stack = []
    path = Hash.new { [] }
    sig = Hash.new(0)
    sig[source] = 1.0
    distance = {}
    distance[source] = 0
    queue = []
    queue << source

    until queue.empty?
      v = queue.shift
      stack << v

      graph.neighbors_of(v).each do |w|
        unless distance.keys.include? w
          queue << w
          distance[w] = distance[v] + 1
        end
        if distance[w] == distance[v] + 1
          sig[w] += sig[v]
          path[w] += [v]
        end
      end
    end

    delta = Hash.new(0)
    until stack.empty?
      w = stack.pop
      coeff = (1.0 + delta[w]) / sig[w].to_f
      path[w].each do |n|
        delta[n] += sig[n] * coeff
      end
      cb[w] += delta[w] if w != source
    end
  end

  cb
end

.closeness_centrality(graph) ⇒ Object

Calculate the closeness centrality for each node.



301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/rugraph.rb', line 301

def self.closeness_centrality(graph)
  closeness_centrality = {}

  graph.vertices.each do |n|
    shortest_paths = graph.shortest_path_lengths(n)
    sum = shortest_paths.values.reduce(&:+)
    closeness_centrality[n] = 0.0
    next unless (sum > 0) && (graph.order > 1)
    closeness_centrality[n] = (shortest_paths.length - 1) / sum.to_f
    s = (shortest_paths.length - 1).to_f / (graph.order - 1)
    closeness_centrality[n] *= s
  end

  closeness_centrality
end

.degree_centrality(graph) ⇒ Object

Calculate the degree centrality for each node.



321
322
323
324
325
326
 
# File 'lib/rugraph.rb', line 321

def self.degree_centrality(graph)
  s = 1.0 / (graph.order - 1)
  graph.degrees
       .map { |n, d| [n, d * s] }
       .to_h
end

.load_centrality(graph) ⇒ Object

Calculate the load centrality for each node.

Based on NetworkX’s Python implementation.



334
335
336
337
338
339
340
341
342
343
344
 
# File 'lib/rugraph.rb', line 334

def self.load_centrality(graph)
  betweenness = graph.vertices
                     .map { |n| [n, 0.0] }
                     .to_h
  betweenness.each do |source, _|
    ubetween = _node_betweenness(graph, source)
    betweenness.merge(ubetween) do |key, v1, v2|
      betweenness[key] = v1 + v2
    end
  end
end

.new_from_edges_array(edges_array) ⇒ Rugraph

Creates graph from describing array. See #load_from_edges_array

Parameters:

  • edges_array (Array) —

    an array describing the Rugraph

Returns:

  • (Rugraph) —

    the generated graph



21
22
23
 
# File 'lib/rugraph.rb', line 21

def self.new_from_edges_array(edges_array)
  new.load_from_edges_array(edges_array)
end

.new_from_vertices_hash(vertices_hash) ⇒ Rugraph

Creates graph from describing hash. See #load_from_vertices_hash

Parameters:

  • vertices_hash (Hash) —

    a hash describing the Rugraph

Returns:

  • (Rugraph) —

    the generated graph



13
14
15
 
# File 'lib/rugraph.rb', line 13

def self.new_from_vertices_hash(vertices_hash)
  new.load_from_vertices_hash(vertices_hash)
end

Instance Method Details

#<<(node) ⇒ Rugraph

Equivalent to ##add_vertex.

Returns:



243
244
245
 
# File 'lib/rugraph.rb', line 243

def <<(node)
  add_vertex(node)
end

#[](node) ⇒ Array?

Equivalent to #neighbors_of

Returns:

  • (Array, nil) —

    an array of its neighbors if the node exists, nil otherwise



226
227
228
 
# File 'lib/rugraph.rb', line 226

def [](node)
  neighbors_of(node)
end

#[]=(node, node_array) ⇒ Object

Sets the edges coming out of a node.

Returns:

  • the new neighbors of the node



235
236
237
 
# File 'lib/rugraph.rb', line 235

def []=(node, node_array)
  @structure[node] = node_array
end

#add_edge(edge) ⇒ Rugraph

Adds an edge to the graph. If the vertex already exists, do nothing.

Parameters:

  • edge (Array) —

    an array formatted as such [source, dest]

Returns:



68
69
70
71
 
# File 'lib/rugraph.rb', line 68

def add_edge(edge)
  edge.each { |node| add_vertex(node) }
  @structure[edge[0]] << edge[1]
end

#add_node(node) ⇒ Rugraph

Adds a vertex to the graph. If the vertex already exists, do nothing.

Parameters:

  • node (Object) —

    the value of the node to add to the graph

Returns:



60
61
62
 
# File 'lib/rugraph.rb', line 60

def add_node(node)
  add_vertex(node)
end

#add_vertex(node) ⇒ Rugraph

Adds a vertex to the graph. If the vertex already exists, do nothing.

Parameters:

  • node (Object) —

    the value of the node to add to the graph

Returns:



55
56
57
 
# File 'lib/rugraph.rb', line 55

def add_vertex(node)
  @structure[node] ||= []
end

#degree(node) ⇒ Integer

Computes the degree of a node.

Parameters:

  • node (Object) —

    the value of a node.

Returns:

  • (Integer) —

    the degree of the node.



175
176
177
 
# File 'lib/rugraph.rb', line 175

def degree(node)
  in_degree(node) + out_degree(node)
end

#degrees ⇒ Enumerator

Computes the degree of each node.

Returns:

  • (Enumerator) —

    an enumerator of the degrees of all nodes



163
164
165
166
167
168
169
 
# File 'lib/rugraph.rb', line 163

def degrees
  Enumerator.new(@structure.length) do |y|
    nodes.each do |node|
      y << [node, degree(node)]
    end
  end
end

#edges ⇒ Array

Returns the list of all the edges in the graph.

Returns:

  • (Array) —

    an array of pairs of nodes.



217
218
219
220
221
 
# File 'lib/rugraph.rb', line 217

def edges
  @structure.reduce([]) do |acc, node|
    acc + node[1].map { |dest| [node[0], dest] }
  end
end

#edges_from(node) ⇒ Array

Returns the edges coming out of a node.

Returns:

  • (Array) —

    an array of the edges.



148
149
150
 
# File 'lib/rugraph.rb', line 148

def edges_from(node)
  self[node].map { |n| [node, n] }
end

#edges_of(node) ⇒ Array

Returns the edges around a node.

Returns:

  • (Array) —

    an array of the edges.



140
141
142
 
# File 'lib/rugraph.rb', line 140

def edges_of(node)
  edges_from(node) | edges_to(node)
end

#edges_to(node) ⇒ Array

Returns the edges coming from a node.

Returns:

  • (Array) —

    an array of the edges.



156
157
158
 
# File 'lib/rugraph.rb', line 156

def edges_to(node)
  edges.select { |edge| edge.last == node }
end

#in_degree(node) ⇒ Integer

Computes the incoming degree of a node.

Parameters:

  • node (Object) —

    the value of a node.

Returns:

  • (Integer) —

    the degree of the node.



183
184
185
 
# File 'lib/rugraph.rb', line 183

def in_degree(node)
  self[node].length
end

#load_from_edges_array(edges_array) ⇒ Rugraph

Adds vertices and edges to the graph from an array [Array] formatted as such

[[source_node, destination] [source_node2, destination2], ...]

Parameters:

  • edges_array (Array) —

    an array describing the Rugraph

Returns:



42
43
44
45
46
47
48
49
 
# File 'lib/rugraph.rb', line 42

def load_from_edges_array(edges_array)
  @structure = edges_array
               .each_with_object({}) do |edge, nodes|
                 nodes[edge[0]] = [] unless nodes.keys.include? edge[0]
                 nodes[edge[0]] << edge[1]
               end
  self
end

#load_from_vertices_hash(vertices_hash) ⇒ Rugraph

Adds vertices and edges to the graph from a hash [Hash] formatted as such

{ node1 => neighboring_nodes_array, node2 => ... }

Parameters:

  • vertices_hash (Hash) —

    a hash describing the Rugraph

Returns:



31
32
33
34
 
# File 'lib/rugraph.rb', line 31

def load_from_vertices_hash(vertices_hash)
  @structure = vertices_hash
  self
end

#neighbors_of(node) ⇒ Array?

Method returning the neighbors of a node.

Parameters:

  • node (Object) —

    the value corresponding to a node in the graph

Returns:

  • (Array, nil) —

    an array of its neighbors if the node exists, nil otherwise



78
79
80
81
 
# File 'lib/rugraph.rb', line 78

def neighbors_of(node)
  return nil unless nodes.include?(node)
  @structure[node] || []
end

#nodes ⇒ Array

Returns the nodes in the graph

Returns:

  • (Array) —

    the values of all the nodes in the graph.



210
211
212
 
# File 'lib/rugraph.rb', line 210

def nodes
  vertices
end

#order ⇒ Integer

Computes the order (number of nodes) of the graph.

Returns:

  • (Integer) —

    the order of the graph.



198
199
200
 
# File 'lib/rugraph.rb', line 198

def order
  nodes.length
end

#out_degree(node) ⇒ Integer

Computes the outcoming degree of a node.

Parameters:

  • node (Object) —

    the value of a node.

Returns:

  • (Integer) —

    the degree of the node.



191
192
193
 
# File 'lib/rugraph.rb', line 191

def out_degree(node)
  @structure.count { |_source, dest| dest.include? node }
end

#shortest_path_lengths(source) ⇒ Hash

Computes the shortest path lengths from a node to all other accessible nodes.

Parameters:

  • source (Object) —

    the value of the source node.

Returns:

  • (Hash) —

    a hash of the lengths of shortest path to each other node.



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/rugraph.rb', line 88

def shortest_path_lengths(source)
  seen = {}
  level = 0
  nextlevel = { source => 1 }
  until nextlevel.empty?
    thislevel = nextlevel
    nextlevel = {}
    thislevel.each do |v, _|
      if seen[v].nil?
        seen[v] = level
        nextlevel.update(neighbors_of(v).map { |w| [w, nil] }.to_h)
      end
    end
    level += 1
  end
  seen
end

#shortest_paths(source) ⇒ Array

Computes the shortest path a node.

Parameters:

  • source (Object) —

    the value of the source node.

Returns:

  • (Array) —

    an array [pred, seen] containing two hashes :

    • pred [Hash] a hash of the shortest path to each node

    • seen [Hash] a hash of the lengths of the shortest path to each node



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/rugraph.rb', line 112

def shortest_paths(source)
  level = 0
  nextlevel = [source]
  seen = { source => level }
  pred = { source => [] }
  until nextlevel.empty?
    level += 1
    thislevel = nextlevel
    nextlevel = []
    thislevel.each do |v|
      neighbors_of(v).each do |w|
        next if (seen.keys.include? w) && (seen[w] != level)
        unless seen.keys.include? w
          pred[w] = []
          seen[w] = level
          nextlevel << w
        end
        pred[w] << v
      end
    end
  end
  [pred, seen]
end

#vertices ⇒ Array

Returns the nodes in the graph

Returns:

  • (Array) —

    the values of all the nodes in the graph.



205
206
207
 
# File 'lib/rugraph.rb', line 205

def vertices
  (@structure.keys | @structure.values).flatten.uniq
end