# pgRouting Manual (3.0-rc1)

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