39.08Intermediate / Advanced6 topics18 min6 interactive animations

Flow modeling

Many problems that look unrelated to flows become max-flow questions once you build the right network: disjoint paths, vertex limits, assignments, shipments, and circulations with demands and lower bounds.

Learning goals

Reduce edge-disjoint and vertex-disjoint paths to max flow
Model an assignment as a flow
Handle several sources and sinks with a super source and sink
Decide feasibility of a circulation with demands and lower bounds

Prerequisites

Maximum flowIntegrality of flows

Flow is a modelling language. The skill is to turn a story (“at most one worker per job”, “each room can be used once”) into capacities, and then let a standard algorithm answer.

39.08.1

Edge-disjoint paths

**Question**: how many paths from s to t can be found so that no edge is used by two paths? Give every edge capacity 1. An integral flow of value k decomposes into k paths that share no edge, and conversely k edge-disjoint paths are a flow of value k. By max-flow min-cut the answer also equals the fewest edges whose removal separates t from s (Menger's theorem).

Try the first preset, “Edge-disjoint paths: a diamond with a cross edge” (0-1 0-2 1-3 2-3 1-2): the answer is 2. On the 6-vertex preset “Same graph: edge-disjoint paths” (0-1 0-2 1-3 2-3 3-4 3-5 4-5) it is also 2, for example 0→1→3→4→5 and 0→2→3→5.

The helper maxFlow is a short BFS augmenting-path routine on a capacity matrix (parallel edges just add up).

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19
20static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
21    int[][] cap = new int[n][n];
22    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
23    return maxFlow(cap, 0, n - 1);
24}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

39.08.2

Vertex splitting

A flow network limits edges, not vertices. To allow each vertex to be used by at most one path, **split** every inner vertex v into v-in and v-out joined by one edge of capacity 1. Every edge that entered v now enters v-in, and every edge that left v leaves v-out. A flow can pass through v at most once.

On the 6-vertex graph above, both routes must use vertex 3, so there is only **1** vertex-disjoint path (the “Vertex-disjoint paths: both routes cross vertex 3” preset), but 2 edge-disjoint paths. Vertex splitting is the standard trick whenever the limited resource is a node: a room, a machine, a junction.

The source and sink are not split: paths are allowed to share them. The code indexes in as 2v and out as 2v + 1.

Java

1static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
2    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
3    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
4    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
5    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
6}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

39.08.3

Assignment

**Assignment**: workers can each do some jobs; every worker takes at most one job and every job is done by at most one worker. Maximise the number of assigned pairs. Build a network with a source joined to every worker (capacity 1), every allowed pair as a worker-to-job edge (capacity 1), and every job joined to the sink (capacity 1). Integral flows are exactly matchings.

The preset “Assignment: 3 workers, 3 jobs” has pairs 0-0 0-1 1-0 2-1 2-2 and assigns all three. In “Assignment: no perfect matching” workers 0, 1 and 2 all compete for job 0 and only worker 2 has another option (job 1), so at most 2 pairs can be made. The two sets of vertices form a bipartite graph; Chapter 40 treats matchings in depth, including faster algorithms.

The code takes pairs {worker, job} and returns the maximum number of assignments.

Java

1static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
2    int n = workers + jobs + 2, s = 0, t = n - 1;
3    int[][] cap = new int[n][n];
4    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
5    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
6    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
7    return maxFlow(cap, s, t);
8}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

39.08.4

Resource allocation

**Resource allocation** generalises assignment to quantities: suppliers have stock, customers have demands, and each supplier-customer pair has a shipping limit. Add a **super source** joined to every supplier with capacity equal to its stock, and a **super sink** reached from every customer with capacity equal to its demand. The maximum flow is the largest total amount that can be shipped.

If the maximum flow equals the total demand, every customer can be served. If it is smaller, the minimum cut shows which group of customers (and suppliers) is the bottleneck.

The super source and sink are the standard trick for several sources or sinks. The same construction appears in the circulation lesson that follows.

Java

