class GraphMatching::Algorithm::MWMGeneral

`MWMGeneral` implements Maximum Weighted Matching in general graphs.

Constants

LBL_CRUMB
LBL_FREE

If b is a top-level blossom, label is 0 if b is unlabeled (free);

1 if b is an S-vertex/blossom;
2 if b is a T-vertex/blossom.
LBL_NAMES
LBL_S
LBL_T

Public Class Methods

new(graph) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 22
def initialize(graph)
  assert(graph).is_a(Graph::WeightedGraph)
  super
  init_graph_structures
  init_algorithm_structures
end

Public Instance Methods

match(max_cardinality) click to toggle source

> As in Problem 3, the algorithm consists of O(n) stages. > In each stage we look for an augmenting path using the > labeling R12 and the two cases C1, C2 as in the simple > algorithm for Problem 2, except that we only use edges > with π<sub>ij</sub> = 0. (Galil, 1986, p. 32)

Van Rantwijk's implementation (and, consequently, this port) supports both maximum cardinality maximum weight matching and MWM irrespective of cardinality.

# File lib/graph_matching/algorithm/mwm_general.rb, line 38
def match(max_cardinality)
  return Matching.new if g.num_edges == 0

  # Iterative *stages*.  Each stage augments the matching.
  # There can be at most n stages, where n is num. vertexes.
  loop do
    init_stage

    # *sub-stages* either augment or scale the duals.
    augmented = false
    loop do
      # > The search is conducted by scanning the S-vertices
      # > in turn. (Galil, 1986, p. 26)
      until augmented || @queue.empty?
        augmented = scan_vertex(@queue.pop)
      end

      break if augmented

      # > There is no augmenting path under these constraints;
      # > compute delta and reduce slack in the optimization problem.
      # > (Van Rantwijk, mwmatching.py, line 732)
      delta, d_type, d_edge, d_blossom = calc_delta(max_cardinality)
      update_duals(delta)
      optimum = act_on_minimum_delta(d_type, d_edge, d_blossom)
      break if optimum
    end

    # > Stop when no more augmenting path can be found.
    # > (Van Rantwijk, mwmatching.py)
    break unless augmented

    expand_tight_s_blossoms
  end

  Matching.from_endpoints(@endpoint, @mate)
end

Private Instance Methods

act_on_minimum_delta(delta_type, delta_edge, delta_blossom) click to toggle source

> Take action at the point where minimum delta occurred. > (Van Rantwijk, mwmatching.py)

# File lib/graph_matching/algorithm/mwm_general.rb, line 80
def act_on_minimum_delta(delta_type, delta_edge, delta_blossom)
  optimum = false
  case delta_type
  when 1
    # > No further improvement possible; optimum reached.
    optimum = true
  when 2
    # > Use the least-slack edge to continue the search.
    @tight_edge[delta_edge] = true
    i, j = @edges[delta_edge].to_a
    if @label[@in_blossom[i]] == LBL_FREE
      # Think of this as swapping i and j, but the corresponding
      # assignment `j = i` happens to be unnecessary.
      i = j
    end
    assert_label(@in_blossom[i], LBL_S)
    @queue.push(i)
  when 3
    # > Use the least-slack edge to continue the search.
    @tight_edge[delta_edge] = true
    i = @edges[delta_edge].to_a[0]
    assert_label(@in_blossom[i], LBL_S)
    @queue.push(i)
  when 4
    # > Expand the least-z blossom.
    expand_blossom(delta_blossom, false)
  else
    raise "Invalid delta_type: #{delta_type}"
  end
  optimum
end
add_blossom(base, k) click to toggle source

> Construct a new blossom with given base, containing edge > k which connects a pair of S vertices. Label the new > blossom as S; set its dual variable to zero; relabel its > T-vertices to S and add them to the queue. > (Van Rantwijk, mwmatching.py, line 270)

