class GraphMatching::Matching
> In .. graph theory, a matching .. in a graph is a set of > edges without common vertices. > en.wikipedia.org/wiki/Matching_%28graph_theory%29
Public Class Methods
# File lib/graph_matching/matching.rb, line 45 def self.[](*edges) new.tap { |m| edges.each { |e| m.add(e) } } end
Van Rantwijk's matching is constructed from two arrays, `mate` and `endpoint`.
-
`endpoint` is an array where each edge is represented by two consecutive elements, which are vertex numbers.
-
`mate` is an array whose indexes are vertex numbers, and whose values are `endpoint` indexes, or `nil` if the vertex is single (unmatched).
A matched vertex `v`'s partner is `endpoint[mate]`.
# File lib/graph_matching/matching.rb, line 37 def self.from_endpoints(endpoint, mate) m = Matching.new mate.each do |p| m.add([endpoint[p], endpoint[p ^ 1]]) unless p.nil? end m end
Gabow (1976) uses a simple array to store his matching. It has one element for each vertex in the graph. The value of each element is either the number of another vertex (Gabow uses sequential integers for vertex numbering) or a zero if unmatched. So, `.gabow` returns a `Matching` initialized from such an array.
# File lib/graph_matching/matching.rb, line 14 def self.gabow(mate) m = new mate.each_with_index do |n1, ix| next if n1.nil? || n1 == 0 n2 = mate[n1] if n2 == ix m.add([n1, n2]) end end m end
# File lib/graph_matching/matching.rb, line 49 def initialize @ary = [] end
Public Instance Methods
# File lib/graph_matching/matching.rb, line 53 def [](i) @ary[i] end
# File lib/graph_matching/matching.rb, line 57 def add(e) i, j = e @ary[i] = j @ary[j] = i end
# File lib/graph_matching/matching.rb, line 63 def delete(e) i, j = e @ary[i] = nil @ary[j] = nil end
# File lib/graph_matching/matching.rb, line 79 def edge?(e) i, j = e !@ary[i].nil? && @ary[i] == j && @ary[j] == i end
`edges` returns an array of undirected edges, represented as two-element arrays.
# File lib/graph_matching/matching.rb, line 71 def edges undirected_edges.map(&:to_a) end
# File lib/graph_matching/matching.rb, line 75 def empty? @ary.all?(&:nil?) end
`size` returns number of edges
# File lib/graph_matching/matching.rb, line 89 def size @ary.compact.size / 2 end
# File lib/graph_matching/matching.rb, line 93 def to_a result = [] skip = [] @ary.each_with_index { |e, i| unless e.nil? || skip.include?(i) result << [i, e] skip << e end } result end
# File lib/graph_matching/matching.rb, line 110 def undirected_edges @ary.each_with_index.inject(Set.new) { |set, (el, ix)| el.nil? ? set : set.add(RGL::Edge::UnDirectedEdge.new(el, ix)) } end
# File lib/graph_matching/matching.rb, line 84 def vertex?(v) @ary.include?(v) end
# File lib/graph_matching/matching.rb, line 116 def vertexes @ary.compact end
Given a `Weighted` graph `g`, returns the sum of edge weights.
# File lib/graph_matching/matching.rb, line 106 def weight(g) edges.map { |e| g.w(e) }.reduce(0, :+) end