# pgRouting Manual (3.1)

## 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.

Boost Graph Inside

Availability

- Version 3.0.0

  - Official function

- Version 2.4.0

  - New Proposed function

Support

- Supported versions: current(3.1) 3.0

- Unsupported versions: 2.6 2.5 2.4

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

## See Also

- Flow - Family of functions

- https://www.boost.org/libs/graph/doc/push_relabel_max_flow.html

- https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm

Indices and tables

- Index

- Search Page