Maximum flow

How much can be pushed through a network, and along which edges.

A different edges query

These functions read capacities, not costs:

Column	Type	Meaning
id	BIGINT	required
source, target	BIGINT	required
capacity	numeric	required — how much source → target carries
reverse_capacity	numeric	optional — how much target → source carries

A missing or non-positive capacity means that direction carries nothing, mirroring how cost works elsewhere. duckrouting_max_flow_min_cost wants cost and reverse_cost as well; duckrouting_edge_disjoint_paths and duckrouting_max_cardinality_match use cost/reverse_cost only, treating every usable direction as capacity 1.

All of them accept a single vertex or a BIGINT[] for source and sink. Several sources or sinks are handled by attaching an unbounded super-source and super-sink, which is how a many-to-many question becomes one flow problem.

duckrouting_max_flow

TABLE duckrouting_max_flow (edges_sql VARCHAR, source BIGINT|BIGINT[], sink BIGINT|BIGINT[])

One row, one DOUBLE: the maximum total flow.

SELECT * FROM duckrouting_max_flow(
  'SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12);
-- → 230.0

SELECT * FROM duckrouting_max_flow(
  'SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, [5, 10, 12]);
-- → 340.0

duckrouting_push_relabel, duckrouting_edmonds_karp, duckrouting_boykov_kolmogorov

TABLE duckrouting_push_relabel (edges_sql VARCHAR, source BIGINT|BIGINT[], sink BIGINT|BIGINT[])
-- identically for duckrouting_edmonds_karp and duckrouting_boykov_kolmogorov

The same maximum, broken down edge by edge. Returns seq, edge, start_vid, end_vid, flow and residual_capacity. Only edges actually carrying flow appear, and flow + residual_capacity is that direction's capacity.

The three differ in algorithm, not in answer — though on a network with slack they may distribute the same total differently.

How differently, on a real network

"Differently" can be dramatic. Push-relabel leaves circulation: cycles that satisfy flow conservation but carry nothing from the source to the sink. On the 1,912-edge network behind the live demo, one source/sink pair returns

Function	Edges reported	Σ flow
duckrouting_push_relabel	474	123,000
duckrouting_edmonds_karp	57	34,200
duckrouting_boykov_kolmogorov	57	34,200

for the same maximum of 600. Push-relabel's answer is a valid maximum flow -- conservation holds at every vertex, no edge exceeds its capacity -- but those 474 edges fall into 16 connected components, and only one of them touches the source or the sink. The rest are loops going nowhere.

So if you are drawing the result, or decomposing it into routes, prefer edmonds_karp or boykov_kolmogorov. If you only want the number, any of them will do, and duckrouting_max_flow is cheaper than all three.

SELECT edge, start_vid, end_vid, flow, residual_capacity
FROM duckrouting_push_relabel(
  'SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12)
ORDER BY edge;
-- → edge  start_vid  end_vid   flow  residual_capacity
-- →    8         11        7  100.0               30.0
-- →   10          7        8  100.0               30.0
-- →   11         11       12  130.0                0.0
-- →   12          8       12  100.0                0.0

Reading that: 130 units go straight from 11 to 12, and another 100 detour via 7 and 8 — 230 in total.

duckrouting_max_flow_min_cost and duckrouting_max_flow_min_cost_cost

TABLE duckrouting_max_flow_min_cost      (edges_sql VARCHAR, source BIGINT|BIGINT[], sink BIGINT|BIGINT[])
TABLE duckrouting_max_flow_min_cost_cost (edges_sql VARCHAR, source BIGINT|BIGINT[], sink BIGINT|BIGINT[])

Of all the ways to achieve the maximum flow, the cheapest. The first returns seq, edge, source, target, flow, residual_capacity, cost and agg_cost, where cost is flow × the edge's cost. The second returns that total alone.

The edges query needs cost and reverse_cost in addition to the capacities.

SELECT edge, source, target, flow, cost, agg_cost
FROM duckrouting_max_flow_min_cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost FROM edges',
  11, 12);
-- → edge  source  target   flow   cost  agg_cost
-- →    8      11       7  100.0  100.0     100.0
-- →   10       7       8  100.0  100.0     200.0
-- →   11      11      12  130.0  130.0     330.0
-- →   12       8      12  100.0  100.0     430.0

SELECT * FROM duckrouting_max_flow_min_cost_cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost FROM edges',
  11, 12);
-- → 430.0

duckrouting_edge_disjoint_paths

TABLE duckrouting_edge_disjoint_paths (edges_sql VARCHAR, start_vid BIGINT|BIGINT[], end_vid BIGINT|BIGINT[])
TABLE duckrouting_edge_disjoint_paths (edges_sql VARCHAR, start_vid BIGINT|BIGINT[], end_vid BIGINT|BIGINT[], directed BOOLEAN)
-- also accepts directed => BOOLEAN

As many routes as exist that share no edge — how many independent ways there are between two points. Uses cost/reverse_cost, giving every usable direction capacity 1, then decomposes the resulting flow back into paths.

Returns pgRouting's shortest-path shape: seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost.

SELECT path_id, path_seq, node, edge FROM duckrouting_edge_disjoint_paths(
  'SELECT id, source, target, cost, reverse_cost FROM edges', 11, 12);
-- → path_id  path_seq  node  edge
-- →       1         1    11     8
-- →       1         2     7    10
-- →       1         3     8    12
-- →       1         4    12    -1
-- →       2         1    11    11
-- →       2         2    12    -1

Two independent routes from 11 to 12, sharing no edge.

duckrouting_max_cardinality_match

TABLE duckrouting_max_cardinality_match (edges_sql VARCHAR)

The largest set of edges no two of which share a vertex. Returns one edge column. Structural, so only id, source and target really matter.

SELECT * FROM duckrouting_max_cardinality_match(
  'SELECT id, source, target, cost, reverse_cost FROM edges');
-- → edge
-- →    1
-- →    5
-- →    6
-- →   13
-- →   14
-- →   16
-- →   17
-- →   18