Class: GraphMatching::Matching

Inherits:
Object
  • Object
show all
Defined in:
lib/graph_matching/matching.rb

Overview

> In .. graph theory, a matching .. in a graph is a set of > edges without common vertices. > en.wikipedia.org/wiki/Matching_%28graph_theory%29

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Matching

Returns a new instance of Matching.



49
50
51
 
# File 'lib/graph_matching/matching.rb', line 49

def initialize
  @ary = []
end

Class Method Details

.[](*edges) ⇒ Object 



45
46
47
 
# 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) ⇒ Object

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]`.



37
38
39
40
41
42
43
 
# 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) ⇒ Object

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.



14
15
16
17
18
19
20
21
22
23
24
 
# 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

Instance Method Details

#[](i) ⇒ Object 



53
54
55
 
# File 'lib/graph_matching/matching.rb', line 53

def [](i)
  @ary[i]
end

#add(e) ⇒ Object 



57
58
59
60
61
 
# File 'lib/graph_matching/matching.rb', line 57

def add(e)
  i, j = e
  @ary[i] = j
  @ary[j] = i
end

#delete(e) ⇒ Object 



63
64
65
66
67
 
# File 'lib/graph_matching/matching.rb', line 63

def delete(e)
  i, j = e
  @ary[i] = nil
  @ary[j] = nil
end

#edge?(e) ⇒ Boolean

Returns:

  • (Boolean) 


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

‘edges` returns an array of undirected edges, represented as two-element arrays.



71
72
73
 
# File 'lib/graph_matching/matching.rb', line 71

def edges
  undirected_edges.map(&:to_a)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @ary.all?(&:nil?)
end

#size ⇒ Object

‘size` returns number of edges



89
90
91
 
# File 'lib/graph_matching/matching.rb', line 89

def size
  @ary.compact.size / 2
end

#to_a ⇒ Object 



93
94
95
96
97
98
99
100
101
102
103
 
# 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 ⇒ Object 



110
111
112
113
114
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


84
85
86
 
# File 'lib/graph_matching/matching.rb', line 84

def vertex?(v)
  @ary.include?(v)
end

#vertexes ⇒ Object 



116
117
118
 
# File 'lib/graph_matching/matching.rb', line 116

def vertexes
  @ary.compact
end

#weight(g) ⇒ Object

Given a ‘Weighted` graph `g`, returns the sum of edge weights.



106
107
108
 
# File 'lib/graph_matching/matching.rb', line 106

def weight(g)
  edges.map { |e| g.w(e) }.reduce(0, :+)
end