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

[](*edges) click to toggle source
# File lib/graph_matching/matching.rb, line 45
def self.[](*edges)
  new.tap { |m| edges.each { |e| m.add(e) } }
end
from_endpoints(endpoint, mate) click to toggle source

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

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
new() click to toggle source
# File lib/graph_matching/matching.rb, line 49
def initialize
  @ary = []
end

Public Instance Methods

[](i) click to toggle source
# File lib/graph_matching/matching.rb, line 53
def [](i)
  @ary[i]
end
add(e) click to toggle source
# File lib/graph_matching/matching.rb, line 57
def add(e)
  i, j = e
  @ary[i] = j
  @ary[j] = i
end
delete(e) click to toggle source
# File lib/graph_matching/matching.rb, line 63
def delete(e)
  i, j = e
  @ary[i] = nil
  @ary[j] = nil
end
edge?(e) click to toggle source
# 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() click to toggle source

`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
empty?() click to toggle source
# File lib/graph_matching/matching.rb, line 75
def empty?
  @ary.all?(&:nil?)
end
size() click to toggle source

`size` returns number of edges

# File lib/graph_matching/matching.rb, line 89
def size
  @ary.compact.size / 2
end
to_a() click to toggle source
# 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
undirected_edges() click to toggle source
# 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
vertex?(v) click to toggle source
# File lib/graph_matching/matching.rb, line 84
def vertex?(v)
  @ary.include?(v)
end
vertexes() click to toggle source
# File lib/graph_matching/matching.rb, line 116
def vertexes
  @ary.compact
end
weight(g) click to toggle source

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