二部グラフの最小重み完全マッチング
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?で解くと、) グラフの大きさが大きくなっても処理時間の増加が緩やかであることが確認できる。