#はじめに
動的最適化やグラフについて色々調べているうちに、NetworkXなるPythonライブラリを見つけ、
色々とやってみたことをまとめようと記事を投稿してみました。
かなり内容が散逸しているため、先に注意点だけまとめておきます。
- NetworkXやグラフ理論について汎用的にまとめているわけではないです
- ダイキストラ法の説明はしていません
- 掲載している内容を凝縮するとこんな感じ(興味なければスルーで！！！)
- NetworkXによってランダムにグラフを生成及びそれを無向グラフにする方法
- NetworkXの組み込み関数を用いずにダイキストラ法を再現する方法
- グラフの表示方法（エッジにおける重みなどの表示も含む）
#NetworkXとは
Pythonでグラフを作成するライブラリです。
様々なグラフの作成（当方はグラフを専門に扱っているわけではないのであんま詳しくないです）を
汎用的にできるほか、それに関わるアルゴリズムも扱うことができるという優れもの。
2021年3月2日現在ではインストールできるみたいです。（conda環境）
$ conda install -c conda-forge networkx
なお、グラフの可視化に別のライブラリortoolpyを使っているのですが、
これについては、pipでしかインストールできませんでした。
$ pip install ortoolpy
#実装内容
##必要となるライブラリのインポート
import heapq #実装部分に使用
from collections import defaultdict #実装部分に使用
import networkx as nx #NetworkX本体
import numpy as np
from ortoolpy import networkx_draw #グラフの描画に使用
import matplotlib.pyplot as plt #グラフの描画に使用
##ランダムグラフの作成と無向グラフ化
まず、ランダムにそれっぽいグラフを作りたい場合はこんな感じで、
#ノードの数
n = 7
#辺ができる確率
p = 0.3
#乱数のシード値
seed = 34
g = nx.random_graphs.fast_gnp_random_graph(n, p, seed, directed = True)
ここでは、経路を調べるのに利用したいので
(directed = True)として連結グラフに限定しています。
なお、ノード数に対してpが小さすぎる場合はきちんとエラーを吐きます。
ここで、グラフの表示を行う(詳細は次の説明にて)と
両矢印だったり、片矢印だったりかなりバラバラになっています。
今回は特に方向を明記する必要性はないので、方向の情報を消していきます。
やり方は簡単で、
g = g.to_undirected()
と付け足してあげれば、
となり、方向情報が消されていることがわかります。
（ラベルの情報が違うのはご愛嬌、対応関係はあっているはず）
##作成したグラフの表示
グラフの表示を行う前に、
各エッジについて重み(ここでは辺の上に表示させたいラベル)を設定しておきます。
for i, j in g.edges():
v = 2 + 7* np.random.rand()
v = int(100 * v) / 100. #コンマ以下の数字を2桁に
#Nodes_list[i].weights[j] = v
#Nodes_list[j].weights[i] = v
g.adj[i][j]['weight'] =v
この「weight」に代入したものが辺の上に表示させたい値となります。
ここで、いよいよグラフを表示していきます。
とはいっても大したことはなく、こんな感じのを書くだけで問題なく表示できます。
##グラフの出力部分
plt.figure(figsize=(6,6))
pos = networkx_draw(g, nx.spring_layout(g)) #点と線だけならここまででおｋ
labels = nx.get_edge_attributes(g,'weight')
nx.draw_networkx_edge_labels(g,pos,edge_labels=labels)
plt.show()
ラベルを表示（広く言えば辺の上になにかを表示）させたいということなら、
後半部分が重要になりそうです。
##ダイキストラ法を組み込み関数を使わずに実装してみた
###組み込み関数や参考ページ
NetworkXにおいて、どの道を通れば、最も少ないコストでいけるのかを知りたければ、
次の関数を実行すれば瞬殺できます。（ただし、無向グラフのままだとダメなようです。）
#G はグラフのクラス
#source, targetはそのままの意味、ただしint型
#weightは重みとして参照するキー(string型)
nx.dijkstra_path(G, source, target, weight='weight')
nx.dijkstra_path_length(G, source, target, weight='weight')
流石にそれでは味気ない（主観）ので、
これを使わずに最短経路の探索アルゴリズムの一つである
ダイキストラアルゴリズムを作ってみました。
アルゴリズムの概要については→こちら
参考にしたコード(アルゴリズムも載ってるけど．．．理解力が足りなかった)については→こちら
をそれぞれ見てください。
###実装
ただ、スタートとゴールを自由に設定したかったのと、
なけなしのプライドにより、もとのコードをほぼ見ないで書いているため、
かなり改造しています。
もう後に残るのはぶっちゃけ趣味の領域です。
コードを載せるとこんな感じです。
import heapq # heapqライブラリのimport
from collections import defaultdict
import networkx as nx
import numpy as np
from ortoolpy import networkx_draw
import matplotlib.pyplot as plt
#ノードクラス
class Node():
def __init__(self, id):
self.reset()
self.id = id
def reset(self):
self.weights = defaultdict() #ここでdefaultdictを採用
self.done = False #確定したノードかどうか(確定フラグと表記)
self.path = [] #経路
self.cost = 1e10 #スタートから自身のノードまでにかかる重みの合計
def show_info(self):
print('id : {}'.format(self.id))
print('done : {}'.format(self.done))
print('path', self.path)
print('cost : {}'.format(self.cost))
print()
#グラフ生成(前述)
n = 7
ratio = 0.3
seed = 34
g = nx.random_graphs.fast_gnp_random_graph(n, ratio, seed = seed, directed= True)
g = g.to_undirected()
#ノード並びに各重みの設定
Nodes_list = [Node(i) for i in range(n)]
for i, j in g.edges():
v = 2 + 7* np.random.rand()
v = int(100 * v) / 100.
Nodes_list[i].weights[j] = v
Nodes_list[j].weights[i] = v
g.adj[i][j]['weight'] =v
######ダイキストラアルゴリズム本体
start_index = 2 #スタートノード（のindex）を設定
Nodes_list[start_index].cost = 0
Nodes_list[start_index].path = [start_index] #当たり前だが、初期値点から初期値点までの経路
#スタート地点のノードをキューに入れておく
candidates =[(0, Nodes_list[start_index])]
while len(candidates) > 0:
#キューからノードを読み込む
(c, Node_n) = heapq.heappop(candidates)
#キューに追加した時点におけるコストが今のノードのコストよりも大きければ無視
if c > Node_n.cost:
continue
#読み込まれたノードに確定フラグをつける
Node_n.done = True
#この場合は、ノードのindexがmとして呼ばれる
for m in Node_n.weights:
weight = Node_n.weights[m]
Node_m = Nodes_list[m]
cost = Node_n.cost + weight
#コストが小さくなれば更新、このときNode_mに確定フラグがついていないことを確認
if cost < Node_m.cost and Node_m.done == False:
Node_m.cost = cost #重みを更新
#キューから読み込んだノードまでの経路情報を読み込む
path = [ip for ip in Node_n.path]
#Node_mのindexを経路の末尾に追加
path.append(Node_m.id)
#こうして得られた経路をNode_mのpathに代入
Node_m.path = path
#キューに投入
heapq.heappush(candidates, (cost, Node_m))
優先度付きキューとdirectdictをバンバン活用しています。
特に、defaultdictについてはもとのコードとは使う部分が微妙に異なっています。
###結果
こんなグラフで
こんな結果が得られます。
##グラフの出力部分
plt.figure(figsize=(6,6))
pos = networkx_draw(g, nx.spring_layout(g))
labels = nx.get_edge_attributes(g,'weight')
nx.draw_networkx_edge_labels(g,pos,edge_labels=labels)
#各ノード情報の出力
[Node.show_info() for Node in Nodes_list]
plt.show()
'''
id : 0
done : True
path [2, 0]
cost : 4.12
id : 1
done : True
path [2, 4, 1]
cost : 9.51
id : 2
done : True
path [2]
cost : 0
id : 3
done : True
path [2, 4, 3]
cost : 6.58
id : 4
done : True
path [2, 4]
cost : 2.93
id : 5
done : True
path [2, 0, 5]
cost : 7.85
id : 6
done : True
path [2, 4, 6]
cost : 6.91
'''
多分大丈夫かな？
#雑記・コメント
NetworkXを軽く触ってみた感想として、かなり便利では？というのが本音。
利用できるアルゴリズムも豊富な上(中身が気になってしまうので実装してみたくはなってしまうが。。。)、
それ抜きにしてもグラフデータを扱う機会があるなら真っ先に使いたいと思いました。
公式リファレンスはこちらになります。