Typical problem and execution method
When each side of the graph $ G = (V, E) $ $ e_ {ij} = (v_i, v_j) \ in E $ has the capacity $ c_ {ij} $, the starting point $ v_s \ in V $ (source) Find the flow that maximizes the total flow rate from to the end point $ v_t \ in V $ (sink).
usage
Signature: nx.maximum_flow(G, s, t, capacity='capacity', flow_func=None, **kwargs)
Docstring:
Find a maximum single-commodity flow.
python
#CSV data
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)
result
(0, 2) 2
(0, 3) 2
(1, 2) 2
(3, 2) 2
(4, 0) 2
(5, 0) 2
(5, 1) 2
(5, 4) 2
python
# pandas.DataFrame
from ortoolpy.optimization import MaximumFlow
MaximumFlow('data/edge0.csv', 5, 2)[1]
node1 | node2 | capacity | weight | flow | |
---|---|---|---|---|---|
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 |
python
#Random number data
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()
Recommended Posts