乗換案内をPythonで作ろう!最短経路探索アルゴリズムのUI実装
見出し画像

乗換案内をPythonで作ろう!最短経路探索アルゴリズムのUI実装

みなさんこんにちは。ときかねえさんです♪

最近、早稲田大学・早水桃子先生の「離散数学入門#5最短経路問題」解説動画を見ました。それがとてもわかりやすく素敵な講義だったので、動画内例題の最短経路問題を解く簡易版乗換案内を作ってみました。

早水先生の講義では、解法の一つであるダイクストラ法がひじょ〜にわかりやすく解説されています。逆茂木がない見事な構成やリマインドのタイミングが絶妙でこういう素晴らしい解説にはとても憧れます。

講義の中で、東京-小田原間の最短経路探索を例題として上げていました。今回は、その例題に対してダイクストラ法を用いた最短経路探索を行う以下のようなアプリを作成します。最短経路探索と描画を行うのものですが、除外する駅をラジオボタンで選択するとリアルタイムで再探索&再描画を行うものです(図1, 2)。

画像1

図1 "除外しない"を選んだ場合

画像2

図2 "新横浜"を除外した場合

以下に順を追って解説します。コードの完全版のみ見たいor欲しいという方は文末をご参照ください♪

ライブラリのインポートと必要なデータの準備

今回もUI設計にはstreamlitを用います。streamlitは便利ですが、深いところにはなかなか触れなかったので私も最近webアプリ開発用に別の言語の勉強もしていました。今回の実装もインタラクティブなグラフ操作が入りますので、作り始めた当初はさすがに今回ばかりはstreamlitだけでは難しいかなとあきらめていましたがなんとかなりました。そのかいあって(?)未経験言語の習得は一向に進まずなんだかpython以外を回避する技術だけがどんどん上がっていってるような気がします。汗

扱うデータとしては、ノードである駅の名称リストとそのインデックス、描画のための駅座標の配列、エッジである駅間重み(所要時間などのコスト)の行列が必要となりますので以下のように定義しておきます。

# -*- coding: utf-8 -*-
import streamlit as st
import streamlit.components.v1 as components
import numpy as np
import networkx as nx
from pyvis.network import Network

st.title('ダイクストラ法のデモ') # タイトル

stations=['東京','品川','渋谷','新宿','新横浜','横浜','小田原'] # 駅名のリスト
sidx=list(range(len(stations))) # 駅名のインデックス
pos=list([[-4,0],[-1,0],[0,2],[-1,-2],[2,0],[3,-2],[5,0]]) # 描画のための駅の座標
# 駅間の所要時間の行列
w=[[ 0, 8,16,15, 0, 0, 0],
  [ 8, 0,13,21,10,17, 0],
  [16,13, 0, 0,27, 0,78],
  [15,21, 0, 0, 0,33, 0],
  [ 0,10,27, 0, 0,13,15],
  [ 0,17, 0,33,13, 0,52],
  [ 0, 0,78, 0,15,52, 0],
  ]

Radio Buttonの配置

今回はUIとしてRadioButtonを使用します。st.radioで定義できます。このradioで選択された駅を上記のリストから削除する操作が以下のように続きます。

# Radio buttonに用いる文字列
stlist=stations[1:-1] #Startの東京,Goalの小田原以外
stlist.append('除外しない') # '除外しない'を追加
removed_station=st.radio('除外する駅名',stlist) # Streamlitのradioを配置
# 選択されたitemのindex取得
idx=[i for i,s in enumerate(stations) if s==removed_station] 

# 条件に基づいた除外処理
if not idx: # '除外外しない'の場合
   pass
else: # 選択された駅をリストから削除
   idx=idx[0]
   stations.pop(idx) # 駅名リストから削除
   sidx.pop(idx) # 駅名インデックスから削除
   pos.pop(idx) # 駅座標から削除
   pos=np.array(pos) # 後のスライシングのためにnp.arrayにしておく
   # 結合行列から削除
   for i in range(len(w)):
       w[i].pop(idx)
   w.pop(idx)

ダイクストラ法を用いた最短経路探索

ダイクストラ法の箇所ですが、今回は車輪の再発明はせずにnetworkxの関数を用います。networkxの形式としてGraphオブジェクトを作成します。関数dijkstra_path, dijkstra_path_lengthを用いて最短経路その合計コストをそれぞれ求めます。

G =nx.Graph() # 新規のNetworkxオブジェクト
for i in range(len(stations)):
   for j in range(len(stations)):
       if w[i][j]>0:
           G.add_edge(i,j,weight=w[i][j])

start_idx=[i for i,s in enumerate(stations) if s=='東京'][0]
goal_idx=[i for i,s in enumerate(stations) if s=='小田原'][0]

# Dijkstra法を適用(networkxのライブラリ)
path=nx.dijkstra_path(G,start_idx,goal_idx) # 最短経路の探索
length=nx.dijkstra_path_length(G,start_idx,goal_idx) # 最短経路のコスト計算

ネットワーク図の描画

描画のために、上で求めた最短経路の部分グラフを駅ペアのリスト化します。また、求まった合計コストを表示します。

# 上で求めた最短経路を駅ペアのリストとして取得(描画のため)
path_pairs=list()
for i in range(len(path)-1):
   path_pairs.append([path[i],path[i+1]])

st.title(r'東京→小田原駅の最短経路')
'最短経路の合計コストは'+str(length)

ネットワーク描画には、pyvisNetworkオブジェクトを用います。ノード(駅)とエッジ(路線)をNetworkオブジェクトに追加します。最短経路内のパスは太い赤線で描画するようにします。