# File lib/graph_matching/algorithm/mwm_general.rb, line 117
def add_blossom(base, k)
  v, w = @edges[k].to_a
  bb = @in_blossom[base]
  bv = @in_blossom[v]
  bw = @in_blossom[w]

  # Create a new top-level blossom.
  b = @unused_blossoms.pop
  @blossom_base[b] = base
  @blossom_parent[b] = nil
  @blossom_parent[bb] = b

  # > Make list of sub-blossoms and their interconnecting
  # > edge endpoints.
  # > (Van Rantwijk, mwmatching.py, line 284)
  #
  # 1. Clear the existing lists
  # 2. Trace back from v to base
  # 3. Reverse lists, add endpoint that connects the pair of S vertices
  # 4. Trace back from w to base
  #
  @blossom_children[b] = []
  @blossom_endps[b] = []
  trace_to_base(bv, bb) do |bv2|
    @blossom_parent[bv2] = b
    @blossom_children[b] << bv2
    @blossom_endps[b] << @label_end[bv2]
  end
  @blossom_children[b] << bb
  @blossom_children[b].reverse!
  @blossom_endps[b].reverse!
  @blossom_endps[b] << 2 * k
  trace_to_base(bw, bb) do |bw2|
    @blossom_parent[bw2] = b
    @blossom_children[b] << bw2
    @blossom_endps[b] << (@label_end[bw2] ^ 1)
  end

  # > Set label to S
  assert(@label[bb]).eq(LBL_S)
  @label[b] = LBL_S
  @label_end[b] = @label_end[bb]

  # > Set dual variable to zero.
  @dual[b] = 0

  # > Relabel vertices.
  blossom_leaves(b).each do |leaf|
    if @label[@in_blossom[leaf]] == LBL_T
      # > This T-vertex now turns into an S-vertex because it
      # > becomes part of an S-blossom; add it to the queue.
      @queue << leaf
    end
    @in_blossom[leaf] = b
  end

  # > Compute blossombestedges[b].
  best_edge_to = rantwijk_array(nil)
  @blossom_children[b].each do |child|
    if @blossom_best_edges[child].nil?
      # > This subblossom [bv] does not have a list of least-
      # > slack edges.  Get the information from the vertices.
      nblists = blossom_leaves(child).map { |leaf|
        @neighb_end[leaf].map { |p|
          p / 2 # Intentional floor division
        }
      }
    else
      # > Walk this subblossom's least-slack edges.
      nblists = [@blossom_best_edges[child]]
    end

    nblists.each do |nblist|
      nblist.each do |x|
        i, j = @edges[x].to_a
        if @in_blossom[j] == b
          # Think of this as swapping i and j, but the corresponding
          # assignment `i = j` happens to be unnecessary.
          j = i
        end
        bj = @in_blossom[j]
        if better_edge_to?(bj, x, b, best_edge_to)
          best_edge_to[bj] = x
        end
      end
    end

    # > Forget about least-slack edges of the subblossom.
    @blossom_best_edges[child] = nil
    @best_edge[child] = nil
  end

  @blossom_best_edges[b] = best_edge_to.compact

  # > Select bestedge[b]
  @best_edge[b] = nil
  @blossom_best_edges[b].each do |edge|
    if @best_edge[b].nil? || slack(edge) < slack(@best_edge[b])
      @best_edge[b] = edge
    end
  end
end
assert_blossom_trace(b) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 220
      def assert_blossom_trace(b)
        t = @label[b] == LBL_T
        s = @label[b] == LBL_S
        m = @label_end[b] == @mate[@blossom_base[b]]
        unless t || s && m
          raise <<-EOS
              Assertion failed: Expected either:
              1. Current Bv to be a T-blossom, or
              2. Bv is an S-blossom and its base is matched to @label_end[bv]
          EOS
        end
      end
assert_label(ix, lbl) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 233
def assert_label(ix, lbl)
  unless @label[ix] == lbl
    raise "Expected label at #{ix} to be #{LBL_NAMES[lbl]}"
  end
end
assign_label(w, t, p = nil) click to toggle source

> Assign label t to the top-level blossom containing vertex w > and record the fact that w was reached through the edge with > remote endpoint p. > (Van Rantwijk, mwmatching.py)

# File lib/graph_matching/algorithm/mwm_general.rb, line 244
def assign_label(w, t, p = nil)
  b = @in_blossom[w]
  assert_label(w, LBL_FREE)
  assert_label(b, LBL_FREE)
  @label[w] = @label[b] = t
  @label_end[w] = @label_end[b] = p
  @best_edge[w] = @best_edge[b] = nil
  if t == LBL_S
    # b became an S-vertex/blossom; add it(s vertices) to the queue.
    @queue.concat(blossom_leaves(b))
  elsif t == LBL_T
    # b became a T-vertex/blossom; assign label S to its mate.
    # (If b is a non-trivial blossom, its base is the only vertex
    # with an external mate.)
    base = @blossom_base[b]
    if @mate[base].nil?
      raise "Expected blossom #{b}'s base (#{base}) to be matched"
    end

    # Assign label S to the mate of blossom b's base.
    # Remember, `mate` elements are pointers to "endpoints".
    # The bitwise XOR is very clever. `mate[x]` and `mate[x] ^ 1`
    # are connected "endpoints".
    base_edge_endpoints = [@mate[base], @mate[base] ^ 1]
    assign_label(
      @endpoint[base_edge_endpoints[0]],
      LBL_S,
      base_edge_endpoints[1]
    )
  else
    raise ArgumentError, "Unexpected label: #{t}"
  end
end
augment_blossom(b, v) click to toggle source

> Swap matched/unmatched edges over an alternating path > through blossom b between vertex v and the base vertex. > Keep blossom bookkeeping consistent. > (Van Rantwijk, mwmatching.py, line 448)

