class GraphMatching::Algorithm::MCMGeneral
`MCMGeneral` implements Maximum Cardinality Matching
in general graphs (as opposed to bipartite).
Public Class Methods
GraphMatching::Algorithm::MatchingAlgorithm::new
# File lib/graph_matching/algorithm/mcm_general.rb, line 20 def initialize(graph) assert(graph).is_a(Graph::Graph) super end
Public Instance Methods
# File lib/graph_matching/algorithm/mcm_general.rb, line 25 def match return Matching.new if g.empty? raise DisconnectedGraph unless g.connected? e(g) end
Private Instance Methods
`e` constructs a maximum matching on a graph. It starts a search for an augmenting path to each unmatched vertex u. It scans edges of the graph, deciding to assign new labels or to augment the matching.
# File lib/graph_matching/algorithm/mcm_general.rb, line 37 def e(g) first = [] label = [] mate = [] # E0. [Initialize.] Read the graph into adjacency lists, # numbering the vertices 1 to V and the edges V + 1 to # V + 2W. Create a dummy vertex 0 For 0 <= i <= V, set # LABEL(u) <- -1, MATE(i) <- 0 (all vertices are nonouter # and unmatched) Set u <- 0 label.fill(-1, 0, g.size + 1) mate.fill(0, 0, g.size + 1) u = 0 # El. [Find unmatched vertex ] Set u = u + 1. If u > V, # halt; MATE contains a maximum matching Otherwise, if vertex # u is matched, repeat step E1 Otherwise (u is unmatched, so # assign a start label and begin a new search) # set LABEL(u) = FIRST(u) = 0 loop do u += 1 break if u > g.size if mate[u] != 0 next # repeat E1 else label[u] = first[u] = 0 end # E2 [Choose an edge ] Choose an edge xy, where x is an outer # vertex. (An edge vw may be chosen twice in a search--once # with x = v, and once with x = w.) If no such edge exists, # go to E7. (Edges xy can be chosen in an arbitrary order. A # possible choice method is "breadth-first": an outer vertex # x = x1 is chosen, and edges (x1,y) are chosen in succeeding # executions of E2, when all such edges have been chosen, the # vertex x2 that was labeled immediately after x1 is chosen, # and the process is repeated for x = x2. This breadth-first # method requires that Algorithm E maintain a list of outer # vertices, x1, x2, ...) searching = true visited_nodes = Set.new visited_edges = DirectedEdgeSet.new(g.size) q = OrderedSet[u] while searching && !q.empty? x = q.deq visited_nodes.add(x) adjacent = g.adjacent_vertex_set(x) discovered = adjacent - visited_edges.adjacent_vertices(x) discovered.each do |y| visited_edges.add(x, y) # E3. [Augment the matching.] If y is unmatched and y != u, # set MATE(y) = x, call R(x, y): then go to E7 (R # completes the augment along path (y)*P(x)) if mate[y] == 0 && y != u mate[y] = x r(x, y, label, mate) searching = false # go to E7 break # E4. [Assign edge labels.] If y is outer, call L, then go to # E2 (L assigns edge label n(xy) to nonouter vertices in P(x) # and P(y)) elsif outer?(label[y]) l(x, y, first, label, mate, q, visited_nodes) # E5. [Assign a vertex label.] Set v <- MATE(y). If v is # nonouter, set LABEL(v) <- x, FIRST(v) <- y, and go to E2 # # E6. [Get next edge.] Go to E2 (y is nonouter and MATE(y) is # outer, so edge xy adds nothing). else v = mate[y] if label[v] == -1 # nonouter label[v] = x first[v] = y end unless visited_nodes.include?(v) q.enq(v) end end end end # # E7. [Stop the search] Set LABEL(O) <- -1. For all outer # vertices i set LABEL(i) <- LABEL(MATE(i)) <- -1 Then go # to E1 (now all vertexes are nonouter for the next search). # label[0] = -1 label.each_with_index do |obj, ix| if ix > 0 && outer?(obj) label[ix] = label[mate[ix]] = -1 end end end Matching.gabow(mate) end
# File lib/graph_matching/algorithm/mcm_general.rb, line 145 def edge_label?(label_value) label_value.is_a?(RGL::Edge::UnDirectedEdge) end
L assigns the edge label n(xy) to nonouter vertices. Edge xy joins outer vertices x, y. L sets join to the first nonouter vertex in both P(x) and P(y). Then it labels all nonouter vertices preceding join in P(x) or P(y).
# File lib/graph_matching/algorithm/mcm_general.rb, line 153 def l(x, y, first, label, mate, q, visited_nodes) # L0. [Initialize.] Set r <- FIRST(x), s <= FIRST(y). # If r = s, return (no vertices can be labeled). # Otherwise flag r and s. (Steps L1-L2 find join by advancing # alternately along paths P(x) and P(y). Flags are assigned # to nonouter vertices r in these paths. This is done by # setting LABEL(r) to a negative edge number, LABEL(r) <- -n(xy). # This way, each invocation of L uses a distinct flag value.) r = first[x] s = first[y] if r == s return # no vertices can be labeled else label[r] = LFlag.new(n(x, y)) end # L1. [Switch paths ] If s != 0, interchange r and s, r <-> s # (r is a flagged nonouter vertex, alternately in P(x) and P(y)). finding_join = true while finding_join if s != 0 temp = r r = s s = temp end # L2. [Next nonouter vertex.] Set r <- FIRST(LABEL(MATE(r))) # (r is set to the next nonouter vertex in P(x) or P(y)). If # r is not flagged, flag r and go to L1 Otherwise set # join <- r and go to L3. r = first[label[mate[r]]] if label[r].is_a?(LFlag) join = r finding_join = false else label[r] = LFlag.new(n(x, y)) end end # L3. [Label vertices in P(x), P(y).] (All nonouter vertexes # between x and join, or y and join, will be assigned edge # labels. See Figure 4(a).) Set v <- FIRST(x) and do L4. Then # set v <- FIRST(y) and do L4. Then go to L5. [first[x], first[y]].each do |v| # L4 [Label v] If v != join, set LABEL(v) <- n(xy), FIRST(v) <- join, # v <- FIRST(LABEL(MATE(v))) and repeat step L4 # Otherwise continue as specified in L3. until v == join label[v] = n(x, y) unless visited_nodes.include?(v) q.enq(v) end first[v] = join v = first[label[mate[v]]] end end # L5 [Update FIRST] For each outer vertex i, if FIRST(i) is # outer, set FIRST(i) <- join. (Join is now the first nonouter # vertex in P(i)) label.each_with_index do |l, i| if i > 0 && outer?(l) && outer?(label[first[i]]) first[i] = join end end # L6. [Done] Return end
Gabow (1976) describes a function `n` which returns the number of the edge from `x` to `y`. Because we are using RGL, and not implementing our own adjacency lists, we can simply return an RGL::Edge::UnDirectedEdge.
# File lib/graph_matching/algorithm/mcm_general.rb, line 233 def n(x, y) RGL::Edge::UnDirectedEdge.new(x, y) end
# File lib/graph_matching/algorithm/mcm_general.rb, line 237 def outer?(label_value) !label_value.is_a?(Integer) || label_value >= 0 end
R(v, w) rematches edges in the augmenting path. Vertex v is outer. Part of path (w) * P(v) is in the augmenting path. It gets re-matched by R(v, w) (Although R sets MATE(v) <- w, it does not set MATE(w) <- v. This is done in step E3 or another call to R.) R is a recursive routine.
# File lib/graph_matching/algorithm/mcm_general.rb, line 246 def r(v, w, label, mate) # R1. [Match v to w ] Set t <- MATE(v), MATE(v) <- w. # If MATE(t) != v, return (the path is completely re-matched) t = mate[v] mate[v] = w return if mate[t] != v # R2. [Rematch a path.] If v has a vertex label, set # MATE(t) <- LABEL(v), call R(LABEL(v), t) recursively, and # then return. if vertex_label?(label[v]) mate[t] = label[v] r(label[v], t, label, mate) # R3. [Rematch two paths.] (Vertex v has an edge label) # Set x, y to vertices so LABEL(v) = n(xy), call R(x, y) # recursively, call R(y, x) recursively, and then return. elsif edge_label?(label[v]) x, y = label[v].to_a r(x, y, label, mate) r(y, x, label, mate) else raise "Vertex #{v} has an unexpected label type" end end
# File lib/graph_matching/algorithm/mcm_general.rb, line 275 def vertex_label?(label_value) label_value.is_a?(Integer) && label_value > 0 end