1static int maxShipment(int[] supply, int[] demand, int[][] limit) {   // limit[i][j]: most supplier i can send to customer j
2    int m = supply.length, k = demand.length, s = 0, t = m + k + 1;
3    int[][] cap = new int[t + 1][t + 1];
4    for (int i = 0; i < m; i++) cap[s][1 + i] = supply[i];             // a supplier cannot send more than it has
5    for (int j = 0; j < k; j++) cap[1 + m + j][t] = demand[j];         // a customer takes no more than it needs
6    for (int i = 0; i < m; i++) for (int j = 0; j < k; j++) cap[1 + i][1 + m + j] = limit[i][j];
7    return maxFlow(cap, s, t);
8}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

39.08.5

Circulation with demands

A **circulation with demands** has no single source and sink. Each vertex v has a **supply** b(v): positive means it injects that much net flow, negative means it consumes. The supplies add up to 0, and the flow on each edge must respect its capacity. Does a flow exist where every vertex's outflow minus inflow equals its supply?

Reduce it to max flow: add a super source S* with an edge of capacity b(v) to every vertex with positive supply, and a super sink T* with an edge of capacity −b(v) from every vertex with negative supply. A feasible flow exists exactly when the maximum flow from S* saturates all the supply edges, that is, equals the sum of the positive supplies.

Load “Circulation: feasible with demands” (0-1:3 0-2:2 1-3:2 2-3:3, supplies 3 0 0 -3): vertex 0 must send 3 units to vertex 3; the route through vertex 1 carries at most 2 and the route through vertex 2 at most 2, so 3 units fit, and the animation saturates 3 of 3.

Java

1static boolean feasibleDemands(int n, int[][] edges, int[] supply) {   // edges {a, b, capacity}; supply sums to 0
2    int s = n, t = n + 1;
3    int[][] cap = new int[n + 2][n + 2];
4    for (int[] e : edges) cap[e[0]][e[1]] += e[2];
5    int required = 0;
6    for (int v = 0; v < n; v++) {
7        if (supply[v] > 0) { cap[s][v] = supply[v]; required += supply[v]; }
8        else if (supply[v] < 0) cap[v][t] = -supply[v];
9    }
10    return maxFlow(cap, s, t) == required;                            // every unit of supply found a demand
11}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

39.08.6

Lower bounds

Sometimes an edge must carry **at least** low units as well as at most high. Handle the lower bound by forcing it first: send low units along the edge for free. That removes low from the supply of its tail and adds it to the head's supply, and leaves a capacity of high − low for the optional part. After this adjustment the problem is a circulation with demands and no lower bounds.

In the editor write such an edge as a-b:low~high. The preset “Circulation: a lower bound makes it infeasible” (0-1:2~3 1-2:0~1, all supplies 0) forces 2 units from vertex 0 to vertex 1; vertex 1 has to pass them on but only has capacity 1 out, and nothing returns to vertex 0. The adjusted supplies need 2 units that cannot be routed, so the answer is infeasible, saturated 0 of 2.

To get an actual feasible flow, run the max flow, then add each edge's lower bound back to the flow found on its optional part.

Java

1static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {   // edges {a, b, low, high}
2    int[] adjusted = supply.clone();
3    int[][] capOnly = new int[edges.length][];
4    for (int k = 0; k < edges.length; k++) {
5        int[] e = edges[k];
6        adjusted[e[0]] -= e[2];                                       // the forced units leave a for free ...
7        adjusted[e[1]] += e[2];                                       // ... and arrive at b
8        capOnly[k] = new int[]{e[0], e[1], e[3] - e[2]};              // only the optional part is routed
9    }
10    return feasibleDemands(n, capOnly, adjusted);
11}

Modelling with flow: disjoint paths, vertex splitting, assignment, circulation

Interactive · edit the input

the directed graph · 4 vertices · 5 edges

source

sink

Added by the constructionCarries flowSaturatedVertex of the model

Setup

Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.

Step 1 / 4

Java

