Pattern Guide
Circulation & Flow with Lower Bounds
"Edge has both minimum and maximum flow. Reduce to standard max-flow via supply/demand."
Circulation with lower bounds extends max-flow where each edge has both a minimum (l) and maximum (u) flow. Transform: subtract lower bounds to get a standard flow problem with a modified source/sink. Applications: feasibility flow (can we satisfy all minimums?), minimum cost feasible flow, and scheduling with mandatory and optional tasks. Uses the "demand-supply" transformation.
Problems you can solve with this pattern
3 problems · click any to start solving
function feasibleFlow(n, edges, s, t) {
// edges: [{u, v, lo, hi}]
// Returns {feasible: bool, flow: f} if feasible
const N = n + 2;
const S2 = n, T2 = n + 1; // super source/sink
// Build flow network
const adj = Array.from({length: N}, () => []);
const addEdge = (u, v, cap) => {
adj[u].push({to: v, cap, rev: adj[v].length});
adj[v].push({to: u, cap: 0, rev: adj[u].length - 1});
};
const demand = new Array(n).fill(0);
for (const {u, v, lo, hi} of edges) {
addEdge(u, v, hi - lo); // reduced capacity
demand[v] += lo; // v gains lo units
demand[u] -= lo; // u loses lo units
}
// Add S' → v for positive demand, u → T' for negative demand
let sumSupply = 0;
for (let i = 0; i < n; i++) {
if (demand[i] > 0) { addEdge(S2, i, demand[i]); sumSupply += demand[i]; }
else if (demand[i] < 0) { addEdge(i, T2, -demand[i]); }
}
// Add t → s with infinite capacity (to allow circulation)
addEdge(t, s, Infinity);
// Run max-flow from S2 to T2
const flow = maxflow(adj, S2, T2, N); // use Dinic's from template
return { feasible: flow === sumSupply };
}Transformation for lower bounds: for edge (u,v) with bounds [l,u], subtract l from both bounds to get [0, u-l]. This forces l units through the edge, creating excess at v and deficit at u. Add a super-source S' and super-sink T': for each node with excess d > 0, add edge S'→node with capacity d; for deficit d < 0, add edge node→T' with capacity |d|. Find max-flow S'→T'. If it saturates all S'-edges: feasible.
function feasibleFlow(n, edges, s, t) {
// edges: [{u, v, lo, hi}]
// Returns {feasible: bool, flow: f} if feasible
const N = n + 2;
const S2 = n, T2 = n + 1; // super source/sink
// Build flow network
const adj = Array.from({length: N}, () => []);
const addEdge = (u, v, cap) => {
adj[u].push({to: v, cap, rev: adj[v].length});
adj[v].push({to: u, cap: 0, rev: adj[u].length - 1});
};
const demand = new Array(n).fill(0);
for (const {u, v, lo, hi} of edges) {
addEdge(u, v, hi - lo); // reduced capacity
demand[v] += lo; // v gains lo units
demand[u] -= lo; // u loses lo units
}
// Add S' → v for positive demand, u → T' for negative demand
let sumSupply = 0;
for (let i = 0; i < n; i++) {
if (demand[i] > 0) { addEdge(S2, i, demand[i]); sumSupply += demand[i]; }
else if (demand[i] < 0) { addEdge(i, T2, -demand[i]); }
}
// Add t → s with infinite capacity (to allow circulation)
addEdge(t, s, Infinity);
// Run max-flow from S2 to T2
const flow = maxflow(adj, S2, T2, N); // use Dinic's from template
return { feasible: flow === sumSupply };
}Edge (u,v) with bounds [l,u]: subtract l → capacity (u-l), adjust demand at endpoints.
- Node v: demand += l (needs l more units)
- Node u: demand -= l (provides l more units)
For each node with demand d:
- d > 0: add S' → node with capacity d
- d < 0: add node → T' with capacity |d|
Feasible iff max-flow(S'→T') = sum of all positive demands.
Applications:
- "Each pipe must carry at least l units": feasibility check
- Minimum flow in network: feasibility + binary search
- Circular scheduling with quotas: each time slot must serve a minimum number of requests