Datalens.ai
← All algorithms

GRAPH-CONNECTIVITY

maximum_flow

Find a maximum single-commodity flow.

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

# Build a directed network of available shipments and capacities.
G = nx.DiGraph()
for origin, destination, capacity, cost in shipments["routes"]:
    G.add_edge(origin, destination, capacity=capacity, weight=cost)

# Verify the result on the example network.
value, result = nx.maximum_flow(G, "warehouse", "store")
assert value == 5 and sum(result["warehouse"].values()) == 5
print("Expected output verified")