# pgRouting Manual (2.5)

## pgr_maxFlow - Proposed

## Synopsis

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

Warning

Experimental functions

- They are not officially of the current release.
- They likely will not be officially be part of the next release:
  - The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
  - Name might change.
  - Signature might change.
  - Functionality might change.
  - pgTap tests might be missing.
  - Might need c/c++ coding.
  - May lack documentation.
  - Documentation if any might need to be rewritten.
  - Documentation examples might need to be automatically generated.
  - Might need a lot of feedback from the comunity.
  - Might depend on a proposed function of pgRouting
  - Might depend on a deprecated function of pgRouting

Characteristics

- The graph is directed.
- 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)\)

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

Calculates the maximum flow from the source to the target.

    pgr_maxFlow(edges_sql, source,  target)
    RETURNS BIGINT

Example: |

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

### One to Many

Calculates the maximum flow from the source to all of the targets.

    pgr_maxFlow(edges_sql, source,  targets)
    RETURNS BIGINT

Example: |

    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

Calculates the maximum flow from all the sources to the target.

    pgr_maxFlow(edges_sql, sources,  target)
    RETURNS BIGINT

Example: |

    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

Calculates the maximum flow from all of the sources to all of the targets.

    pgr_maxFlow(edges_sql, sources,  targets)
    RETURNS BIGINT

Example: |

    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)

## Description of the Signatures

### Description of the edges_sql query for Max-flow like functions

edges_sql: | an SQL query, 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

### Description of the Parameters of the Flow Signatures

Column | Type | Default | Description
--- | --- | --- | ---
edges_sql | `TEXT` |  | The edges SQL query as described above.
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.

### Description of the return value

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

## See Also

- Flow - Family of functions
- http://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