二部グラフの最小重み完全マッチング

NetworkXではminimum_weight_full_matchingで用意されているのでその速さ（処理時間）を確認してみる。

確認方法説明

速さを確認するのに、以下のような比較対象となる解法を準備する。

（一般のグラフにおいて最小重み完全マッチングを求めるには、NetworkXでは残念ながら直接の関数が用意されていないので、）一般のグラフに対する最小重みマッチングを解く方法に対し、二部グラフという制約がいかに速さに影響するか確認する。

具体的に（二部グラフである）同じグラフに対し、一般のグラフに対する最小重みマッチングを解く処理時間と、二部グラフの最小重み完全マッチングを(Hopcroft–Karp algorithm?で)解く処理時間を比較する。

処理時間確認

次のようなコードで確認を行った。

必要ライブラリをimportする

hk.ipynb

import networkx as nx
import time
import random

一般のグラフに対する最小重みマッチングを解く関数の準備

hk.ipynb

def matching(edges):
    # グラフを作成
    G = nx.Graph()

    # 重み付きエッジを追加
    G.add_edges_from(edges)

    # マッチングのみ時間を計測
    start_time = time.time()
    matching = nx.algorithms.matching.min_weight_matching(G, weight='weight')
    end_time = time.time()

    # マッチングとその総重みを表示
    total_weight = sum(G[u][v]['weight'] for u, v in matching)
    print("マッチング:", matching)
    print("総重み:", total_weight)
    print("実行時間:", end_time - start_time, "秒")

二部グラフの最小重み完全マッチングを(Hopcroft–Karp algorithm?で)解く関数の準備

hk.ipynb

def matching_bipartite(edges):
    # 重複なしの1つ目の要素を取得
    unique_first_elements = list(set(edge[0] for edge in edges))
    # 重複なしの2つ目の要素を取得
    unique_second_elements = list(set(edge[1] for edge in edges))

    # 二部グラフを作成
    G_bipartite = nx.Graph()

    # 左の頂点集合を追加
    left_nodes = unique_first_elements
    G_bipartite.add_nodes_from(left_nodes, bipartite=0)

    # 右の頂点集合を追加
    right_nodes = unique_second_elements
    G_bipartite.add_nodes_from(right_nodes, bipartite=1)

    # 重み付きエッジを追加
    G_bipartite.add_edges_from(edges)

    # マッチングのみ時間を計測
    start_time_bipartite = time.time()
    matching_bipartite = nx.bipartite.minimum_weight_full_matching(G_bipartite).items()
    end_time_bipartite = time.time()

    # マッチングとその総重みを表示
    print("マッチング:", matching_bipartite)
    # https://stackoverflow.com/questions/73533607/is-there-a-way-to-return-the-edges-used-in-a-minimum-weight-matching-on-a-bipart
    weight = sum(
        G_bipartite.edges[u, v]['weight']
        for u, v in matching_bipartite
    ) // 2
    print("総重み:", weight)
    print("実行時間:", end_time_bipartite - start_time_bipartite, "秒")

二部グラフの準備

大きさの異なる二部グラフを作成する。

hk.ipynb

def generate_random_bipartite_graph(nodes_part1, nodes_part2, min_weight, max_weight):
    edges = []
    
    for node1 in nodes_part1:
        for node2 in nodes_part2:
            weight = random.randint(min_weight, max_weight)
            edges.append((node1, node2, {'weight': weight}))
    
    return edges

hk.ipynb

min_weight_1 = 1
max_weight_1 = 10

nodes_part1 = [i for i in range(1, 11)]
nodes_part2 = [i for i in range(11, 21)]
random_edges_1 = generate_random_bipartite_graph(nodes_part1, nodes_part2, min_weight_1, max_weight_1)

# 結果の出力
print(random_edges_1)

# 大きくしないとエッジが多いので最小値が出る確率が高くなってしまう
max_weight_2 = 50

nodes_part3 = [i for i in range(1, 51)]
nodes_part4 = [i for i in range(51, 101)]
random_edges_2 = generate_random_bipartite_graph(nodes_part3, nodes_part4, min_weight_1, max_weight_2)

max_weight_3 = 100