# File lib/graph_matching/algorithm/mwm_general.rb, line 282
def augment_blossom(b, v)
  t = immediate_subblossom_of(b, v)

  # > Recursively deal with the first sub-blossom.
  if t >= @nvertex
    augment_blossom(t, v)
  end

  # > Move along the blossom until we get to the base.
  j, jstep, endptrick = blossom_loop_direction(b, t)
  i = j
  while j != 0
    # > Step to the next sub-blossom and augment it recursively.
    j += jstep
    p = @blossom_endps[b][j - endptrick] ^ endptrick
    x = @endpoint[p]
    augment_blossom_step(b, j, x)

    # > Step to the next sub-blossom and augment it recursively.
    j += jstep
    x = @endpoint[p ^ 1]
    augment_blossom_step(b, j, x)

    # > Match the edge connecting those sub-blossoms.
    match_endpoint(p)
  end

  # > Rotate the list of sub-blossoms to put the new base at
  # > the front.
  @blossom_children[b].rotate!(i)
  @blossom_endps[b].rotate!(i)
  @blossom_base[b] = @blossom_base[@blossom_children[b][0]]
  assert(@blossom_base[b]).eq(v)
end
augment_blossom_step(b, j, x) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 317
def augment_blossom_step(b, j, x)
  t = @blossom_children[b][j]
  if t >= @nvertex
    augment_blossom(t, x)
  end
end
augment_matching(k) click to toggle source

> Swap matched/unmatched edges over an alternating path > between two single vertices. The augmenting path runs > through edge k, which connects a pair of S vertices. > (Van Rantwijk, mwmatching.py, line 494)

# File lib/graph_matching/algorithm/mwm_general.rb, line 328
def augment_matching(k)
  v, w = @edges[k].to_a
  [[v, 2 * k + 1], [w, 2 * k]].each do |(s, p)|
    # > Match vertex s to remote endpoint p. Then trace back from s
    # > until we find a single vertex, swapping matched and unmatched
    # > edges as we go.
    # > (Van Rantwijk, mwmatching.py, line 504)
    loop do
      bs = @in_blossom[s]
      assert_label(bs, LBL_S)
      assert(@label_end[bs]).eq(@mate[@blossom_base[bs]])
      # > Augment through the S-blossom from s to base.
      if bs >= @nvertex
        augment_blossom(bs, s)
      end
      @mate[s] = p
      # > Trace one step back.
      # If we reach a single vertex, stop
      break if @label_end[bs].nil?
      t = @endpoint[@label_end[bs]]
      bt = @in_blossom[t]
      assert_label(bt, LBL_T)
      # > Trace one step back.
      assert(@label_end[bt]).not_nil
      s = @endpoint[@label_end[bt]]
      j = @endpoint[@label_end[bt] ^ 1]
      # > Augment through the T-blossom from j to base.
      assert(@blossom_base[bt]).eq(t)
      if bt >= @nvertex
        augment_blossom(bt, j)
      end
      @mate[j] = @label_end[bt]
      # > Keep the opposite endpoint;
      # > it will be assigned to mate[s] in the next step.
      p = @label_end[bt] ^ 1
    end
  end
end
better_edge_to?(bj, k, b, best_edge_to) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 367
def better_edge_to?(bj, k, b, best_edge_to)
  bj != b &&
    @label[bj] == LBL_S &&
    (best_edge_to[bj] == nil || slack(k) < slack(best_edge_to[bj]))
end
blossom_leaves(b, ary = []) click to toggle source

TODO: Optimize by returning lazy iterator

# File lib/graph_matching/algorithm/mwm_general.rb, line 374
def blossom_leaves(b, ary = [])
  if b < @nvertex
    ary.push(b)
  else
    @blossom_children[b].each do |c|
      if c < @nvertex
        ary.push(c)
      else
        ary.concat(blossom_leaves(c))
      end
    end
  end
  ary
end
blossom_loop_direction(b, t) click to toggle source

> Decide in which direction we will go round the blossom. > (Van Rantwijk, mwmatching.py, lines 385, 460)

# File lib/graph_matching/algorithm/mwm_general.rb, line 391
def blossom_loop_direction(b, t)
  j = @blossom_children[b].index(t)
  if j.odd?
    # > go forward and wrap
    j -= @blossom_children[b].length
    jstep = 1
    endptrick = 0
  else
    # > go backward
    jstep = -1
    endptrick = 1
  end
  [j, jstep, endptrick]
end
calc_delta(max_cardinality) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 406
def calc_delta(max_cardinality)
  delta = nil
  delta_type = nil
  delta_edge = nil
  delta_blossom = nil

  # > Compute delta1: the minumum value of any vertex dual.
  # > (Van Rantwijk, mwmatching.py)
  unless max_cardinality
    delta_type = 1
    delta = @dual[0, @nvertex].min
  end

  # > Compute delta2: the minimum slack on any edge between
  # > an S-vertex and a free vertex.
  # > (Van Rantwijk, mwmatching.py)
  (0...@nvertex).each do |v|
    next unless @label[@in_blossom[v]] == LBL_FREE && !@best_edge[v].nil?
    d = slack(@best_edge[v])
    next unless delta_type == nil || d < delta
    delta = d
    delta_type = 2
    delta_edge = @best_edge[v]
  end

  # > Compute delta3: half the minimum slack on any edge between
  # > a pair of S-blossoms.
  # > (Van Rantwijk, mwmatching.py)
  (0...2 * @nvertex).each do |b|
    unless @blossom_parent[b].nil? &&
        @label[b] == LBL_S &&
        !@best_edge[b].nil?
      next
    end
    kslack = slack(@best_edge[b])
    d = kslack / 2 # Van Rantwijk had some type checking here.  Why?
    next unless delta_type.nil? || d < delta
    delta = d
    delta_type = 3
    delta_edge = @best_edge[b]
  end

  # > Compute delta4: minimum z variable of any T-blossom.
  # > (Van Rantwijk, mwmatching.py)
  (@nvertex...2 * @nvertex).each do |b|
    top_t_blossom = top_level_blossom?(b) && @label[b] == LBL_T
    next unless top_t_blossom && (delta_type.nil? || @dual[b] < delta)
    delta = @dual[b]
    delta_type = 4
    delta_blossom = b
  end

  if delta_type.nil?
    # > No further improvement possible; max-cardinality optimum
    # > reached. Do a final delta update to make the optimum
    # > verifyable.
    # > (Van Rantwijk, mwmatching.py)
    assert(max_cardinality).eq(true)
    delta_type = 1
    delta = [0, @dual[0, @nvertex].min].max
  end

  [delta, delta_type, delta_edge, delta_blossom]
