%reload_ext autoreload
%autoreload 2
%matplotlib inline
%load_ext lab_black

準備

import random
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

例題

あなたは幼稚園の先生だ．いま，あなたの $12$人の園児たちは$3$行，$4$列にきちんと並んでいる．園児たちは自分の前後左右のいずれかの友達から1人を選び手をつなぐことができる．手をつなぐ人数を最大にするには，どのようにしたら良いのだろうか？

上の問題は無向グラフ上のマッチング問題になる．ここでマッチング(matching)とは，点の次数が1 以下の部分グラフのことである．

上の問題のグラフは，$3 \times 4$ の格子グラフであり，以下のようになる．

m, n = 3, 4
G = nx.grid_2d_graph(m, n)
pos = {(i, j): (i, j) for (i, j) in G.nodes()}
plt.figure()
nx.draw(G, pos=pos, node_size=100)
plt.show()

極大マッチング

いま，園児たちに順番に自分の好きな友達と手をつなぐように指示したとしよう．前後左右の友達から（すでに手をつないでいる園児は除外して）1人を選んで手をつないでいくと，やがて前後左右の誰とも手をつなげない状態になる．このときの手のつなぎ方を極大マッチング (maximal matching)とよぶ．

edges = nx.maximal_matching(G)
nx.draw(G, pos=pos, width=5, node_size=10, edgelist=edges, edge_color="orange")
plt.show()

最大マッチング

本当に求めたいものは，手をつなぐ数を最大化するようなマッチングである．これを最大マッチング(maximum matching)とよぶ．極大マッチングは貪欲解法で簡単に求めることができるが，最大マッチングも多項式時間で求めることができる．枝に重み（手を繋いだときの利益）がついても，その合計を最大化してくれる．

極大マッチングでは10人の園児が手をつなぐ可能性もあるが，最大マッチングでは必ず全員（12人）が手をつなぐことに成功する．

edges = nx.max_weight_matching(G)
nx.draw(G, pos=pos, width=5, node_size=10, edgelist=edges, edge_color="orange")
plt.show()

最小費用の完全マッチングも求めたい場合には，枝の重みを負に設定すれば良い．この場合には，引数のmaxcardinalityをTrueに設定して，枝の本数を最大にする必要がある．

D = {"L001": {"L002","L003","L013","L014"},
        "L002":{"L001","L003","L013","L014"},
        "L003":{"L001","L002","L013","L014"},
        "L004":{"L001","L002","L003","L005","L006","L007","L008","L009","L010","L011","L012","L013","L014"},
        "L005":{"L001","L002","L003","L004","L006","L007","L008","L009","L010","L011","L012","L013","L014"},
        "L006":{"L001","L002","L003","L004","L005","L007","L008","L009","L010","L011","L012","L013","L014"},
        "L007":{"L001","L002","L003","L008","L009","L010","L011","L012","L013","L014"},
        "L008":{"L001","L002","L003","L009","L010","L011","L012","L013","L014"},
        "L009":{"L001","L002","L003","L008","L010","L011","L012","L013","L014"},
        "L010":{"L011","L012","L013","L014"},
        "L011":{"L010","L012","L013","L014"},
        "L012":{"L010","L011","L013","L014"},
        "L013":{"L014"}
    }

lb, ub = 1, 20
import networkx as nx
G = nx.Graph()
for i, neighbor in D.items():
    for j in neighbor:
        G.add_edge(i,j)
for (i, j) in G.edges():
    G[i][j]["weight"] = random.randint(lb, ub)
    #print(i,j,G[i][j]["weight"])
edges = nx.max_weight_matching(G)
for (i,j) in edges:
    if i in D:
        if j in D[i]:
            print(i, "<=", j)
        else:
            print(j, "<=", i)

L007 <= L002
L010 <= L012
L001 <= L013
L004 <= L003
L006 <= L005
L008 <= L009

lb, ub = 1, 20
for (i, j) in G.edges():
    G[i][j]["weight"] = random.randint(lb, ub)
edges = nx.max_weight_matching(G, maxcardinality=False)
edges

{('L001', 'L002'),
 ('L003', 'L006'),
 ('L004', 'L005'),
 ('L007', 'L008'),
 ('L010', 'L012'),
 ('L011', 'L009'),
 ('L013', 'L014')}

plt.figure()
nx.draw(G, pos=pos, node_size=100)
edge_labels = {}
for (i, j) in G.edges():
    edge_labels[i, j] = f"{ G[i][j]['weight'] }"
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
nx.draw(G, pos=pos, width=5, edgelist=edges, edge_color="orange")
plt.show()

安定マッチング問題

最も基本的な安定マッチング問題は，安定結婚問題(stable marriage problem)とよばれ，以下のように定義される．

２つの異なる集合 $S, R$ が与えられており， 2つの集合で構成される2部グラフの完全マッチング $M$ を求めたい．各集合（古典的には男女の集団と仮定されるが，ここではsuitorとreviewerとする）には， $S$ と $R$ の各要素 $s,r$ は，別の集合の要素に対する選好(preference) を全順序 $\prec_s, \prec_r$ として持っている．