nodes_part5 = [i for i in range(1, 101)]
nodes_part6 = [i for i in range(101, 201)]
random_edges_3 = generate_random_bipartite_graph(nodes_part5, nodes_part6, min_weight_1, max_weight_3)

準備した二部グラフに対し、それぞれの方法でマッチング

hk.ipynb

matching(random_edges_1)
matching(random_edges_2)
matching(random_edges_3)

matching_bipartite(random_edges_1)
matching_bipartite(random_edges_2)
matching_bipartite(random_edges_3)

処理結果

マッチング: {(4, 16), (1, 11), (15, 7), (6, 17), (8, 13), (20, 10), (3, 19), (14, 9), (12, 2), (5, 18)}
総重み: 17
実行時間: 0.001112222671508789 秒
マッチング: {(7, 78), (95, 20), (36, 68), (27, 62), (11, 60), (31, 93), (22, 99), (30, 88), (46, 72), (6, 66), (4, 54), (24, 87), (63, 12), (42, 96), (47, 52), (29, 74), (79, 32), (25, 89), (18, 77), (41, 51), (23, 73), (26, 90), (71, 37), (98, 45), (84, 34), (91, 21), (19, 69), (15, 56), (39, 53), (16, 61), (48, 59), (92, 35), (44, 80), (76, 17), (1, 81), (67, 5), (49, 94), (82, 33), (58, 14), (38, 100), (70, 13), (75, 3), (2, 55), (65, 10), (50, 86), (40, 57), (85, 28), (43, 83), (9, 97), (64, 8)}
総重み: 112
実行時間: 0.042578935623168945 秒
マッチング: {(128, 26), (151, 9), (76, 189), (120, 49), (104, 7), (81, 133), (55, 114), (40, 196), (72, 148), (67, 198), (17, 142), (29, 180), (58, 161), (33, 150), (53, 192), (61, 193), (68, 107), (186, 1), (30, 141), (94, 144), (98, 199), (47, 187), (65, 168), (48, 106), (115, 50), (63, 177), (159, 4), (101, 14), (59, 109), (42, 157), (173, 39), (5, 119), (10, 179), (82, 110), (158, 78), (41, 124), (170, 6), (21, 118), (139, 64), (8, 166), (165, 46), (60, 121), (92, 153), (38, 182), (62, 176), (11, 146), (54, 181), (73, 194), (93, 172), (25, 154), (28, 116), (34, 132), (31, 197), (122, 52), (13, 103), (75, 185), (23, 147), (18, 169), (24, 130), (91, 113), (174, 19), (86, 135), (66, 175), (89, 140), (15, 102), (51, 195), (70, 145), (79, 178), (32, 200), (108, 37), (123, 83), (3, 112), (74, 163), (45, 127), (77, 125), (22, 143), (27, 188), (99, 137), (57, 131), (56, 111), (85, 156), (87, 138), (84, 105), (136, 69), (95, 190), (167, 96), (71, 162), (36, 149), (100, 152), (80, 164), (184, 20), (44, 171), (117, 97), (155, 90), (2, 183), (129, 16), (88, 134), (12, 160), (191, 43), (126, 35)}
総重み: 225
実行時間: 0.20990514755249023 秒
マッチング: dict_items([(1, 11), (2, 12), (3, 19), (4, 16), (5, 18), (6, 17), (7, 15), (8, 13), (9, 14), (10, 20), (11, 1), (12, 2), (19, 3), (16, 4), (18, 5), (17, 6), (15, 7), (13, 8), (14, 9), (20, 10)])
総重み: 17
実行時間: 0.0007631778717041016 秒
マッチング: dict_items([(1, 81), (2, 55), (3, 75), (4, 54), (5, 67), (6, 66), (7, 78), (8, 64), (9, 97), (10, 65), (11, 60), (12, 63), (13, 70), (14, 58), (15, 56), (16, 61), (17, 76), (18, 77), (19, 69), (20, 95), (21, 91), (22, 99), (23, 73), (24, 87), (25, 89), (26, 90), (27, 62), (28, 85), (29, 74), (30, 88), (31, 93), (32, 79), (33, 82), (34, 84), (35, 92), (36, 68), (37, 71), (38, 100), (39, 53), (40, 57), (41, 51), (42, 96), (43, 83), (44, 80), (45, 98), (46, 72), (47, 52), (48, 59), (49, 94), (50, 86), (81, 1), (55, 2), (75, 3), (54, 4), (67, 5), (66, 6), (78, 7), (64, 8), (97, 9), (65, 10), (60, 11), (63, 12), (70, 13), (58, 14), (56, 15), (61, 16), (76, 17), (77, 18), (69, 19), (95, 20), (91, 21), (99, 22), (73, 23), (87, 24), (89, 25), (90, 26), (62, 27), (85, 28), (74, 29), (88, 30), (93, 31), (79, 32), (82, 33), (84, 34), (92, 35), (68, 36), (71, 37), (100, 38), (53, 39), (57, 40), (51, 41), (96, 42), (83, 43), (80, 44), (98, 45), (72, 46), (52, 47), (59, 48), (94, 49), (86, 50)])
総重み: 112
実行時間: 0.0014748573303222656 秒
マッチング: dict_items([(1, 186), (2, 183), (3, 112), (4, 159), (5, 119), (6, 170), (7, 104), (8, 166), (9, 151), (10, 179), (11, 146), (12, 160), (13, 103), (14, 101), (15, 102), (16, 129), (17, 142), (18, 169), (19, 174), (20, 184), (21, 118), (22, 143), (23, 147), (24, 130), (25, 154), (26, 128), (27, 188), (28, 116), (29, 180), (30, 141), (31, 197), (32, 200), (33, 150), (34, 132), (35, 126), (36, 149), (37, 108), (38, 182), (39, 173), (40, 196), (41, 124), (42, 157), (43, 191), (44, 171), (45, 127), (46, 165), (47, 187), (48, 106), (49, 120), (50, 115), (51, 195), (52, 122), (53, 192), (54, 181), (55, 114), (56, 111), (57, 131), (58, 161), (59, 109), (60, 121), (61, 193), (62, 176), (63, 177), (64, 139), (65, 168), (66, 175), (67, 198), (68, 107), (69, 136), (70, 145), (71, 162), (72, 148), (73, 194), (74, 163), (75, 185), (76, 189), (77, 125), (78, 158), (79, 178), (80, 164), (81, 133), (82, 110), (83, 123), (84, 105), (85, 156), (86, 135), (87, 138), (88, 134), (89, 140), (90, 155), (91, 113), (92, 153), (93, 172), (94, 144), (95, 190), (96, 167), (97, 117), (98, 199), (99, 137), (100, 152), (186, 1), (183, 2), (112, 3), (159, 4), (119, 5), (170, 6), (104, 7), (166, 8), (151, 9), (179, 10), (146, 11), (160, 12), (103, 13), (101, 14), (102, 15), (129, 16), (142, 17), (169, 18), (174, 19), (184, 20), (118, 21), (143, 22), (147, 23), (130, 24), (154, 25), (128, 26), (188, 27), (116, 28), (180, 29), (141, 30), (197, 31), (200, 32), (150, 33), (132, 34), (126, 35), (149, 36), (108, 37), (182, 38), (173, 39), (196, 40), (124, 41), (157, 42), (191, 43), (171, 44), (127, 45), (165, 46), (187, 47), (106, 48), (120, 49), (115, 50), (195, 51), (122, 52), (192, 53), (181, 54), (114, 55), (111, 56), (131, 57), (161, 58), (109, 59), (121, 60), (193, 61), (176, 62), (177, 63), (139, 64), (168, 65), (175, 66), (198, 67), (107, 68), (136, 69), (145, 70), (162, 71), (148, 72), (194, 73), (163, 74), (185, 75), (189, 76), (125, 77), (158, 78), (178, 79), (164, 80), (133, 81), (110, 82), (123, 83), (105, 84), (156, 85), (135, 86), (138, 87), (134, 88), (140, 89), (155, 90), (113, 91), (153, 92), (172, 93), (144, 94), (190, 95), (167, 96), (117, 97), (199, 98), (137, 99), (152, 100)])
総重み: 225
実行時間: 0.0055048465728759766 秒

処理結果に対する結論

（Hopcroft–Karp algorithm?で解くと、) グラフの大きさが大きくなっても処理時間の増加が緩やかであることが確認できる。