# Networkオブジェクトの用意
nt=Network("500px","700px",heading='')
# ノードを追加
for i in range(len(stations)):
   nt.add_node(i,label=stations[i],x=int(pos[i][0]*55),y=int(pos[i][1]*60))
# 以下で、nodeの物理効果をオフにする。
# オンのままだとある駅を動かすとnode間相互作用で他も動いてしまう
for n in nt.nodes:
   n.update({'physics':False})

# エッジを追加
for pair in G.edges:
   p=list(pair)
   col,wid=('red',10) if p in path_pairs else ('green',1) # 最短経路内のペアのみ太赤線にする
   nt.add_edge(p[0],p[1],color=col,width=wid,label=w[p[0]][p[1]]) # エッジの描画

Netwrokオブジェクトをhtmlファイルとして出力しstreamlitのcomponentに渡します。

# htmlファイルとして出力&表示
nt.show('test.html')
htmlfile=open('test.html','r',encoding='utf-8')
source=htmlfile.read()
components.html(source,height=800,width=900)

コードの完全版を以下に記します。

# -*- coding: utf-8 -*-
import streamlit as st
import streamlit.components.v1 as components
import numpy as np
import networkx as nx
from pyvis.network import Network

st.title('ダイクストラ法のデモ') # タイトル

stations=['東京','品川','渋谷','新宿','新横浜','横浜','小田原'] # 駅名のリスト
sidx=list(range(len(stations))) # 駅名のインデックス
pos=list([[-4,0],[-1,0],[0,2],[-1,-2],[2,0],[3,-2],[5,0]]) # 描画のための駅の座標
# 駅間の所要時間の行列
w=[[ 0, 8,16,15, 0, 0, 0],
  [ 8, 0,13,21,10,17, 0],
  [16,13, 0, 0,27, 0,78],
  [15,21, 0, 0, 0,33, 0],
  [ 0,10,27, 0, 0,13,15],
  [ 0,17, 0,33,13, 0,52],
  [ 0, 0,78, 0,15,52, 0],
  ]

# Radio buttonに用いる文字列
stlist=stations[1:-1] #Startの東京,Goalの小田原以外
stlist.append('除外しない') # '除外しない'を追加
removed_station=st.radio('除外する駅名',stlist) # Streamlitのradioを配置
idx=[i for i,s in enumerate(stations) if s==removed_station] # 選択されたitemのindex取得
if not idx: # '除外外しない'の場合
   pass
else: # 選択された駅をリストから削除
   idx=idx[0]
   stations.pop(idx) # 駅名リストから削除
   sidx.pop(idx) # 駅名インデックスから削除
   pos.pop(idx) # 駅座標から削除
   pos=np.array(pos) # 後のスライシングのためにnp.arrayにしておく
   # 結合行列から削除
   for i in range(len(w)):
       w[i].pop(idx)
   w.pop(idx)

G =nx.Graph() # 新規のNetworkxオブジェクト
for i in range(len(stations)):
   for j in range(len(stations)):
       if w[i][j]>0:
           G.add_edge(i,j,weight=w[i][j])

start_idx=[i for i,s in enumerate(stations) if s=='東京'][0]
goal_idx=[i for i,s in enumerate(stations) if s=='小田原'][0]

# Dijkstra法を適用(networkxのライブラリ)
path=nx.dijkstra_path(G,start_idx,goal_idx) # 最短経路の探索
length=nx.dijkstra_path_length(G,start_idx,goal_idx) # 最短経路のコスト計算

# 上で求めた最短経路を駅ペアのリストとして取得(描画のため)
path_pairs=list()
for i in range(len(path)-1):
   path_pairs.append([path[i],path[i+1]])

st.title(r'東京→小田原駅の最短経路')
'最短経路の合計コストは'+str(length)

# Networkオブジェクトの用意
nt=Network("500px","700px",heading='')
# ノードを追加
for i in range(len(stations)):
   nt.add_node(i,label=stations[i],x=int(pos[i][0]*55),y=int(pos[i][1]*60))
# 以下で、nodeの物理効果をオフにする。
# オンのままだとある駅を動かすとnode間相互作用で他も動いてしまう
for n in nt.nodes:
   n.update({'physics':False})

# エッジを追加
for pair in G.edges:
   p=list(pair)
   col,wid=('red',10) if p in path_pairs else ('green',1) # 最短経路内のペアのみ太赤線にする
   nt.add_edge(p[0],p[1],color=col,width=wid,label=w[p[0]][p[1]]) # エッジの描画

# htmlファイルとして出力&表示
nt.show('test.html')
htmlfile=open('test.html','r',encoding='utf-8')
source=htmlfile.read()
components.html(source,height=800,width=900)

以上です。実行は以下のようにします。

streamlit run ファイル名.py

最短経路探索の箇所と描画の箇所に若干重複がありますので、その辺りを改善すればもっと短く書けると思います。駅や路線の総数や重みの項目(料金や混雑具合など)を増やし、UIを充実させていけばどんどん本格的なアプリになります。(ただし、ノード数が大きすぎるとリアルタイム描画が難しくなったりもしますので注意が必要です。)

楽しんでいただけましたでしょうか?
もしよろしければフォローやスキお願いしますね♪
この記事がみなさまのPythonコーディングのお役に立てればうれしいです♪

♪♪♪Have a nice coding day♪♪♪


追記:
2021年8月5日 内包表記のところを修正しました。


この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
スキありがとうございます❤️
サイエンス・プログラミング・ファイナンス好き筋トレ女子♪ 元ポスドク研究者→専業トレーダー挫折→現在AI関連開発&半自動株式投資。 AI, Fintech, Pytnon, 物理学, 心理学, 美容, 筋トレ ♪♪♪Have a nice coding day♪♪♪