NetworkX④（最大流問題）

NetworkXを、使って 最大流問題 を解いてみます。

最大流問題

グラフ間に流れる数値を最大化させる問題を 最大流問題 といいます。

[最大流問題の例]

ネットワーク上の２台のコンピュータｓ、ｔがありｓからｔにデータを送ります。

このネットワークには全部でＮ台のコンピュータがあり、いくつかのコンピュータ間は一方向性の

通信ケーブルで接続されていて、それぞれ１秒間に通信できる最大のデータ量が決まってきます。

ｓからｔへ１秒間で最大どれだけのデータを送信することができるでしょうか。

まず、ネットワーク上のコンピュータとデータ量をグラフに表示してみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最大流問題 を解くためには、maximum_flow関数 を使います。

引数には、グラフオブジェクト、始点ノード、終了ノードを設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
flow_value, flows = nx.maximum_flow(G, 's', 't')
print(f'maximum flow: {flow_value}')

caps = nx.get_edge_attributes(G, 'capacity')
for u in nx.topological_sort(G):
    for v, flow in sorted(flows[u].items()):
        print(f'  ({u}, {v}): {flow}/{caps[(u, v)]}')

[実行結果]

maximum flow: 11

  (s, 1): 9/10

  (s, 2): 2/2

  (1, 2): 3/6

  (1, 3): 6/6

  (3, 2): 0/3

  (3, t): 6/8

  (2, t): 5/5

ｓからｔへの最大流は 11 と導き出すことができました。

また、最大流が流れる際に各ノード間に流すデータ通信も表示しています。