python: NetworkX によるグラフのパス列挙

今日は、NetworkXを使ったグラフの パスの列挙 を紹介します。

グラフの任意の２つのノードが与えられたとき、その２点を始点終点とするパスを列挙します。厳密には、単純道(simple path)を列挙します。単純道とは、簡単に言えば、同じノードが複数回パスに現れないものをいいます。

今日は、重み付き有向グラフ を例に、パスを列挙したいと思います。もちろん、重み無しでも、無向グラフでも適用可能です。

いろいろ調べましたが、パスの列挙は NetworkX にメソッドがありますが、パスに含まれる辺の重みの合計を出力することができないようです。重みの合計が知りたかったので、そこのコードも紹介します。

重み付き有向グラフの読み込みと可視化

まず、パスを探索するためにグラフを作ります。可視化をする必要はありませんが、ついでに可視化します。

読み込みと可視化については、以下の記事で紹介した方法です。

www.letsopt.com

まず、読み込ませたいテキストファイルはこちら。

下記のコードは、まず上記のテキストファイルを読み込んで、グラフを出力します。

# パッケージのインポート
import matplotlib.pyplot as plt
import networkx as nx

# 有向グラフの作成
G = nx.DiGraph()

# 重み付きのファイルの読み込み
G = nx.read_weighted_edgelist('graph_data5.txt', nodetype=int, create_using=nx.DiGraph)

# グラフの描画
pos = nx.spring_layout(G)
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)
nx.draw_networkx(G, pos, with_labels=True, alpha=0.5)

# 表示
plt.axis("off")
plt.show()

結果

f:id:cresselia2012:20191114222035p:plain

有向グラフで辺の向きによって重みが違う場合、上記の可視化方法ではどちらが出力されるか不明ですので、ご注意ください。

パスの列挙&パスに含まれる辺の重みの合計の計算

ここからが今日のメインの内容です。

上記のコードに続き

# パスに含まれる辺の重みの合計を計算
def path_total_weight(path, edge_labels):
    total = 0
    for i in range(len(path)-1):
        total += edge_labels[(path[i],path[i+1])]
    return total

# edge_labels を出力
print('edge_labels:')
print(edge_labels)

# ノード１ -> ノード6 のパスを列挙
print('1 -> 6 paths:')
for path in nx.all_simple_paths(G, source=1, target=6):
    print(f'path: {path}', end=", ")
    print(f'total_weight: {path_total_weight(path, edge_labels)}')

結果

edge_labels:
{(1, 3): 5.0, (3, 2): 9.0, (3, 4): 5.0, (2, 3): 8.0, (4, 3): 7.0, (4, 5): 3.0, (4, 6): 5.0, (5, 6): 4.0}
1 -> 6 paths:
path: [1, 3, 4, 5, 6], total_weight: 17.0
path: [1, 3, 4, 6], total_weight: 15.0

今回の例では、ノード1 を始点とし、ノード6 を終点とするパスを列挙しています。

パスの列挙自体は、NetworkX のメソッドである all_simple_paths(Graph, source, target) を使用しています。これを呼び出すと、パスのリストを取得することができます。今回の例では、1→6のパスは２つあり、それらが出力されました。

変数 edge_labels には、始点終点に対応する重みが格納されているます。

関数 path_total_weight(path, edge_labels) は与えられた path に格納された連続したノードを使って、edge_labels から重みを取り出し、合計の重みを計算し返します。

以上、パスの列挙のご紹介でした〜。