以下の条件を満たすような組 $(s,r)$ がないマッチング $M$ を安定マッチングとよぶ．

$（s，r）$ は $M$ に含まれない．
$(s,r') \in M$ となる $r'$ に対して $r \prec_s r'$ となる（すなわち $s$ さんは，マッチングされていない $r$ さんの方が好きである）．
$(s',r) \in M$ となる $s'$ に対して $s \prec_r s'$ となる（すなわち $r$ さんも，マッチングされていない $s$ さんの方が好きである）．

具体的な例で説明しよう．

$n$ 箇所の病院の集合 $H$ と $n$ 人の学生のマッチングを求めたい．各病院 $h$ は学生の選好順 $student[h]$ をもち，各学生 $s$ は病院の選好順 $hospital[s]$ をもつ．病院 $h$ が割り当てられている学生 $s'$ より $s$ を選好し，学生 $s$ が割り当てられている病院 $h'$ より $h$ を選好しているとき，$(h,s)$ を不安定ペア (unstable pair) とよぶ，病院と学生の完全マッチングで，不安定ペアが存在しないものを安定マッチング (stable matching)とよぶ．

1つの（病院最適な）安定マッチングを算出するGale-Shapleyのアルゴリズム（以下の論文に基づく）を示す．

David Gale and Lloyd Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962

空の集合からなるマッチング $M$ を準備する．
学生が割り当てられていない病院 $h$ がなくなるまで，以下を実行する．
- $h$ の選好リストの先頭の学生 $s$ を選択し，プロポーズする．
- $s$ が未割り当てなら，マッチング $M$ に $(h,s)$ を追加する．
- $s$ にすでに割り当てられている病院 $h'$ より $h$ を選好するなら，$M$ から $(h',s)$ を除き $(h,s)$ を追加する．
- そうでないなら，$h$ は拒否される．

安定マッチング問題の解説と実装方法については，以下のビデオを参照されたい．

簡単な $O(n^2)$ 時間の実装を以下に示す．

student_pref = np.array([[0, 1, 2], [1, 0, 2], [0, 1, 2]])
hospital_pref = np.array([[1, 0, 2], [0, 1, 2], [0, 1, 2]])

top_student = [0, 0, 0]
n = len(student_pref)
hospital_rank = np.zeros((n, n), dtype=int)
for s in range(n):
    for i in range(n):
        hospital_rank[s, hospital_pref[s, i]] = i

hospital_list = list(range(n))
student = [-1 for i in range(n)]
hospital = [-1 for i in range(n)]

while hospital_list:
    print("Unassigned Hospital=", hospital_list)
    h = hospital_list.pop(0)
    print(h)
    s = student_pref[h, top_student[h]]
    top_student[h] += 1
    print(h, "proposes to", s)
    if hospital[s] == -1:  # 未割り当て
        student[h] = s
        hospital[s] = h
    elif hospital_rank[s, h] < hospital_rank[s, hospital[s]]:
        print("Student", s, " is assigned to Hospital", h)
        hospital_list.append(hospital[s])
        student[h] = s
        hospital[s] = h
    else:
        print(h, "is rejected")
        hospital_list.append(h)
print("Student=", student)
print("Hospital=", hospital)

Unassigned Hospital= [0, 1, 2]
0
0 proposes to 0
Unassigned Hospital= [1, 2]
1
1 proposes to 1
Unassigned Hospital= [2]
2
2 proposes to 0
2 is rejected
Unassigned Hospital= [2]
2
2 proposes to 1
2 is rejected
Unassigned Hospital= [2]
2
2 proposes to 2
Student= [0, 1, 2]
Hospital= [0, 1, 2]

なお，以下のパッケージで，安定マッチング問題を含む様々な問題を解くことができる．

https://matching.readthedocs.io/en/latest/index.html

安定ルームメイト問題

類似の問題として安定ルームメイト問題(stable roommates problem)がある．以下のように定義される．

集合 $P$ (player) が与えられており，その要素数は偶数であると仮定する． $P$に対する完全マッチング $M$ （部屋割を表す）を求めたい． $P$ の各要素 $p$ は，自分以外の人に対する選好を全順序 $\prec_p$ として持っている．

以下の条件を満たすような組 $(s,r)$ がないマッチング $M$ を安定マッチングとよぶ．

$（s，r）$ は $M$ に含まれない．
$(s,r') \in M$ となる $r'$ に対して $r \prec_s r'$ となる（すなわち $s$ さんは，マッチングされていない $r$ さんの方が好きである）．
$(s',r) \in M$ となる $s'$ に対して $s \prec_r s'$ となる（すなわち $r$ さんも，マッチングされていない $s$ さんの方が好きである）．

安定ルームメイト問題に対する安定マッチングも，安定マッチングで紹介したパッケージで解くことができる．