Module: TournamentSystem::Algorithm::Matching
Overview
Implements graph matching algorithms for tournament systems.
Instance Method Summary collapse
-
#all_perfect_matchings(array) ⇒ Object
Iterate all perfect matchings of a specific size.
-
#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.
-
#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.
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.
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).
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.
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 |