``` 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.2.0

• New proposed signature

• Version 3.0.0

• Official function

• Version 2.4.0

• New Proposed function

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 , start vid , end vid )
pgr_maxFlow( Edges SQL , start vid , end vids )
pgr_maxFlow( Edges SQL , start vids , end vid )
pgr_maxFlow( Edges SQL , start vids , end vids )
RETURNS ``` BIGINT ```

One to One

pgr_maxFlow( Edges SQL , start vid , end vid )
RETURNS ``` BIGINT ```
Example :

From vertex \(11\) to vertex \(12\)

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, 12);
pgr_maxflow
-------------
230
(1 row)

```

One to Many

pgr_maxFlow( Edges SQL , start vid , end vids )
RETURNS ``` BIGINT ```
Example :

From vertex \(11\) to vertices \(\{5, 10, 12\}\)

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
11, ARRAY[5, 10, 12]);
pgr_maxflow
-------------
340
(1 row)

```

Many to One

pgr_maxFlow( Edges SQL , start vids , end vid )
RETURNS ``` BIGINT ```
Example :

From vertices \(\{11, 3, 17\}\) to vertex \(12\)

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], 12);
pgr_maxflow
-------------
230
(1 row)

```

Many to Many

pgr_maxFlow( Edges SQL , start vids , end vids )
RETURNS ``` BIGINT ```
Example :

From vertices \(\{11, 3, 17\}\) to vertices \(\{5, 10, 12\}\)

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
pgr_maxflow
-------------
360
(1 row)

```

Combinations

RETURNS ``` BIGINT ```
Example :

Using a combinations table, equivalent to calculating result from vertices \(\{5, 6\}\) to vertices \(\{10, 15, 14\}\) .

The combinations table:

```SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
source  target
--------+--------
5      10
6      15
6      14
(3 rows)

```

The query:

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
pgr_maxflow
-------------
80
(1 row)

```

Parameters

Column

Type

Description

``` TEXT ```

Edges SQL as described below

``` TEXT ```

Combinations SQL as described below

start vid

``` BIGINT ```

Identifier of the starting vertex of the path.

start vids

``` ARRAY[BIGINT] ```

Array of identifiers of starting vertices.

end vid

``` BIGINT ```

Identifier of the ending vertex of the path.

end vids

``` ARRAY[BIGINT] ```

Array of identifiers of ending vertices.

Inner Queries

Edges SQL

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 ``` )

``` 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 ```

ANY-NUMERICAL :

``` SMALLINT ``` , ``` INTEGER ``` , ``` BIGINT ``` , ``` REAL ``` , ``` FLOAT ```

Combinations SQL

Parameter

Type

Description

``` source ```

ANY-INTEGER

Identifier of the departure vertex.

``` target ```

ANY-INTEGER

Identifier of the arrival vertex.

Where:

ANY-INTEGER :

``` SMALLINT ``` , ``` INTEGER ``` , ``` BIGINT ```

Result Columns

Type

Description

``` BIGINT ```

Maximum flow possible from the source(s) to the target(s)

Example :

Manually assigned vertex combinations.

```SELECT * FROM pgr_maxFlow(
'SELECT id, source, target, capacity, reverse_capacity
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
pgr_maxflow
-------------
80
(1 row)

```