Module: GraphMatching::Graph::Weighted

Included in:
WeightedBigraph, WeightedGraph
Defined in:
lib/graph_matching/graph/weighted.rb

Overview

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.

Defined Under Namespace

Modules: ClassMethods

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.included(base) ⇒ Object 



28
29
30
31
32
33
 
# 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

Instance Method Details

#init_weights ⇒ Object 



75
76
77
 
# File 'lib/graph_matching/graph/weighted.rb', line 75

def init_weights
  @weight = Array.new(num_vertices) { |_| Array.new(num_vertices) }
end

#max_w ⇒ Object 



79
80
81
 
# 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) ⇒ Object

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



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# 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) ⇒ Object

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

Raises:

  • (ArgumentError) 


86
87
88
89
90
91
92
 
# 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