end
calc_slack(k) click to toggle source

Returns nil if `k` is known to be an endpoint of a tight edge. Otherwise, calculates and returns the slack of `k`, and updates the `tight_edge` cache.

# File lib/graph_matching/algorithm/mwm_general.rb, line 474
def calc_slack(k)
  if @tight_edge[k]
    nil
  else
    kslack = slack(k)
    if kslack <= 0
      @tight_edge[k] = true
    end
    kslack
  end
end
consider_loose_edge_to_free_vertex(w, k, kslack) click to toggle source

> w is a free vertex (or an unreached vertex inside > a T-blossom) but we can not reach it yet; > keep track of the least-slack edge that reaches w. > (Van Rantwijk, mwmatching.py, line 725)

# File lib/graph_matching/algorithm/mwm_general.rb, line 490
def consider_loose_edge_to_free_vertex(w, k, kslack)
  if @best_edge[w].nil? || kslack < slack(@best_edge[w])
    @best_edge[w] = k
  end
end
consider_loose_edge_to_s_blossom(v, k, kslack) click to toggle source

While scanning neighbors of `v`, a loose edge to an S-blossom is found, and the `@best_edge` cache may be updated.

> keep track of the least-slack non-allowable [loose] edge > to a different S-blossom. > (Van Rantwijk, mwmatching.py, line 717)

# File lib/graph_matching/algorithm/mwm_general.rb, line 504
def consider_loose_edge_to_s_blossom(v, k, kslack)
  b = @in_blossom[v]
  if @best_edge[b].nil? || kslack < slack(@best_edge[b])
    @best_edge[b] = k
  end
end
consider_tight_edge(k, w, p, v) click to toggle source

> If we scan the S-vertex i and consider the edge (i,j), > there are two cases: > > * (C1) j is free; or > * (C2) j is an S-vertex > > C2 cannot occur in the bipartite case. The case in > which j is a T-vertex is discarded. > (Galil, 1986, p. 26-27)

# File lib/graph_matching/algorithm/mwm_general.rb, line 521
def consider_tight_edge(k, w, p, v)
  augmented = false

  if @label[@in_blossom[w]] == LBL_FREE

    # > (C1) w is a free vertex;
    # > label w with T and label its mate with S (R12).
    # > (Van Rantwijk, mwmatching.py, line 690)
    #
    # > In case C1 we apply R12. (Galil, 1986, p. 27)
    #
    # > * (R1) If (i, j) is not matched and i is an S-person
    # >   and j a free (unlabeled) person then label j by T; and
    # > * (R2) If (i, j) is matched and j is a T-person
    # >   and i a free person, then label i by S.
    # >
    # > Modified from (Galil, 1986, p. 25) as follows:
    #
    # > Any time R1 is used and j is labeled by T, R2 is
    # > immediately used to label the spouse of j with S.
    # > (Since j was not labeled before, it must be married
    # > and its spouse must be unlabeled.)  We call this
    # > rule R12. (Galil, 1986, p. 26)
    #
    assign_label(w, LBL_T, p ^ 1)

  elsif @label[@in_blossom[w]] == LBL_S

    # > (C2) w is an S-vertex (not in the same blossom);
    # > follow back-links to discover either an
    # > augmenting path or a new blossom.
    # > (Van Rantwijk, mwmatching.py, line 694)
    #
    base = scan_blossom(v, w)
    if base.nil?
      # > Found an augmenting path; augment the
      # > matching and end this stage.
      # > (Van Rantwijk, mwmatching.py, line 703)
      augment_matching(k)
      augmented = true
    else
      # > Found a new blossom; add it to the blossom
      # > bookkeeping and turn it into an S-blossom.
      # > (Van Rantwijk, mwmatching.py, line 699)
      add_blossom(base, k)
    end

  elsif @label[w] == LBL_FREE

    # > w is inside a T-blossom, but w itself has not
    # > yet been reached from outside the blossom;
    # > mark it as reached (we need this to relabel
    # > during T-blossom expansion).
    # > (Van Rantwijk, mwmatching.py, line 709)
    #
    assert_label(@in_blossom[w], LBL_T)
    @label[w] = LBL_T
    @label_end[w] = p ^ 1

  end

  augmented
