module TournamentSystem::Algorithm::Matching

Implements graph matching algorithms for tournament systems.

Public Instance Methods

all_perfect_matchings(array) { || ... } click to toggle source

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.

@example

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

@param array [Array<element>] @overload all_perfect_matchings(array, size)

@return [Enumerator<Array<element>>] enumerator for all perfect matches

@overload all_perfect_matchings(array, size) { |group| … }

@yieldparam group [Array(element, size)] a group of elements
@return [nil]
# 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, &block) click to toggle source

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)+.

@param array [Array<element>] @yieldparam first [element] The first element of an edge to compute the weight of. @yieldparam second [element] The second element of an edge to compute the weight of. @return [Array<Array(element, element)>] A perfect matching with maximum weight

# 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| ... } click to toggle source

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.

@param array [Array<element>] @yieldparam first [element] The first element of an edge to compute the weight of. @yieldparam second [element] The second element of an edge to compute the weight of. @return [Array<Array(element, element)>] A perfect matching with minimum weight

# 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

Private Instance Methods

create_complete_graph(array) { |first, second| ... } click to toggle source

Construct a complete graph from element indecies (starting from 1)

# File lib/tournament_system/algorithm/matching.rb, line 88
def create_complete_graph(array)
  edges = []

  array.each.with_index do |first, first_index|
    next_index = first_index + 1

    array[next_index..array.length].each.with_index do |second, second_index|
      second_index += next_index

      edges << [next_index, second_index + 1, yield(first, second)]
    end
  end

  edges
end