グラフ理論の例題 NetworkX

NetworkX

PythonのライブラリであるNetworkXは、グラフ理論を扱う際に便利なツールです。

このライブラリを使うことで、グラフ理論の様々な問題を解決することができます。

例えば、グラフの可視化グラフの検索グラフの解析などが挙げられます。

1. 最短経路を求める

以下のようなグラフがあるとします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=1)

nx.draw(G, with_labels=True)
plt.show()

[実行結果]

このグラフでは、ノード同士を結ぶエッジには重みが設定されています。

このグラフで、ノードAからノードDへの最短経路を求めるには、以下のコードを実行します。

[Google Colaboratory]

1
2
shortest_path = nx.shortest_path(G, source='A', target='D', weight='weight')
print("最短経路は", shortest_path, "です。")

このコードでは、nx.shortest_path()を用いて最短経路を求めています。

weight=’weight’を指定することで、エッジの重みを考慮した最短経路が求められます。

[実行結果]

最短経路は ['A', 'C', 'D'] です。

2. 最小全域木を求める

以下のようなグラフがあるとします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_weighted_edges_from([('A', 'B', 4), ('A', 'H', 8), ('B', 'C', 8), ('B', 'H', 11), ('C', 'D', 7), ('C', 'F', 4), ('C', 'I', 2), ('D', 'E', 9), ('D', 'F', 14), ('E', 'F', 10), ('F', 'G', 2), ('G', 'H', 1), ('G', 'I', 6), ('H', 'I', 7)])

nx.draw(G, with_labels=True)
plt.show()

[実行結果]

このグラフは、9つの頂点と14本の辺を持つ重み付きグラフです。

このグラフの最小全域木を求めるには、以下のコードを実行します。

[Google Colaboratory]

1
2
T = nx.minimum_spanning_tree(G)
print("最小全域木の辺は", T.edges(data=True), "です。")

このコードでは、nx.minimum_spanning_tree()を用いて最小全域木を求めています。

求められた最小全域木の辺は、辞書形式で返されます。

[実行結果]

最小全域木の辺は [('A', 'B', {'weight': 4}), ('A', 'H', {'weight': 8}), ('H', 'G', {'weight': 1}), ('C', 'I', {'weight': 2}), ('C', 'F', {'weight': 4}), ('C', 'D', {'weight': 7}), ('D', 'E', {'weight': 9}), ('F', 'G', {'weight': 2})] です。

まとめ

今回は、NetworkXを用いてグラフ理論の問題を解決する例題を2つ挙げてみました。

NetworkXは非常に豊富な機能を持っているため、様々な問題に対して適用することができます。