end
expand_blossom(b, endstage) click to toggle source

> Expand the given top-level blossom. > (Van Rantwijk, mwmatching.py, line 361)

Blossoms are expanded during slack adjustment delta type 4, and after all stages are complete (endstage will be true).

# File lib/graph_matching/algorithm/mwm_general.rb, line 591
def expand_blossom(b, endstage)
  promote_sub_blossoms_of(b, endstage)

  # > If we expand a T-blossom during a stage, its sub-blossoms
  # > must be relabeled.
  if !endstage && @label[b] == LBL_T
    expand_t_blossom(b)
  end

  recycle_blossom_number(b)
end
expand_t_blossom(b) click to toggle source

> Start at the sub-blossom through which the expanding > blossom obtained its label, and relabel sub-blossoms until > we reach the base. > Figure out through which sub-blossom the expanding blossom > obtained its label initially. > (Van Rantwijk, mwmatching.py, line 378)

# File lib/graph_matching/algorithm/mwm_general.rb, line 609
def expand_t_blossom(b)
  assert(@label_end[b]).not_nil
  entry_child = @in_blossom[@endpoint[@label_end[b] ^ 1]]

  # > Move along the blossom until we get to the base.
  j, jstep, endptrick = blossom_loop_direction(b, entry_child)
  p = @label_end[b]
  while j != 0

    # > Relabel the T-sub-blossom.
    @label[@endpoint[p ^ 1]] = LBL_FREE
    @label[
      @endpoint[@blossom_endps[b][j - endptrick] ^ endptrick ^ 1]
    ] = LBL_FREE
    assign_label(@endpoint[p ^ 1], LBL_T, p)

    # > Step to the next S-sub-blossom and note its forward endpoint.
    # Intentional floor division
    @tight_edge[@blossom_endps[b][j - endptrick] / 2] = true
    j += jstep
    p = @blossom_endps[b][j - endptrick] ^ endptrick

    # > Step to the next T-sub-blossom.
    # Intentional floor division
    @tight_edge[p / 2] = true
    j += jstep
  end

  # > Relabel the base T-sub-blossom WITHOUT stepping through to
  # > its mate (so don't call assignLabel).
  bv = @blossom_children[b][j]
  @label[@endpoint[p ^ 1]] = @label[bv] = LBL_T
  @label_end[@endpoint[p ^ 1]] = @label_end[bv] = p
  @best_edge[bv] = nil

  # > Continue along the blossom until we get back to entrychild.
  j += jstep
  while @blossom_children[b][j] != entry_child

    # > Examine the vertices of the sub-blossom to see whether
    # > it is reachable from a neighbouring S-vertex outside the
    # > expanding blossom.
    bv = @blossom_children[b][j]
    if @label[bv] == LBL_S
      # > This sub-blossom just got label S through one of its
      # > neighbours; leave it.
      j += jstep
      next
    end

    # > If the sub-blossom contains a reachable vertex, assign
    # > label T to the sub-blossom.
    v = first_labeled_blossom_leaf(bv)
    unless v.nil?
      assert_label(v, LBL_T)
      assert(@in_blossom[v]).eq(bv)
      @label[v] = LBL_FREE
      @label[@endpoint[@mate[@blossom_base[bv]]]] = LBL_FREE
      assign_label(v, LBL_T, @label_end[v])
    end

    j += jstep
  end
end
expand_tight_s_blossoms() click to toggle source

> End of a stage; expand all S-blossoms which have dualvar = 0. > (Van Rantwijk, mwmatching.py)

# File lib/graph_matching/algorithm/mwm_general.rb, line 676
def expand_tight_s_blossoms
  (@nvertex...2 * @nvertex).each do |b|
    if top_level_blossom?(b) && @label[b] == LBL_S && @dual[b] == 0
      expand_blossom(b, true)
    end
  end
end
first_labeled_blossom_leaf(b) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 684
def first_labeled_blossom_leaf(b)
  blossom_leaves(b).find { |leaf| @label[leaf] != LBL_FREE }
end
immediate_subblossom_of(b, v) click to toggle source

Starting from a vertex `v`, ascend the blossom tree, and return the sub-blossom immediately below `b`.

# File lib/graph_matching/algorithm/mwm_general.rb, line 690
def immediate_subblossom_of(b, v)
  t = v
  while @blossom_parent[t] != b
    t = @blossom_parent[t]
  end
  t
end
init_algorithm_structures() click to toggle source

Data structures used throughout the algorithm.

