module GraphMatching::Graph::Weighted

The `Weighted` module is mixed into undirected graphs to support edge weights. Directed graphs are not supported.

Data Structure


Weights are stored in a 2D array. The weight of an edge i,j is stored twice, at `[i]` and `[j]`.

Storing the weight twice wastes memory. A symmetrical matrix can be stored in a 1D array (bit.ly/1DMfLM3) However, translating the 2D coordinates into a 1D index marginally increases the cost of access, and this is a read-heavy structure, so maybe the extra memory is an acceptable trade-off. It's also conceptually simpler, for what that's worth.

If directed graphs were supported (they are not) this 2D array would be an obvious choice.

Algorithms which operate on weighted graphs are tightly coupled to this data structure due to optimizations.

Public Class Methods

included(base) click to toggle source
# File lib/graph_matching/graph/weighted.rb, line 28
def self.included(base)
  base.extend ClassMethods
  base.class_eval do
    attr_accessor :weight
  end
end

Public Instance Methods

init_weights() click to toggle source
# File lib/graph_matching/graph/weighted.rb, line 75
def init_weights
  @weight = Array.new(num_vertices) { |_| Array.new(num_vertices) }
end
max_w() click to toggle source
# File lib/graph_matching/graph/weighted.rb, line 79
def max_w
  edges.map { |edge| w(edge.to_a) }.max
end
set_w(edge, weight) click to toggle source

`set_w` sets a single weight. It not efficient, and is only provided for situations where constructing the entire graph with `.[]` is not convenient.

# File lib/graph_matching/graph/weighted.rb, line 97
def set_w(edge, weight)
  if edge[0].nil? || edge[1].nil?
    raise ArgumentError, "Invalid edge: #{edge}"
  end
  unless weight.is_a?(Integer)
    raise TypeError, 'Edge weight must be integer'
  end
  init_weights if @weight.nil?
  i = edge[0] - 1
  j = edge[1] - 1
  raise "Edge not found: #{edge}" unless has_edge?(*edge)
  @weight[i] ||= []
  @weight[j] ||= []
  @weight[i][j] = weight
  @weight[j][i] = weight
end
w(edge) click to toggle source

Returns the weight of an edge. Accessing `#weight` is much faster, so this method should only be used where clarity outweighs performance.

# File lib/graph_matching/graph/weighted.rb, line 86
def w(edge)
  i, j = edge
  raise ArgumentError, "Invalid edge: #{edge}" if i.nil? || j.nil?
  raise "Edge not found: #{edge}" unless has_edge?(*edge)
  init_weights if @weight.nil?
  @weight[i - 1][j - 1]
end