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
GraphMatching::Algorithm::MatchingAlgorithm::new
# 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
> 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
> 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
> 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
# 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
# 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 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
> 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
# 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
> 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
# 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
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
> 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
# 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
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
> 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
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
> 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 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
> 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
> 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
# 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
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
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
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
# 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
# File lib/graph_matching/algorithm/mwm_general.rb, line 870 def init_stage init_stage_caches @queue = [] init_stage_labels end
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
> 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
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
> 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
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
# 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
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
> 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
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
# 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 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
> .. 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