※本記事はChromebookを使用して執筆しました
目次
こんなお困りごとはないですか？
pythonビギナー
Pythonの扱いには慣れてきたけど、実社会の問題を解いてみたいわ。
例えば、最近マーケットデザインという分野が流行っているようだけど、実際にPythonで実装して体験してみたいわ。
解決方法は？
あるよ。
忠犬SE
マーケットデザインではマッチング理論が扱われているんだけど、マッチング理論の二部グラフの1対1のマッチング問題についてはグラフ理論を使えば解けるよ。
二部グラフの1対1のマッチング問題については『史上空前!! 笑いの祭典 ザ・ドリームマッチ』をイメージすると解りやすいいよ。
忠犬SE
史上空前!! 笑いの祭典 ザ・ドリームマッチ
普段テレビでなかなかネタを披露することのない中堅クラスの人気お笑い芸人たちをシャッフルして即席コンビを結成させ、ネタを披露し合うコンテスト形式の番組。
『史上空前!! 笑いの祭典 ザ・ドリームマッチ』 ウィキペディア
例えば、５人のボケと５人のツッコミがいて、可能なかぎり相思相愛のコンビを作ることを考えよう。
各ボケが、５人のツッコミから上位３位までを選択し、順位が良い順に「３ポイント、２ポイント、１ポイント」付与して、各ツッコミも同様に、５人のボケから上位３位までを選択しポイントを付与したとするよ。
このとき、ポイントが最大になるような組み合わせ（＝可能なかぎり相思相愛）を考えることを重み最大マッチング問題というんだ。
※実際にはコンビを決めるあのやりとり含めてザ・ドリームマッチの面白みなのだが。。。
重み最大マッチング問題を解いた結果が下図だよ。
５人のボケ（ネイビー）と５人のツッコミ（レッド） のペアが太線で表現されているよ。太線が引かれていないのはいわゆる残り物だね。
忠犬SE
ここでは、Pythonのnetworkxというライブラリを使用してグラフの定義と重み最大マッチング問題を解いて、解いた結果をdash_cytoscapeというdashフレームワークのコンポーネントを使って可視化しているよ。
早速始めてみよう。
忠犬SE
networkxでマッチング問題を解いてdash_cytoscapeで可視化する
流れ
- 全体の概要を理解する
- colabノートブックを作成する
- 実際に動かしてみる
- STEP
全体概要を理解する
可視化については、下記記事を参考にしてwebアプリを作成します。
- Colabにてdash_cytoscapeを使用するためのライブラリをインストールする
- 可視化用webアプリの基底クラスとしてJupyterDashを継承したクラスを作成する
- networkxを使用してグラフ（node、edge、weight）を定義する関数を定義する
- networkxを使用して3で作成したグラフの重み最大マッチング問題を解く関数を定義する
- 基底クラスを継承してwebアプリを定義したクラスを作成する
- 4の関数を実行してグラフと重み最大マッチング問題を解いた結果を取得する
- networkxのグラフオブジェクトをdash_cytoscapeで使用可能なデータ形式に変換
- 条件を指定してnodeの色を設定
- 重み最大マッチング結果に該当edgeの色を変更
- タイトル名とポート番号を指定してwebアプリを実行する
- STEP
Colabのノートブックを作成する
下記記事などを参考に、Colabで新しいノートブックを作成します。
- STEP
実際に動かしてみる
下記リンクよりColabを起動し、[ランタイム]_[すべてのセルを実行]で実行出来ます。
基本的には Colab のソースを確認下さい。
1. Colabにてdash_cytoscapeを使用するためのライブラリをインストールする
!pip install jupyter-dash !pip install dash_bootstrap_components !pip install dash_cytoscape2. 可視化用webアプリの基底クラスとしてJupyterDashを継承したクラスを作成する
from jupyter_dash import JupyterDash import dash_bootstrap_components as dbc class JupyterDashBootStrap(JupyterDash): def __init__(self, _title, _port): super().__init__(__name__, external_stylesheets=self.__external_stylesheets()) if _title is not None: self.title = _title self.__setlayout() self.__run(_port) def __setlayout(self): self.layout = self.buildbaselayout() self.registcalback(self) def buildbaselayout(self): return def registcalback(self, app): return def __run(self, _port): if _port is None: self.run_server(mode="external") else: self.run_server(mode="external", port=_port ) def __external_stylesheets(self): return [dbc.themes.BOOTSTRAP]3. networkxを使用してグラフ（node、edge、weight）を定義する関数を定義する
※コード量が多いため省略。Colab を直接ご確認ください。
4. networkxを使用して3で作成したグラフの重み最大マッチング問題を解く関数を定義する
import re import copy def com_replace(_s): ''' dashではidに","（カンマ）は使えないため置換する。 ※カンマをそのまま置換するとjson形式が崩れるため注意が必要 ※(1, 1)->1 ''' pattern = r'(\d{1,4}?), (\d{1,4}?)' result = re.sub(pattern, r'\1_\2', str(_s)) return result def CreateGraphAndMax_weight_matching(): G = CreateGraph() # 重み最大マッチング mw = nx.max_weight_matching(G) # 扱いやすいように重み最大マッチングの結果のノード名を置換してリストに格納する mw_list = [] for a in mw: fromtolist = [] for b in a: fromtolist.append((com_replace(b))) mw_list.append(fromtolist) return G, mw_list5. 基底クラスを継承してwebアプリを定義したクラスを作成する
※コード量が多いため省略。Colab を直接ご確認ください。
※layoutやstylesheetへの設定値については下記をご参考ください
6. タイトル名とポート番号を指定してwebアプリを実行する
MyDashCytoscape("*** networkx2cytoscape ***", 8881)実行すると下図のようなグラフが可視化されます。
各edgeに重みが付与されていますが、よく見る中央部分がラベルが重なって解りづらいです。
実は、dash_cytoscapeを使って可視化すると各nodeをマウスでドラッグして移動させることができます。
移動させることで重みのラベルが見やすくなります。
最後に
今回は、動くプログラムを優先したので、グラフ理論やマッチング理論の理論的背景は省略しました。
さらに理解を深めたという方たちは↓を参考にしてください。
忠犬SE
【付録】さらに理解を深めたいという方たちへのおすすめ本
Pythonで学ぶネットワーク分析 ColaboratoryとNetworkXを使った実践入門
Pythonインタラクティブ・データビジュアライゼーション入門
【付録】さらに理解を深めたいという方たちへ①
理解を深めるためには、実際に動かしてみるのが一番です。
下記テーマを参考に、色々と動かしてみてはいかがでしょうか？
- CSVファイルを読み込んでグラフを定義出来るようにする
- nodeの数やedgeの数を増やしていって数処理速度がどのように変化するか可視化する
ご参考
ちなみに今回は下記 Chromebook を使用しました。
14.0型フルHD × Core i3 × メモリ8GB を満たす数少ない端末です。
軽くて持ち運びしやすく開発に耐えうるスペックなのでおすすめです。
 | 価格:70,510円 |
Chromebook でプログラミングを始める方法については下記記事をご参考下さい。
