# pgr_maxFlow¶

pgr_maxFlow — Calculates the maximum flow in a directed graph from the source(s) to the targets(s) using the Push Relabel algorithm.

Availability

• Version 3.0.0
• Official function
• Version 2.4.0
• New Proposed function

Support

## Description¶

The main characteristics are:

• The graph is directed.
• Calculates the maximum flow from the source(s) to the target(s).
• When the maximum flow is 0 then there is no flow and 0 is returned.
• There is no flow when a source is the same as a target.
• Any duplicated value in the source(s) or target(s) are ignored.
• Uses the pgr_pushRelabel algorithm.
• Running time: $$O( V ^ 3)$$

## Signatures¶

Summary

pgr_maxFlow(Edges SQL, source,  target)
pgr_maxFlow(Edges SQL, sources,  target)
pgr_maxFlow(Edges SQL, source,  targets)
pgr_maxFlow(Edges SQL, sources,  targets)
RETURNS BIGINT


### One to One¶

pgr_maxFlow(Edges SQL, source,  target)
RETURNS BIGINT

Example: From vertex $$6$$ to vertex $$11$$
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, 11
);
pgr_maxflow
-------------
230
(1 row)



### One to Many¶

pgr_maxFlow(Edges SQL, source,  targets)
RETURNS BIGINT

Example: From vertex $$6$$ to vertices $$\{11, 1, 13\}$$
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, 6, ARRAY[11, 1, 13]
);
pgr_maxflow
-------------
340
(1 row)



### Many to One¶

pgr_maxFlow(Edges SQL, sources,  target)
RETURNS BIGINT

Example: From vertices $$\{6, 8, 12\}$$ to vertex $$11$$
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], 11
);
pgr_maxflow
-------------
230
(1 row)



### Many to Many¶

pgr_maxFlow(Edges SQL, sources,  targets)
RETURNS BIGINT

Example: From vertices $$\{6, 8, 12\}$$ to vertices $$\{1, 3, 11\}$$
SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table'
, ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
pgr_maxflow
-------------
360
(1 row)



## Parameters¶

Column Type Default Description
Edges SQL TEXT   The edges SQL query as described in Inner Query.
source BIGINT   Identifier of the starting vertex of the flow.
sources ARRAY[BIGINT]   Array of identifiers of the starting vertices of the flow.
target BIGINT   Identifier of the ending vertex of the flow.
targets ARRAY[BIGINT]   Array of identifiers of the ending vertices of the flow.

## Inner query¶

Edges SQL: an SQL query of a directed graph of capacities, which should return a set of rows with the following columns:
Column Type Default Description
id ANY-INTEGER   Identifier of the edge.
source ANY-INTEGER   Identifier of the first end point vertex of the edge.
target ANY-INTEGER   Identifier of the second end point vertex of the edge.
capacity ANY-INTEGER

Weight of the edge (source, target)

• When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_capacity ANY-INTEGER -1

Weight of the edge (target, source),

• When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

## Return Columns¶

Type Description
BIGINT Maximum flow possible from the source(s) to the target(s)