ๆๅฐ่ฒป็จๆตๅ้ก
ๆๅใฐใฉใ$G=(V,E)$ใซใใใฆใๅ่พบใฎๅฎน้ใจ้ใฟใใใซ็ฏ็นใฎ้่ฆ้ใไธใใใใใจใใๅ่พบใฎๅฎน้ใ่ถ ้ใใใซๅ่พบใฎๆต้ใซๅฏพใใ้ใฟใฎ็ทๅใๆๅฐใจใชใใใญใผใๆฑใใใ
- ๅ็ฏ็นใซใใใฆใใๆตๅ ฅ้ - ๆตๅบ้ใใฏใ้่ฆ้ใจ็ญใใใ
- ้่ฆ้ใ่ฒ ใฎๅ ดๅใไพ็ตฆ้ใ่กจใใ
- ๅ จใฆใฎ็ฏ็นใฎ้่ฆ้ใฎๅใฏ0ใงใชใใใฐใใใชใใ
ๅฎ่กๆนๆณ
usage
Signature: nx.min_cost_flow(G, demand='demand', capacity='capacity', weight='weight')
Docstring:
Return a minimum cost flow satisfying all demands in digraph G.
G is a digraph with edge costs and capacities and in which nodes
have demand, i.e., they want to send or receive some amount of
flow. A negative demand means that the node wants to send flow, a
positive demand means that the node want to receive flow. A flow on
the digraph G satisfies all demand if the net flow into each node
is equal to the demand of that node.
python
# 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, directed=True)[0]
result = nx.min_cost_flow(g)
for i, d in result.items():
for j, f in d.items():
if f: print((i, j), f)
็ตๆ
(0, 1) 1
(0, 3) 1
(0, 4) 2
(4, 5) 1
python
# pandas.DataFrame
from ortoolpy.optimization import MinCostFlow
MinCostFlow('data/node0.csv','data/edge0.csv')
| node1 | node2 | capacity | weight | flow | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 1 | 1 |
| 1 | 0 | 3 | 2 | 2 | 1 |
| 2 | 0 | 4 | 2 | 2 | 2 |
| 3 | 4 | 5 | 2 | 1 | 1 |
python
# ไนฑๆฐใใผใฟ
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 # ไพ็ตฆ
g.nodes[7]['demand'] = 2 # ้่ฆ
g.adj[2][7]['capacity'] = 1 # ๅฎน้
result = nx.min_cost_flow(g)
for i, d in result.items():
for j, f in d.items():
if f: print((i, j), f)
็ตๆ
(1, 2) 2
(2, 3) 1
(2, 7) 1
(3, 7) 1
