## 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 function:

• pgr_maxFlow(Combinations)

• 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, source,  target)
pgr_maxFlow(Edges SQL, sources,  target)
pgr_maxFlow(Edges SQL, source,  targets)
pgr_maxFlow(Edges SQL, sources,  targets)
pgr_maxFlow(Edges SQL, Combinations SQL)
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)

```

#### Combinations

```pgr_maxFlow(Edges SQL, Combinations SQL)
RETURNS BIGINT
```
Example :

Using a combinations table, equivalent to calculating result from vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\) .

```SELECT * FROM pgr_maxFlow(
'SELECT id,
source,
target,
capacity,
reverse_capacity
FROM edge_table',
'SELECT * FROM ( VALUES (6, 1), (8, 3), (12, 11), (8, 1) ) AS t(source, target)'
);
pgr_maxflow
-------------
360
(1 row)

```

### Parameters

Column

Type

Default

Description

Edges SQL

``` TEXT ```

Edges query as described in Inner Queries .

Combinations SQL

``` TEXT ```

Combinations query as described in Inner Queries .

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 queries

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

Combinations SQL :

an SQL query which should return a set of rows with the following columns:

Column

Type

Default

Description

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.

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

The function aggregates the sources and the targets, removes the duplicates, and then it calculates the result from the resultant source vertices to the target vertices.

### Return Columns

Type

Description

``` BIGINT ```

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