如何获取同一二分图的多个不同最大匹配

Great question! Generating hundreds of distinct maximum matchings in a large bipartite graph is totally doable—here's how to approach it, building on the Hopcroft-Karp algorithm you're already using:

The key insight is that maximum matchings aren't unique, and we can generate new ones by swapping edges in alternating cycles within the graph. An alternating cycle is a cycle where edges flip between being part of the current matching and not part of it. Swapping which edges are matched in these cycles preserves the total size of the matching (so it stays maximum).

Here's a step-by-step breakdown:

• Start with an initial maximum matching found via Hopcroft-Karp.
• Build a residual graph from the current matching: reverse the direction of matched edges, keep non-matched edges in their original direction. Alternating cycles in the original graph become directed cycles in this residual graph.
• Find random directed cycles in the residual graph, swap the matched/unmatched edges in the original graph to create a new maximum matching.
• Repeat this process, checking for duplicates, until you have hundreds of unique matchings.

Below is modified code that extends your existing setup to generate multiple distinct maximum matchings:

import igraph as ig
from scipy.sparse import random, find
from scipy import stats
from numpy.random import default_rng
import numpy as np
from igraph import Graph, plot
import random as rd

def generate_multiple_max_matches(g, num_matches=100):
    # Get initial maximum matching with Hopcroft-Karp
    initial_match = g.maximum_bipartite_matching()
    matches = [initial_match]
    
    # Split nodes into left (type 0) and right (type 1) partitions
    left_nodes = [v.index for v in g.vs if v['type'] == 0]
    right_nodes = [v.index for v in g.vs if v['type'] == 1]
    
    while len(matches) < num_matches:
        # Pick a random existing matching as the base for modification
        current_match = rd.choice(matches)
        # Create a dict for quick lookup of matched pairs (left -> right)
        match_map = {u: current_match.match_of(u) for u in left_nodes if current_match.match_of(u) is not None}
        
        # Build residual graph: reverse matched edges, keep non-matched edges as-is
        residual_edges = []
        for u in left_nodes:
            for v in g.neighbors(u):
                if match_map.get(u) == v:
                    # Matched edge: reverse direction (right -> left)
                    residual_edges.append((v, u))
                else:
                    # Non-matched edge: keep direction (left -> right)
                    residual_edges.append((u, v))
        
        residual_g = Graph(directed=True)
        residual_g.add_vertices(g.vcount())
        residual_g.add_edges(residual_edges)
        
        # Find up to 10 simple cycles in the residual graph (keeps things efficient)
        cycles = residual_g.simple_cycles(mode="all", limit=10)
        if not cycles:
            continue  # No cycles found, try another base matching
        
        # Pick a random cycle to modify
        cycle = rd.choice(cycles)
        # Bipartite graphs only have even-length cycles, skip any odd ones just in case
        if len(cycle) % 2 != 0:
            continue
        
        # Create new matching by swapping edges in the cycle
        new_match_map = match_map.copy()
        for i in range(0, len(cycle), 2):
            u, v = cycle[i], cycle[i+1]
            if u in left_nodes:
                # Assign left node u to right node v (overwriting existing match if needed)
                new_match_map[u] = v
            else:
                # Remove the match for the left node v (since u is a right node now matched elsewhere)
                if v in new_match_map:
                    del new_match_map[v]
        
        # Convert to igraph Matching object
        new_match_pairs = [(u, v) for u, v in new_match_map.items()]
        new_match = ig.Matching(g, new_match_pairs)
        
        # Check for duplicates before adding
        new_match_set = set(tuple(sorted(new_match.items())))
        duplicate = False
        for m in matches:
            if set(tuple(sorted(m.items()))) == new_match_set:
                duplicate = True
                break
        if not duplicate:
            matches.append(new_match)
    
    return matches

# Generate your sample bipartite graph
np.random.seed(7)
rng = default_rng()
rvs = stats.poisson(2).rvs
S = random(20, 20, density=0.35, random_state=rng, data_rvs=rvs)
triples = [*zip(*find(S))]
edges = [(triple[0], triple[1]+20) for triple in triples]
types = [0]*20 + [1]*20
g = Graph.Bipartite(types, edges)

# Generate 100 distinct maximum matchings
max_matches = generate_multiple_max_matches(g, num_matches=100)

# Visualize the 5th matching (adjust index to see others)
sample_match = max_matches[4]
visual_style = {
    "vertex_size": 20,
    "bbox": (600, 300),
    "vertex_label": range(g.vcount()),
    "vertex_color": "lightblue",
    "edge_width": [5 if e.target == sample_match.match_of(e.source) else 1.0 for e in g.es],
    "edge_color": ["red" if e.target == sample_match.match_of(e.source) else "black" for e in g.es]
}
plot(g, layout=g.layout_bipartite(), **visual_style)

• Duplicate Checking: Converting matchings to sorted tuples in a set is a simple way to avoid duplicates, which can happen if you cycle back to a previous matching.
• Efficiency: Limiting the number of cycles found per iteration (limit=10) prevents the code from getting stuck searching for cycles in huge graphs. Randomly selecting base matchings and cycles also helps generate diverse matchings quickly.
• Bipartite Cycle Guarantee: Bipartite graphs only contain even-length cycles, so we skip any odd-length ones to ensure we don't break the matching size.

内容的提问来源于stack exchange，提问作者byteful