class GraphMatching::Algorithm::MCMBipartite
`MCMBipartite` implements Maximum Cardinality Matching
in bipartite graphs.
Public Class Methods
new(graph)
click to toggle source
Calls superclass method
GraphMatching::Algorithm::MatchingAlgorithm::new
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 11 def initialize(graph) assert(graph).is_a(Graph::Bigraph) super end
Public Instance Methods
match()
click to toggle source
# 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
Private Instance Methods
assert_valid_aug_path(path)
click to toggle source
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 74 def assert_valid_aug_path(path) unless path.length >= 2 && path.length.even? raise 'Invalid augmenting path' end end
augment(m, path)
click to toggle source
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 80 def augment(m, path) assert_valid_aug_path(path) ix = 0 while ix < path.length i = path[ix] j = path[ix + 1] mi = m[i] mj = m[j] m[mi] = nil unless mi == nil m[mj] = nil unless mj == nil m[i] = j m[j] = i ix += 2 end m end
backtrack_from(end_vertex, predecessors)
click to toggle source
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 97 def backtrack_from(end_vertex, predecessors) augmenting_path = [end_vertex] while predecessors.key?(augmenting_path.last) augmenting_path.push(predecessors[augmenting_path.last]) end augmenting_path end
matched_adjacent(from, except, g, m)
click to toggle source
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 105 def matched_adjacent(from, except, g, m) g.adjacent_vertices(from).select { |i| i != except && m[from] == i } end
unlabeled_across_unmatched_edges_from(v, g, m, t)
click to toggle source
Look across unmatched edges from `v` to find vertexes not labeled `t`.
# File lib/graph_matching/algorithm/mcm_bipartite.rb, line 113 def unlabeled_across_unmatched_edges_from(v, g, m, t) g.adjacent_vertices(v).select { |i| m[v] != i && !t.include?(i) } end