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[v]].



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