Pythonでグラフ（ネットワーク）を簡単に扱えるツールとして，NetworkXがあります．
この記事では，NetworkXの基本的な使い方を紹介します．
NetworkXとは？
NetworkXは，グラフ理論やネットワーク理論系の計算を行うためのPythonのパッケージです．
普通に書くよりも簡単にグラフが定義できたり，図を作ったりできます（matplotlibなどと併用します）．
また，ノード間の最短経路を求めたりするいくつかの探索関数が用意されています．
この記事の目標
以降では，実際にNetworkXを使ってみたいと思います．
この記事の目標は，以下の通りです．
NetworkXの基本的な使い方を習得する
参考にした記事はこの記事の最後に載せてあります．
NetworkXの基本的な使い方
まずは，NetworkXの基本的な機能を使ってみたいと思います．
NetworkXのインストール
インストールは，pipでできます．
pip install network
グラフ：ノードとエッジから成る．
ノード：グラフでの「点」のこと．節点，頂点とも呼ばれる．
エッジ：ノードとノードを結ぶ線のこと．辺，枝とも呼ばれ，ネットワークの界隈ではリンクとも呼ばれる．エッジには向きと長さを考えることができる．
簡単なグラフを表示する
以下のように書けば，ノードとエッジが生成されます．matplotlibで可視化しています．
import networkx as nx
import matplotlib.pyplot as plt
# Graphオブジェクトの作成
G = nx.Graph()
# nodeデータの追加
G.add_nodes_from(["A","B","C","D","E"])
# edgeデータの追加
G.add_edges_from([("A", "B"), ("B", "C"),("A", "C"),("D", "E"),("C", "E")])
# ネットワークの可視化
nx.draw(G, with_labels = True)
plt.show()
ちなみに，以下でノードやエッジを追加したり，削除したりできます．
# 頂点の追加
G.add_node("F")
# 辺の追加 (頂点も必要に応じて追加される)
G.add_edge("A", "F")
# 辺の削除
G.remove_edge("B", "C")
G.remove_edges_from([("A", "F"), ("A", "B")])
# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node("F")
G.remove_nodes_from(["A", "B"])
また，何かと便利なのでノード数とエッジ数を確認する関数を紹介しておきます．
#ノード数とエッジ数を出力
print('ノード数：',nx.number_of_nodes(G))
print('エッジ数：',nx.number_of_edges(G))
ノード数： 5
エッジ数： 5
これで，とりあえず指定した名前のノードを置き，指定したエッジを設定することはできました．
しかし，現段階ではノードの座標やエッジの距離の情報は自動で設定されておらず，描画は自動でされています．
今回の目標は「自分で設定したグラフ上で巡回セールスマン問題を解く」ことなので，ノードの座標もしくはエッジの距離を自分で設定したいです．
ノードの座標を設定する
はじめに生成したグラフで話を進めます．ノードやエッジを削除した場合は，もう一度はじめのグラフに戻した方が分かりやすいと思います．
ノードの座標を設定するには，座標を定義した後，オプションとしてposを設定します．
# nodeの座標を設定
pos = {
"A": (1, -1),
"B": (1, 0.5),
"C": (-0.5, 2),
"D": (0, 0),
"E": (-1, 0.5),
}
# ネットワークの可視化
nx.draw(G, pos=pos, with_labels = True)
plt.show()
ノードの座標が決まれば，各エッジの距離も自動的に決まりますね．
描画しただけではきちんと設定されているのか分からないので，エッジの距離を見てみましょう．グラフに関する問題ではノードの関係性を考えることが重要なので，エッジの距離だけ見れば十分です．
#ノード間の距離を計算する
print(G.edges)
for e in G.edges:
distance = np.sqrt((pos[e[0]][0]-pos[e[1]][0])**2+(pos[e[0]][1]-pos[e[1]][1])**2)
print('edge', e, '距離 = ', distance)
[(‘A’, ‘B’), (‘A’, ‘C’), (‘B’, ‘C’), (‘C’, ‘E’), (‘D’, ‘E’)]
edge (‘A’, ‘B’) 距離 = 1.5
edge (‘A’, ‘C’) 距離 = 3.3541019662496847
edge (‘B’, ‘C’) 距離 = 2.1213203435596424
edge (‘C’, ‘E’) 距離 = 1.5811388300841898
edge (‘D’, ‘E’) 距離 = 1.118033988749895
ノード間の距離が取得できることが確認できました．
基本的な情報を取得する
# ノードの一覧
print(list(G.nodes))
# エッジの一覧
print(list(G.edges))
他にも色々あるようです．
経路探索関数
NetworkXにはいくつかの関数が用意されています．後々使えそうなので，いくつか使ってみます．
# 2点間の最短経路
print(nx.shortest_path(G, source="A", target="D"))
#['A', 'C', 'E', 'D']
# 指定した点から各点への最短経路
print(nx.shortest_path(G, source="C"))
#{'C': ['C'], 'B': ['C', 'B'], 'A': ['C', 'A'], 'E': ['C', 'E'], 'D': ['C', 'E', 'D']}
# 各点から指定した点への最短経路
print(nx.shortest_path(G, target="D"))
#{'D': ['D'], 'E': ['E', 'D'], 'C': ['C', 'E', 'D'], 'B': ['B', 'C', 'E', 'D'], 'A': ['A', 'C', 'E', 'D']}
# 各点から各点への最短経路
print(nx.shortest_path(G))
#{'A': {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'E': ['A', 'C', 'E'], 'D': ['A', 'C', 'E', 'D']}, ... 'E': {'E': ['E'], 'D': ['E', 'D'], 'C': ['E', 'C'], 'B': ['E', 'C', 'B'], 'A': ['E', 'C', 'A']}}
# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
print(list(nx.all_simple_paths(G, source="D", target="A")))
#[['D', 'E', 'C', 'B', 'A'], ['D', 'E', 'C', 'A']]
これを使って，色々な問題が解けそうですね．
参考にした記事
コメント