# File lib/graph_matching/algorithm/mwm_general.rb, line 699
def init_algorithm_structures
  # > If v is a vertex,
  # > mate[v] is the remote endpoint of its matched edge, or -1 if it is
  # > single (i.e. endpoint[mate[v]] is v's partner vertex).
  # > Initially all vertices are single; updated during augmentation.
  # > (Van Rantwijk, mwmatching.py)
  @mate = Array.new(@nvertex, nil)

  # > If b is a top-level blossom,
  # > label[b] is 0 if b is unlabeled (free);
  # >             1 if b is an S-vertex/blossom;
  # >             2 if b is a T-vertex/blossom.
  # > The label of a vertex is found by looking at the label of its
  # > top-level containing blossom.
  # > If v is a vertex inside a T-blossom, label[v] is 2 iff v is
  # > reachable from an S-vertex outside the blossom. Labels are assigned
  # > during a stage and reset after each augmentation.
  # > (Van Rantwijk, mwmatching.py)
  @label = rantwijk_array(LBL_FREE)

  # > If b is a labeled top-level blossom, labelend[b] is the remote
  # > endpoint of the edge through which b obtained its label, or -1 if
  # > b's base vertex is single. If v is a vertex inside a T-blossom and
  # > label[v] == 2, labelend[v] is the remote endpoint of the edge
  # > through which v is reachable from outside the blossom. (Van
  # > Rantwijk, mwmatching.py)
  @label_end = rantwijk_array(nil)

  # > If v is a vertex, inblossom[v] is the top-level blossom to which v
  # > belongs. If v is a top-level vertex, v is itself a blossom (a
  # > trivial blossom) and inblossom[v] == v. Initially all vertices are
  # > top-level trivial blossoms. (Van Rantwijk, mwmatching.py)
  @in_blossom = (0...@nvertex).to_a

  # > If b is a sub-blossom, blossomparent[b] is its immediate parent
  # > (sub-)blossom. If b is a top-level blossom, blossomparent[b] is -1.
  # > (Van Rantwijk, mwmatching.py)
  @blossom_parent = rantwijk_array(nil)

  # A 2D array representing a tree of blossoms.
  #
  # > The blossom structure of a graph is represented by a
  # > *blossom tree*.  Its nodes are the graph G, the blossoms
  # > of G, and all vertices included in blossoms.  The root is
  # > G, whose children are the maximal blossoms.  ..  Any
  # > vertex is a leaf.
  # > (Gabow, 1985, p. 91)
  #
  # Van Rantwijk implements the blossom tree with an array in
  # two halves.  The first half is "trivial" blossoms, vertexes,
  # the leaves of the tree.  The second half are non-trivial blossoms.
  #
  # > Vertices are numbered 0 .. (nvertex-1).
  # > Non-trivial blossoms are numbered nvertex .. (2*nvertex-1)
  # > (Van Rantwijk, mwmatching.py, line 58)
  #
  # > If b is a non-trivial (sub-)blossom, blossomchilds[b]
  # > is an ordered list of its sub-blossoms, starting with
  # > the base and going round the blossom.
  # > (Van Rantwijk, mwmatching.py, line 144)
  #
  @blossom_children = rantwijk_array(nil)

  # > If b is a (sub-)blossom,
  # > blossombase[b] is its base VERTEX (i.e. recursive sub-blossom).
  # > (Van Rantwijk, mwmatching.py, line 153)
  #
  @blossom_base = (0...@nvertex).to_a + Array.new(@nvertex, nil)

  # > If b is a non-trivial (sub-)blossom,
  # > blossomendps[b] is a list of endpoints on its connecting edges,
  # > such that blossomendps[b][i] is the local endpoint of
  # > blossomchilds[b][i] on the edge that connects it to
  # > blossomchilds[b][wrap(i+1)].
  # > (Van Rantwijk, mwmatching.py, line 147)
  #
  @blossom_endps = rantwijk_array(nil)

  # > If v is a free vertex (or an unreached vertex inside a T-blossom),
  # > bestedge[v] is the edge to an S-vertex with least slack,
  # > or -1 if there is no such edge.
  # > If b is a (possibly trivial) top-level S-blossom,
  # > bestedge[b] is the least-slack edge to a different S-blossom,
  # > or -1 if there is no such edge.
  # > This is used for efficient computation of delta2 and delta3.
  # > (Van Rantwijk, mwmatching.py)
  #
  @best_edge = rantwijk_array(nil)

  # > If b is a non-trivial top-level S-blossom,
  # > blossombestedges[b] is a list of least-slack edges to neighbouring
  # > S-blossoms, or None if no such list has been computed yet.
  # > This is used for efficient computation of delta3.
  # > (Van Rantwijk, mwmatching.py, line 168)
  #
  @blossom_best_edges = rantwijk_array(nil)

  # > List of currently unused blossom numbers.
  # > (Van Rantwijk, mwmatching.py, line 174)
  @unused_blossoms = (@nvertex...2 * @nvertex).to_a

  # > If v is a vertex,
  # > dualvar[v] = 2 * u(v) where u(v) is the v's variable in the dual
  # > optimization problem (multiplication by two ensures integer values
  # > throughout the algorithm if all edge weights are integers).
  # > If b is a non-trivial blossom, dualvar[b] = z(b)
  # > where z(b) is b's variable in the dual optimization
  # > problem. (Van Rantwijk, mwmatching.py, line 177)
  #
  @dual = Array.new(@nvertex, g.max_w) + Array.new(@nvertex, 0)

  # Optimization: Cache of tight (zero slack) edges.  *Tight*
  # is a term I attribute to Gabow, though it may be earlier.
  #
  # > Edge ij is *tight* if equality holds in [its dual
  # > value function]. (Gabow, 1985, p. 91)
  #
  # Van Rantwijk calls this cache `allowedge`, denoting its use
  # in the algorithm.
  #
  # > If allowedge[k] is true, edge k has zero slack in the optimization
  # > problem; if allowedge[k] is false, the edge's slack may or may not
  # > be zero.
  @tight_edge = Array.new(@edges.length, false)

  # Queue of newly discovered S-vertices.
  @queue = []
