NetworkX
PythonのライブラリであるNetworkXは、グラフ理論を扱う際に便利なツールです。
このライブラリを使うことで、グラフ理論の様々な問題を解決することができます。
例えば、グラフの可視化、グラフの検索、グラフの解析などが挙げられます。
1. 最短経路を求める
以下のようなグラフがあるとします。
[Google Colaboratory]
1 | import networkx as nx |
[実行結果]
このグラフでは、ノード同士を結ぶエッジには重みが設定されています。
このグラフで、ノードAからノードDへの最短経路を求めるには、以下のコードを実行します。
[Google Colaboratory]
1 | shortest_path = nx.shortest_path(G, source='A', target='D', weight='weight') |
このコードでは、nx.shortest_path()を用いて最短経路を求めています。
weight=’weight’を指定することで、エッジの重みを考慮した最短経路が求められます。
[実行結果]
最短経路は ['A', 'C', 'D'] です。
2. 最小全域木を求める
以下のようなグラフがあるとします。
[Google Colaboratory]
1 | import networkx as nx |
[実行結果]
このグラフは、9つの頂点と14本の辺を持つ重み付きグラフです。
このグラフの最小全域木を求めるには、以下のコードを実行します。
[Google Colaboratory]
1 | T = nx.minimum_spanning_tree(G) |
このコードでは、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は非常に豊富な機能を持っているため、様々な問題に対して適用することができます。