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
# 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
# File lib/graph_matching/graph/weighted.rb, line 75 def init_weights @weight = Array.new(num_vertices) { |_| Array.new(num_vertices) } end
# File lib/graph_matching/graph/weighted.rb, line 79 def max_w edges.map { |edge| w(edge.to_a) }.max end
`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
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