end
init_graph_structures() click to toggle source

Builds data structures about the graph. These structures are not modified by the algorithm.

# File lib/graph_matching/algorithm/mwm_general.rb, line 830
def init_graph_structures
  @weight = g.weight

  # The size of the array (or part of an array) used for
  # vertexes (as opposed to blossoms) throughout this
  # algorithm.  It is *not*, as one might assume from the
  # name, the number of vertexes in the graph.
  @nvertex = g.max_v.to_i + 1

  # Make a local copy of the edges.  We'll refer to edges
  # by number throughout throughout the algorithm and it's
  # important that the order be consistent.
  @edges = g.edges.map { |e| [e.source, e.target] }

  # In Joris van Rantwijk's implementation, there seems to be
  # a concept of "edge numbers".  His `endpoint` array has two
  # elements for each edge.  His `mate` array "points to" his
  # `endpoint` array.  (See below)  I'm sure there's a reason,
  # but I don't understand yet.
  #
  # > If p is an edge endpoint, endpoint[p] is the vertex to
  # > which endpoint p is attached.  Not modified by the
  # > algorithm. (Van Rantwijk, mwmatching.py, line 93)
  @endpoint = @edges.flatten

  # > If v is a vertex, neighbend[v] is the list of remote
  # > endpoints of the edges attached to v.  Not modified by
  # > the algorithm. (Van Rantwijk, mwmatching.py, line 98)
  @neighb_end = init_neighb_end(@nvertex, @edges)
end
init_neighb_end(nvertex, edges) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 861
def init_neighb_end(nvertex, edges)
  neighb_end = Array.new(nvertex) { [] }
  edges.each_with_index do |(i, j), k|
    neighb_end[i].push(2 * k + 1)
    neighb_end[j].push(2 * k)
  end
  neighb_end
end
init_stage() click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 870
def init_stage
  init_stage_caches
  @queue = []
  init_stage_labels
end
init_stage_caches() click to toggle source

Clear the Van Rantwijk “best edge” caches

# File lib/graph_matching/algorithm/mwm_general.rb, line 877
def init_stage_caches
  @best_edge = rantwijk_array(nil)
  @blossom_best_edges.fill(nil, @nvertex)
  @tight_edge = Array.new(@edges.length, false)
end
init_stage_labels() click to toggle source

> We start by labeling all single persons S > (Galil, 1986, p. 26)

> Label single blossoms/vertices with S and put them in > the queue. (Van Rantwijk, mwmatching.py, line 649)

# File lib/graph_matching/algorithm/mwm_general.rb, line 888
def init_stage_labels
  @label = rantwijk_array(LBL_FREE)
  (0...@nvertex).each do |v|
    if @mate[v].nil? && @label[@in_blossom[v]] == LBL_FREE
      assign_label(v, LBL_S)
    end
  end
end
match_endpoint(p) click to toggle source

Add endpoint p's edge to the matching.

# File lib/graph_matching/algorithm/mwm_general.rb, line 898
def match_endpoint(p)
  @mate[@endpoint[p]] = p ^ 1
  @mate[@endpoint[p ^ 1]] = p
end
promote_sub_blossoms_of(b, endstage) click to toggle source

> Convert sub-blossoms [of `b`] into top-level blossoms. > (Van Rantwijk, mwmatching.py, line 364)

# File lib/graph_matching/algorithm/mwm_general.rb, line 905
def promote_sub_blossoms_of(b, endstage)
  @blossom_children[b].each do |s|
    @blossom_parent[s] = nil
    if s < @nvertex
      @in_blossom[s] = s
    elsif endstage && @dual[s] == 0
      expand_blossom(s, endstage)
    else
      blossom_leaves(s).each do |v|
        @in_blossom[v] = s
      end
    end
  end
end
rantwijk_array(fill) click to toggle source

Returns an array of size 2n, where n is the number of vertexes. Common in Van Rantwijk's implementation, but the idea may come from Gabow (1985) or earlier.

# File lib/graph_matching/algorithm/mwm_general.rb, line 1000
def rantwijk_array(fill)
  Array.new(2 * @nvertex, fill)
end
recycle_blossom_number(b) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 920
def recycle_blossom_number(b)
  @label[b] = nil
  @label_end[b] = nil
  @blossom_children[b] = nil
  @blossom_endps[b] = nil
  @blossom_base[b] = nil
  @blossom_best_edges[b] = nil
  @best_edge[b] = nil
  @unused_blossoms.push(b)