1static int maxFlow(int[][] cap, int s, int t) {                       // cap[u][v]: capacity, becomes the residual matrix
2    int n = cap.length, flow = 0;
3    while (true) {
4        int[] parent = new int[n];
5        Arrays.fill(parent, -1);
6        parent[s] = s;
7        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
8        while (!queue.isEmpty() && parent[t] == -1) {
9            int u = queue.poll();
10            for (int v = 0; v < n; v++) if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; queue.add(v); }
11        }
12        if (parent[t] == -1) return flow;
13        int b = Integer.MAX_VALUE;
14        for (int v = t; v != s; v = parent[v]) b = Math.min(b, cap[parent[v]][v]);
15        for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= b; cap[v][parent[v]] += b; }
16        flow += b;
17    }
18}
19static int edgeDisjointPaths(int n, int[][] edges) {                  // directed edges {a, b}; source 0, sink n - 1
20    int[][] cap = new int[n][n];
21    for (int[] e : edges) cap[e[0]][e[1]]++;                          // every edge gets capacity 1
22    return maxFlow(cap, 0, n - 1);
23}
24static int vertexDisjointPaths(int n, int[][] edges) {                // paths may share only the source and the sink
25    int[][] cap = new int[2 * n][2 * n];                              // vertex v is split: in = 2v, out = 2v + 1
26    for (int v = 1; v < n - 1; v++) cap[2 * v][2 * v + 1] = 1;        // the vertex itself can be used once
27    for (int[] e : edges) cap[2 * e[0] + 1][2 * e[1]]++;              // edge: out of a, into b
28    return maxFlow(cap, 1, 2 * (n - 1));                              // from out(source) to in(sink)
29}
30static int maxAssignments(int workers, int jobs, int[][] canDo) {     // canDo {worker, job}
31    int n = workers + jobs + 2, s = 0, t = n - 1;
32    int[][] cap = new int[n][n];
33    for (int w = 0; w < workers; w++) cap[s][1 + w] = 1;              // each worker takes at most one job
34    for (int j = 0; j < jobs; j++) cap[1 + workers + j][t] = 1;       // each job is done by at most one worker
35    for (int[] p : canDo) cap[1 + p[0]][1 + workers + p[1]] = 1;
36    return maxFlow(cap, s, t);
37}
38// edges {a, b, low, high}; supply[v] = flow that must leave v net (negative: must arrive); returns true if a feasible flow exists
39static boolean feasibleCirculation(int n, int[][] edges, int[] supply) {
40    int s = n, t = n + 1;
41    int[][] cap = new int[n + 2][n + 2];
42    int[] need = supply.clone();                                      // supply left over after the forced lower-bound flow
43    for (int[] e : edges) {
44        cap[e[0]][e[1]] += e[3] - e[2];                               // only the optional part is routed
45        need[e[0]] -= e[2];
46        need[e[1]] += e[2];
47    }
48    int required = 0;
49    for (int v = 0; v < n; v++) {
50        if (need[v] > 0) { cap[s][v] = need[v]; required += need[v]; }
51        else if (need[v] < 0) cap[v][t] = -need[v];
52    }
53    return maxFlow(cap, s, t) == required;                            // every unit of surplus found a deficit
54}

Live state

4 model vertices5 model edges

problem

Edge-disjoint paths

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L19	problem=Edge-disjoint paths	Find as many paths from 0 to 3 as possible so that no edge is used twice. Each edge may be used by one path at most.
2	L20	vertices=4 edges=5	Give every edge capacity 1. A flow of value k from the source to the sink then splits into k paths that share no edge, and k disjoint paths give a flow of value k.
3	L22	max_flow=2	Maximum flow in the model network: 2.
4	L19	return=2 paths=2	2 edge-disjoint paths: 0→2→3; 0→1→3. By max-flow min-cut this also equals the fewest edges whose removal disconnects 3 from 0.

Practice ladder

Now try it yourself

Easy

Find the Town Judge

Medium

Is Graph Bipartite?
Cheapest Flights Within K Stops

Advanced

Maximum Students Taking Exam
Distribute Repeating Integers
Minimum Cost to Make at Least One Valid Path in a Grid

Key takeaways

Edge-disjoint paths: unit capacities. Vertex-disjoint paths: split each inner vertex into in and out with capacity 1.
Assignment and shipping: super source and sink with capacities for stock and demand.
Circulations with demands and lower bounds reduce to one max flow that must saturate all the supply.