NetworkXでTTCサイクルを実装する（アルゴリズム編）
大学のマーケットデザインの授業で習った「TTCアルゴリズム」をPythonのライブラリNetworkXを使って実装してみたので、残しておこうと思います。 今回の記事ではアルゴリズムの中身の部分について、次回はそれをWebサイト(Django)上でGUIで動かして、誰でもプレゼント交換に使えるようにした記事を書く予定です。 TTCアルゴリズムのコード さて、まずTTCアルゴリズムのマッチングを行うコードは以下の通りです。 import networkx as nx import random import matplotlib.pyplot as plt def ttc_algorithm(preference_dict: dict): result_cycles_list = [] while preference_dict != {}: # create directed graph g = nx.DiGraph() # add nodes nodes_list = [] for key in preference_dict: nodes_list.append(key) nodes_list.sort() for elem in nodes_list: g.add_node(elem) for key in preference_dict: g.add_edge(key, preference_dict[key][0]) # search for cycles cycles = nx.simple_cycles(g) cycles_list = list(cycles) # Graph drawing part starts here color_map_dict_pre = {key: "deepskyblue" for key in preference_dict.keys()} for cy...