class GraphMatching::Algorithm::MCMBipartite

`MCMBipartite` implements Maximum Cardinality Matching in bipartite graphs.

Public Class Methods

new(graph) click to toggle source
# 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