Google Colaboratory で二部マッチング問題を解いて networkx で可視化する方法

5 min

※本記事はChromebookを使用して執筆しました

広告_零号機

こんなお困りごとはないですか?

pythonビギナー

pythonビギナー

Pythonの扱いには慣れてきたけど、実社会の問題を解いてみたいわ。

例えば、最近マーケットデザインという分野が流行っているようだけど、実際にPythonで実装して体験してみたいわ。

解決方法は?

あるよ。

忠犬SE

忠犬SE

マーケットデザインではマッチング理論が扱われているんだけど、マッチング理論の二部グラフの1対1のマッチング問題についてはグラフ理論を使えば解けるよ。

二部グラフの1対1のマッチング問題については『史上空前!! 笑いの祭典 ザ・ドリームマッチをイメージすると解りやすいいよ。

忠犬SE

忠犬SE

史上空前!! 笑いの祭典 ザ・ドリームマッチ

普段テレビでなかなかネタを披露することのない中堅クラスの人気お笑い芸人たちをシャッフルして即席コンビを結成させ、ネタを披露し合うコンテスト形式の番組。

『史上空前!! 笑いの祭典 ザ・ドリームマッチ』 ウィキペディア

例えば、5人のボケと5人のツッコミがいて、可能なかぎり相思相愛のコンビを作ることを考えよう。

各ボケが、5人のツッコミから上位3位までを選択し、順位が良い順に「3ポイント、2ポイント、1ポイント」付与して、各ツッコミも同様に、5人のボケから上位3位までを選択しポイントを付与したとするよ。

このとき、ポイントが最大になるような組み合わせ(=可能なかぎり相思相愛)を考えることを重み最大マッチング問題というんだ。

※実際にはコンビを決めるあのやりとり含めてザ・ドリームマッチの面白みなのだが。。。

重み最大マッチング問題を解いた結果が下図だよ。

5人のボケ(ネイビー)と5人のツッコミ(レッド) のペアが太線で表現されているよ。太線が引かれていないのはいわゆる残り物だね。

忠犬SE

忠犬SE

ここでは、Pythonのnetworkxというライブラリを使用してグラフの定義と重み最大マッチング問題を解いて、解いた結果をdash_cytoscapeというdashフレームワークのコンポーネントを使って可視化しているよ。

早速始めてみよう。

忠犬SE

忠犬SE

networkxでマッチング問題を解いてdash_cytoscapeで可視化する

流れ

  • 全体の概要を理解する
  • colabノートブックを作成する
  • 実際に動かしてみる
  1. STEP

    全体概要を理解する

    可視化については、下記記事を参考にしてwebアプリを作成します。

    1. Colabにてdash_cytoscapeを使用するためのライブラリをインストールする
    2. 可視化用webアプリの基底クラスとしてJupyterDashを継承したクラスを作成する
    3. networkxを使用してグラフ(node、edge、weight)を定義する関数を定義する
    4. networkxを使用して3で作成したグラフの重み最大マッチング問題を解く関数を定義する
    5. 基底クラスを継承してwebアプリを定義したクラスを作成する
      • 4の関数を実行してグラフと重み最大マッチング問題を解いた結果を取得する
      • networkxのグラフオブジェクトをdash_cytoscapeで使用可能なデータ形式に変換
      • 条件を指定してnodeの色を設定
      • 重み最大マッチング結果に該当edgeの色を変更
    6. タイトル名とポート番号を指定してwebアプリを実行する
  2. STEP

    Colabのノートブックを作成する

    下記記事などを参考に、Colabで新しいノートブックを作成します。

  3. STEP

    実際に動かしてみる

    下記リンクよりColabを起動し、[ランタイム]_[すべてのセルを実行]で実行出来ます。
    基本的には Colab のソースを確認下さい。

    Open In Colab

    1. Colabにてdash_cytoscapeを使用するためのライブラリをインストールする

    !pip install jupyter-dash
    !pip install dash_bootstrap_components
    !pip install dash_cytoscape

    2. 可視化用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_list

    5. 基底クラスを継承してwebアプリを定義したクラスを作成する

    ※コード量が多いため省略。Colab を直接ご確認ください。

    ※layoutやstylesheetへの設定値については下記をご参考ください

    6. タイトル名とポート番号を指定してwebアプリを実行する

    MyDashCytoscape("*** networkx2cytoscape ***", 8881)

    実行すると下図のようなグラフが可視化されます。

    各edgeに重みが付与されていますが、よく見る中央部分がラベルが重なって解りづらいです。

    実は、dash_cytoscapeを使って可視化すると各nodeをマウスでドラッグして移動させることができます。

    移動させることで重みのラベルが見やすくなります。

最後に

今回は、動くプログラムを優先したので、グラフ理論やマッチング理論の理論的背景は省略しました。

さらに理解を深めたという方たちは↓を参考にしてください。

忠犬SE

忠犬SE

【付録】さらに理解を深めたいという方たちへのおすすめ本

Pythonで学ぶネットワーク分析 ColaboratoryとNetworkXを使った実践入門

Pythonインタラクティブ・データビジュアライゼーション入門

【付録】さらに理解を深めたいという方たちへ①

理解を深めるためには、実際に動かしてみるのが一番です。

下記テーマを参考に、色々と動かしてみてはいかがでしょうか?

  1. CSVファイルを読み込んでグラフを定義出来るようにする
  2. nodeの数やedgeの数を増やしていって数処理速度がどのように変化するか可視化する

ご参考

ちなみに今回は下記 Chromebook を使用しました。
14.0型フルHD × Core i3 × メモリ8GB を満たす数少ない端末です。
軽くて持ち運びしやすく開発に耐えうるスペックなのでおすすめです。

富士通|FUJITSU ノートパソコン FMV Chromebook 14F(タッチパネル) ダーククロム FCB143FB [14.0型 /Chrome OS /intel Core i3 /メモリ:8GB /SSD:128GB /タッチパネル対応 /2021年12月モデル]【point_rb】

価格:70,510円
(2022/2/23 18:35時点)
感想(1件)

Chromebook でプログラミングを始める方法については下記記事をご参考下さい。

広告_零号機-エリア2
kewton

kewton

大学院卒業後、某大手SIerで10年以上SEとして従事。
社会人3年目までに基本情報・応用情報技術者、データベーススペシャリスト、簿記3級・2級を取得。
基幹系システム・IoTシステム開発のプロジェクト経験多数。AI活用システムの企画・プロト開発経験あり。
強みは、プロマネだけでなく自身で開発も実施してきたこと。
【扱える言語】
C#、java、python、javascript、Excel VBA
【扱えるDB】
oracle、sql server、postgreSQL、mongoDB

FOLLOW

関連記事

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA