Module: TournamentSystem::Algorithm::Matching

Extended by:
Matching
Included in:
Matching
Defined in:
lib/tournament_system/algorithm/matching.rb

Overview

Implements graph matching algorithms for tournament systems.

Instance Method Summary collapse

Instance Method Details

#all_perfect_matchings(array, size) ⇒ Enumerator<Array<element>> #all_perfect_matchings(array, size) {|group| ... } ⇒ nil

Iterate all perfect matchings of a specific size. A perfect matchings is a unique grouping of all elements with a specific group size.

Note that iterating all perfect matchings can be expensive. The total amount of matchings for size n is given by (n - 1)!!, a double factorial.

Examples:

all_perfect_matchings([1, 2, 3, 4]).includes?([[1, 2], [3, 4]]) #=> true

Overloads:

  • #all_perfect_matchings(array, size) ⇒ Enumerator<Array<element>>

    Returns enumerator for all perfect matches.

    Returns:

    • (Enumerator<Array<element>>)

      enumerator for all perfect matches

  • #all_perfect_matchings(array, size) {|group| ... } ⇒ nil

    Yield Parameters:

    • group (Array(element, size))

      a group of elements

    Returns:

    • (nil)

Parameters:

  • array (Array<element>)


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# File 'lib/tournament_system/algorithm/matching.rb', line 27

def all_perfect_matchings(array)
  return to_enum(:all_perfect_matchings, array) unless block_given?

  if array.empty?
    yield []
    return
  end

  array[1..-1].combination(1) do |group|
    group.unshift array[0]

    remaining = array.reject { |element| group.include?(element) }
    all_perfect_matchings(remaining) do |groups|
      yield [group] + groups
    end
  end
end

#maximum_weight_perfect_matching(array) {|first, second| ... } ⇒ Array<Array(element, element)>

Performs maximum weight perfect matching of a undirected complete graph composed of the given vertices.

The block is called for every edge in the complete graph.

Implementation performs in O(v^3 log v).

Parameters:

  • array (Array<element>)

Yield Parameters:

  • first (element)

    The first element of an edge to compute the weight of.

  • second (element)

    The second element of an edge to compute the weight of.

Returns:

  • (Array<Array(element, element)>)

    A perfect matching with maximum weight



56
57
58
59
60
61
62
63
64
65
66
67
68
69
# File 'lib/tournament_system/algorithm/matching.rb', line 56

def maximum_weight_perfect_matching(array, &block)
  edges = create_complete_graph(array, &block)
  graph = GraphMatching::Graph::WeightedGraph[*edges]

  # Get the maximum weighted maximum cardinality matching of the complete graph
  matching = graph.maximum_weighted_matching(true)

  # Converted matching back to input values (remember, indecies start from 1 in this case)
  matching.edges.map do |edge|
    edge.map do |index|
      array[index - 1]
    end
  end
end

#minimum_weight_perfect_matching(array) {|first, second| ... } ⇒ Array<Array(element, element)>

Identical to #maximum_weight_perfect_matching, except instead of maximizing weight it minimizes it.

This is simply achieved by negating the weight and then maximizing that.

Parameters:

  • array (Array<element>)

Yield Parameters:

  • first (element)

    The first element of an edge to compute the weight of.

  • second (element)

    The second element of an edge to compute the weight of.

Returns:

  • (Array<Array(element, element)>)

    A perfect matching with minimum weight



79
80
81
82
83
# File 'lib/tournament_system/algorithm/matching.rb', line 79

def minimum_weight_perfect_matching(array)
  maximum_weight_perfect_matching(array) do |first, second|
    -yield(first, second)
  end
end