Datalens.ai
← All algorithms

GRAPH-CONNECTIVITY

capacity_scaling

Find a minimum cost flow satisfying all demands in digraph G.

Example of usage

Plan shipments over a capacitated retail distribution network.

Usage / limitations

+Use when: Evaluate maximum throughput, minimum cuts and shipping costs.

−Limitations: Illustrative capacities and costs are not real operational forecasts.

Mathematical formula

See method documentation: implementation and assumptions vary.
Sample dataShow 
{
  "variable": "shipments",
  "domain": "Retail distribution and logistics planning",
  "feature_names": [
    "origin",
    "destination",
    "capacity_units",
    "cost_per_unit"
  ],
  "routes": [
    [
      "warehouse",
      "hub_a",
      3,
      2
    ],
    [
      "warehouse",
      "hub_b",
      2,
      1
    ],
    [
      "hub_a",
      "store",
      3,
      1
    ],
    [
      "hub_b",
      "store",
      2,
      3
    ],
    [
      "hub_a",
      "hub_b",
      1,
      1
    ]
  ]
}

Code example (Python)

# DataLens.ai example — distribution network capacity and flow.
# Copy input + code + test includes the named dataset shown above.
import networkx as nx

# Create a directed distribution network with supply at the warehouse.
G = nx.DiGraph()
G.add_node("warehouse", demand=-5)
G.add_node("store", demand=5)
G.add_node("hub_a", demand=0)
G.add_node("hub_b", demand=0)
for origin, destination, capacity, cost in shipments["routes"]:
    G.add_edge(origin, destination, capacity=capacity, weight=cost)

# Verify the result on the example network.
total_cost, result = nx.capacity_scaling(G)
assert total_cost >= 0 and sum(result["warehouse"].values()) == 5
print("Expected output verified")