NetworkX④(最大流問題)

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

最大流問題

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

[最大流問題の例]

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

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

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

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

この問題に対応するネットワーク上の 各コンピュータデータ量 を下記のグラフで表示します。

[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

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

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