조합 최적화 - 일반적인 문제 - 최대 흐름 문제

일반적인 문제와 실행 방법

최대 흐름 문제

그래프 $G=(V,E)$의 각 변 $e_{ij}=(v_i,v_j)\in E$가 용량 $c_{ij}$를 가질 때 시작점 $v_s\in V$(소스) 에서 종점 $v_t\in V$(싱크)로의 총 유량이 최대가 되는 플로우를 구하라.

실행 방법

usage

Signature: nx.maximum_flow(G, s, t, capacity='capacity', flow_func=None, **kwargs)
Docstring:
Find a maximum single-commodity flow.

파이썬

# CSVデータ
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = nx.maximum_flow(g, 5, 2)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist
  =[(k1, k2) for k1, d in t[1].items() for k2, v in d.items() if v])
plt.show()
for i, d in t[1].items():
    for j, f in d.items():
        if f: print((i, j), f)

결과

(0, 2) 2
(0, 3) 2
(1, 2) 2
(3, 2) 2
(4, 0) 2
(5, 0) 2
(5, 1) 2
(5, 4) 2

파이썬

# pandas.DataFrame
from ortoolpy.optimization import MaximumFlow
MaximumFlow('data/edge0.csv', 5, 2)[1]

node1
node2
capacity
weight
플로우




0
0
2
2
4
2


1
0
3
2
2
2


2
0
4
2
2
2


3
0
5
2
4
2


4
1
2
2
5
2


5
1
5
2
5
2


6
2
3
2
3
2


7
4
5
2
1
2



파이썬

# 乱数データ
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['capacity'] = 1
t = nx.maximum_flow(g, 5, 6)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist
  =[(k1, k2) for k1, d in t[1].items() for k2, v in d.items() if v])
plt.show()

데이터

data/node0.csv

data/edge0.csv