class Rugraph

Rugraph class representing a Directed graph.

Public Class Methods

betweenness_centrality(graph) click to toggle source

Calculates the betweenness centrality for each node.

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

@param graph [Rugraph] a graph @return [Hash] a hash with the nodes as keys and their centrality as values

# 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) click to toggle source

Calculate the closeness centrality for each node.

@param (see betweenness_centrality) @return (see betweenness_centrality)

# 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) click to toggle source

Calculate the degree centrality for each node.

@param (see betweenness_centrality) @return (see betweenness_centrality)

# 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) click to toggle source

Calculate the load centrality for each node.

Based on NetworkX’s Python implementation.

@param (see betweenness_centrality) @return (see betweenness_centrality)

# 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() click to toggle source

@return [Rugraph] an empty graph.

# File lib/rugraph.rb, line 5
def initialize
  @structure = {}
end

new_from_edges_array(edges_array) click to toggle source

Creates graph from describing array. See {#load_from_edges_array}

@param (see load_from_edges_array) @return [Rugraph] the generated graph

# 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) click to toggle source

Creates graph from describing hash. See {#load_from_vertices_hash}

@param (see load_from_vertices_hash) @return [Rugraph] the generated graph

# File lib/rugraph.rb, line 13
def self.new_from_vertices_hash(vertices_hash)
  new.load_from_vertices_hash(vertices_hash)
end

Private Class Methods

_node_betweenness(graph, source) click to toggle source

# File lib/rugraph.rb, line 346
def self._node_betweenness(graph, source)
  (pred, between) = graph.shortest_paths(source)

  ordered = _ordered_nodes_from_paths(between)
  between.each { |k, _| between[k] = 1.0 }

  until ordered.empty?
    v = ordered.pop
    next unless pred.include? v
    pred[v].each do |x|
      break if x == source
      between[x] += between[v] / pred[v].size.to_f
    end
  end

  between.each { |n, _| between[n] -= 1 }
end

_ordered_nodes_from_paths(paths) click to toggle source

# File lib/rugraph.rb, line 364
def self._ordered_nodes_from_paths(paths)
  paths.to_a
       .sort { |a, b| a.last <=> b.last }
       .map(&:first)
       .flatten
end

Public Instance Methods

<<(node) click to toggle source

Equivalent to #{add_vertex}.

@params (see add_vertex) @return (see add_vertex)

# File lib/rugraph.rb, line 243
def <<(node)
  add_vertex(node)
end

[](node) click to toggle source

Equivalent to {#neighbors_of}

@return (see neighbors_of)

# File lib/rugraph.rb, line 226
def [](node)
  neighbors_of(node)
end

[]=(node, node_array) click to toggle source

Sets the edges coming out of a node.

@params node_array [Array] an array of nodes @params node [node] the concerned node @return the new neighbors of the node

# File lib/rugraph.rb, line 235
def []=(node, node_array)
  @structure[node] = node_array
end

add_edge(edge) click to toggle source

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

@param edge [Array] an array formatted as such [source, dest] @return [Rugraph] the graph

# 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) click to toggle source

(see add_vertex)

# File lib/rugraph.rb, line 60
def add_node(node)
  add_vertex(node)
end

add_vertex(node) click to toggle source

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

@param node [Object] the value of the node to add to the graph @return [Rugraph] the graph

# File lib/rugraph.rb, line 55
def add_vertex(node)
  @structure[node] ||= []
end

degree(node) click to toggle source

Computes the degree of a node.

@param node [Object] the value of a node. @return [Integer] the degree of the node.

# File lib/rugraph.rb, line 175
def degree(node)
  in_degree(node) + out_degree(node)
end

degrees() click to toggle source

Computes the degree of each node.

@return [Enumerator] an enumerator of the degrees of all nodes

# 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() click to toggle source

Returns the list of all the edges in the graph.

@return [Array] an array of pairs of nodes.

# 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) click to toggle source

Returns the edges coming out of a node.

@params node [Object] @return [Array] an array of the edges.

# File lib/rugraph.rb, line 148
def edges_from(node)
  self[node].map { |n| [node, n] }
end

edges_of(node) click to toggle source

Returns the edges around a node.

@params node [Object] @return [Array] an array of the edges.

# File lib/rugraph.rb, line 140
def edges_of(node)
  edges_from(node) | edges_to(node)
end

edges_to(node) click to toggle source

Returns the edges coming from a node.

@params node [Object] @return [Array] an array of the edges.

# File lib/rugraph.rb, line 156
def edges_to(node)
  edges.select { |edge| edge.last == node }
end

in_degree(node) click to toggle source

Computes the incoming degree of a node.

@param (see degree) @return (see degree)

# File lib/rugraph.rb, line 183
def in_degree(node)
  self[node].length
end

load_from_edges_array(edges_array) click to toggle source

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

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

@param edges_array [Array] an array describing the Rugraph @return [Rugraph] the graph

# 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) click to toggle source

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

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

@param vertices_hash [Hash] a hash describing the Rugraph @return [Rugraph] the graph

# File lib/rugraph.rb, line 31
def load_from_vertices_hash(vertices_hash)
  @structure = vertices_hash
  self
end

neighbors_of(node) click to toggle source

Method returning the neighbors of a node.

@param node [Object] the value corresponding to a node in the graph @return [Array, nil] an array of its neighbors if the node exists,

nil otherwise

# File lib/rugraph.rb, line 78
def neighbors_of(node)
  return nil unless nodes.include?(node)
  @structure[node] || []
end

nodes() click to toggle source

(see vertices)

# File lib/rugraph.rb, line 210
def nodes
  vertices
end

order() click to toggle source

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

@return [Integer] the order of the graph.

# File lib/rugraph.rb, line 198
def order
  nodes.length
end

out_degree(node) click to toggle source

Computes the outcoming degree of a node.

@param (see degree) @return (see degree)

# File lib/rugraph.rb, line 191
def out_degree(node)
  @structure.count { |_source, dest| dest.include? node }
end

shortest_path_lengths(source) click to toggle source

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

@param source [Object] the value of the source node. @return [Hash] a hash of the lengths of shortest path to each other node.

# 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) click to toggle source

Computes the shortest path a node.

@param source [Object] the value of the source node. @return [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

# 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() click to toggle source

Returns the nodes in the graph

@return [Array] the values of all the nodes in the graph.

# File lib/rugraph.rb, line 205
def vertices
  (@structure.keys | @structure.values).flatten.uniq
end