end
remove_breadcrumbs(path) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 981
def remove_breadcrumbs(path)
  path.each do |b| @label[b] = LBL_S end
end
scan_blossom(v, w) click to toggle source

Backtrack to find an augmenting path (returns nil) or the base of a new blossom (returns base).

> Backtrack from i and j, using the labels, to the > single persons s<sub>i</sub> and s<sub>j</sub> > from which i and j got their S labels. If > s<sub>i</sub> ≠ s<sub>j</sub>, we find an augmenting > path from s<sub>i</sub> to s<sub>j</sub> and augment > the matching. (Galil, 1986, p. 27)

> Trace back from vertices v and w to discover either a new > blossom or an augmenting path. Return the base vertex of > the new blossom or -1. (Van Rantwijk, mwmatching.py, line 233)

# File lib/graph_matching/algorithm/mwm_general.rb, line 944
def scan_blossom(v, w)
  # > Trace back from v and w, placing breadcrumbs as we go.
  path = []
  base = nil
  until v.nil? && w.nil?
    # > Look for a breadcrumb in v's blossom or put a new breadcrumb.
    b = @in_blossom[v]
    if @label[b] & 4 != 0
      base = @blossom_base[b]
      break
    end
    assert_label(b, LBL_S)
    path.push(b)
    @label[b] = LBL_CRUMB
    # > Trace one step back.
    assert(@label_end[b]).eq(@mate[@blossom_base[b]])
    if @label_end[b].nil?
      # > The base of blossom b is single; stop tracing this path.
      v = nil
    else
      v = @endpoint[@label_end[b]]
      b = @in_blossom[v]
      assert_label(b, LBL_T)
      # > b is a T-blossom; trace one more step back.
      assert(@label_end[b]).not_nil
      v = @endpoint[@label_end[b]]
    end

    # > Swap v and w so that we alternate between both paths.
    unless w.nil?
      v, w = w, v
    end
  end
  remove_breadcrumbs(path)
  base
end
scan_vertex(v) click to toggle source

> Scanning a vertex means considering in turn all its edges > except the matched edge. (There will be at most one). > (Galil, 1986, p. 26)

# File lib/graph_matching/algorithm/mwm_general.rb, line 1007
def scan_vertex(v)
  assert_label(@in_blossom[v], LBL_S)
  augmented = false

  @neighb_end[v].each do |p|
    k = p / 2 # Intentional floor division
    w = @endpoint[p]

    if @in_blossom[v] == @in_blossom[w]
      # > this edge is internal to a blossom; ignore it
      # > (Van Rantwijk, mwmatching.py, line 681)
      next
    end

    # Calculate slack of `k`'s edge and update tight_edge cache.
    kslack = calc_slack(k)

    # > .. we only use edges with π<sub>ij</sub> = 0.
    # > (Galil, 1986, p. 32)
    if @tight_edge[k]
      augmented = consider_tight_edge(k, w, p, v)
      break if augmented
    elsif @label[@in_blossom[w]] == LBL_S
      consider_loose_edge_to_s_blossom(v, k, kslack)
    elsif @label[w] == LBL_FREE
      consider_loose_edge_to_free_vertex(w, k, kslack)
    end
  end

  augmented
end
slack(k) click to toggle source

Van Rantwijk's implementation of slack does not match Galil's.

> Return 2 * slack of edge k (does not work inside blossoms). > (Van Rantwijk, mwmatching.py, line 194)

# File lib/graph_matching/algorithm/mwm_general.rb, line 1044
def slack(k)
  i, j = @edges[k]
  @dual[i] + @dual[j] - 2 * @weight[i - 1][j - 1]
end
top_level_blossom?(b) click to toggle source
# File lib/graph_matching/algorithm/mwm_general.rb, line 1049
def top_level_blossom?(b)
  !@blossom_base[b].nil? && @blossom_parent[b].nil?
end
trace_to_base(bx, bb) { |bx| ... } click to toggle source

Trace a path around a blossom, from sub-blossom `bx` to blossom base `bb`, by following `@label_end`. At each step, `yield` the sub-blossom `bx`.

# File lib/graph_matching/algorithm/mwm_general.rb, line 988
def trace_to_base(bx, bb)
  while bx != bb
    yield bx
    assert_blossom_trace(bx)
    assert(@label_end[bx]).not_nil
    bx = @in_blossom[@endpoint[@label_end[bx]]]
  end
end
update_duals(delta) click to toggle source

> .. we make the following changes in the dual > variables. (Galil, 1986, p. 32)

# File lib/graph_matching/algorithm/mwm_general.rb, line 1055
def update_duals(delta)
  (0...@nvertex).each do |v|
    case @label[@in_blossom[v]]
    when LBL_S
      @dual[v] -= delta
    when LBL_T
      @dual[v] += delta
    else
      # No change to free vertexes
    end
  end
  (@nvertex...2 * @nvertex).each do |b|
    next unless top_level_blossom?(b)
    case @label[b]
    when LBL_S
      @dual[b] += delta
    when LBL_T
      @dual[b] -= delta
    else
      # No change to free blossoms
    end
  end
end