Class: GraphMatching::Algorithm::MCMBipartite
- Inherits:
-
MatchingAlgorithm
- Object
- MatchingAlgorithm
- GraphMatching::Algorithm::MCMBipartite
- Defined in:
- lib/graph_matching/algorithm/mcm_bipartite.rb
Overview
‘MCMBipartite` implements Maximum Cardinality Matching in bipartite graphs.
Direct Known Subclasses
Instance Attribute Summary
Attributes inherited from MatchingAlgorithm
Instance Method Summary collapse
-
#initialize(graph) ⇒ MCMBipartite
constructor
A new instance of MCMBipartite.
- #match ⇒ Object
Methods inherited from MatchingAlgorithm
Constructor Details
#initialize(graph) ⇒ MCMBipartite
Returns a new instance of MCMBipartite.
11 12 13 14 |
# File 'lib/graph_matching/algorithm/mcm_bipartite.rb', line 11 def initialize(graph) assert(graph).is_a(Graph::Bigraph) super end |
Instance Method Details
#match ⇒ Object
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
# File 'lib/graph_matching/algorithm/mcm_bipartite.rb', line 16 def match u = g.partition[0] m = [] loop do # Begin each stage by clearing all labels and marks t = [] predecessors = {} aug_path = nil # Label unmatched vertexes in U with label R. r = u.select { |i| m[i] == nil } # These R-vertexes are candidates for the start of an augmenting path. unmarked = r.dup.to_a # While there are unmarked R-vertexes loop do break unless aug_path.nil? start = unmarked.pop break unless start # Follow the unmatched edges (if any) to vertexes in V # ignoring any V-vertexes already labeled T unlabeled_across_unmatched_edges_from(start, g, m, t).each do |vi| t << vi predecessors[vi] = start # If there are matched edges, follow each to a vertex # in U and label the U-vertex with R. Otherwise, # backtrack to construct an augmenting path. adj_u_in_m = matched_adjacent(vi, start, g, m) adj_u_in_m.each do |ui| r << ui unmarked << ui predecessors[ui] = vi end if adj_u_in_m.empty? aug_path = backtrack_from(vi, predecessors) break end end end if aug_path.nil? break else m = augment(m, aug_path) end end Matching.gabow(m) end |