LoginSignup
3
0

More than 3 years have passed since last update.

@o_range(Takahiro Maekawa)

NetworkXによるランダムグラフ生成＆プロットとダイキストラ法による最短経路アルゴリズムを試してみた話

Last updated at Posted at 2021-03-02

はじめに

動的最適化やグラフについて色々調べているうちに、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が小さすぎる場合はきちんとエラーを吐きます。

ここで、グラフの表示を行う(詳細は次の説明にて)と
Figure_0０.png
両矢印だったり、片矢印だったりかなりバラバラになっています。
今回は特に方向を明記する必要性はないので、方向の情報を消していきます。
やり方は簡単で、

無向グラフ化

g = g.to_undirected()

と付け足してあげれば、
Figure_1.png

となり、方向情報が消されていることがわかります。
（ラベルの情報が違うのはご愛嬌、対応関係はあっているはず）

作成したグラフの表示

グラフの表示を行う前に、
各エッジについて重み(ここでは辺の上に表示させたいラベル)を設定しておきます。

各エッジに対応する重みの設定
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」に代入したものが辺の上に表示させたい値となります。

ここで、いよいよグラフを表示していきます。
とはいっても大したことはなく、こんな感じのを書くだけで問題なく表示できます。

NetworXによるグラフの表示
##グラフの出力部分
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についてはもとのコードとは使う部分が微妙に異なっています。

結果

こんなグラフで
Figure_2.png

こんな結果が得られます。

結果
##グラフの出力部分
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を軽く触ってみた感想として、かなり便利では？というのが本音。
利用できるアルゴリズムも豊富な上(中身が気になってしまうので実装してみたくはなってしまうが。。。)、
それ抜きにしてもグラフデータを扱う機会があるなら真っ先に使いたいと思いました。
公式リファレンスはこちらになります。

3
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0