# pgRouting Manual (3.0-rc1)

## pgr_edmondsKarp

`pgr_edmondsKarp` — Calculates the flow on the graph edges that maximizes the flow from the sources to the targets using Push Relabel Algorithm.

Boost Graph Inside

Availability

- Version 3.0.0
  - Official function
- Version 2.5.0
  - Renamed from `pgr_maxFlowEdmondsKarp`
  - Proposed function
- Version 2.3.0
  - New Experimental function

Support

- Supported versions: current(3.0)
- Unsupported versions: 2.6 2.5 2.4 2.3

## Description

The main characteristics are:

- The graph is directed.
- Process is done only on edges with positive capacities.
- When the maximum flow is 0 then there is no flow and EMPTY SET 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.
- Calculates the flow/residual capacity for each edge. In the output
  - Edges with zero flow are omitted.
- Creates a super source and edges to all the source(s), and a super target and the edges from all the targets(s).
- The maximum flow through the graph is guaranteed to be the value returned by pgr_maxFlow when executed with the same parameters and can be calculated:
  - By aggregation of the outgoing flow from the sources
  - By aggregation of the incoming flow to the targets

- Running time: \(O( V * E ^ 2)\)

## Signatures

Summary

    pgr_edmondsKarp(Edges SQL, source,  target)
    pgr_edmondsKarp(Edges SQL, sources, target)
    pgr_edmondsKarp(Edges SQL, source,  targets)
    pgr_edmondsKarp(Edges SQL, sources, targets)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

### One to One

    pgr_edmondsKarp(Edges SQL, source,  target)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: | From vertex \(6\) to vertex \(11\)

    SELECT * FROM pgr_edmondsKarp(
        'SELECT id,
                source,
                target,
                capacity,
                reverse_capacity
        FROM edge_table'
        , 6, 11
    );
     seq | edge | start_vid | end_vid | flow | residual_capacity
    -----+------+-----------+---------+------+-------------------
       1 |   10 |         5 |      10 |  100 |                30
       2 |    8 |         6 |       5 |  100 |                30
       3 |   11 |         6 |      11 |  130 |                 0
       4 |   12 |        10 |      11 |  100 |                 0
    (4 rows)

### One to Many

    pgr_edmondsKarp(Edges SQL, source,  targets)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: | From vertex \(6\) to vertices \(\{1, 3, 11\}\)

    SELECT * FROM pgr_edmondsKarp(
        'SELECT id,
                source,
                target,
                capacity,
                reverse_capacity
        FROM edge_table'
       , 6, ARRAY[1, 3, 11]
    );
     seq | edge | start_vid | end_vid | flow | residual_capacity
    -----+------+-----------+---------+------+-------------------
       1 |    1 |         2 |       1 |   50 |                80
       2 |    3 |         4 |       3 |   80 |                50
       3 |    4 |         5 |       2 |   50 |                 0
       4 |   10 |         5 |      10 |   80 |                50
       5 |    8 |         6 |       5 |  130 |                 0
       6 |    9 |         6 |       9 |   80 |                50
       7 |   11 |         6 |      11 |  130 |                 0
       8 |   16 |         9 |       4 |   80 |                 0
       9 |   12 |        10 |      11 |   80 |                20
    (9 rows)

### Many to One

    pgr_edmondsKarp(Edges SQL, sources,  target)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: | From vertices \(\{6, 8, 12\}\) to vertex \(11\)

    SELECT * FROM pgr_edmondsKarp(
        'SELECT id,
                source,
                target,
                capacity,
                reverse_capacity
        FROM edge_table'
       , ARRAY[6, 8, 12], 11
    );
     seq | edge | start_vid | end_vid | flow | residual_capacity
    -----+------+-----------+---------+------+-------------------
       1 |   10 |         5 |      10 |  100 |                30
       2 |    8 |         6 |       5 |  100 |                30
       3 |   11 |         6 |      11 |  130 |                 0
       4 |   12 |        10 |      11 |  100 |                 0
    (4 rows)

### Many to Many

    pgr_edmondsKarp(Edges SQL, sources,  targets)
    RETURNS SET OF (seq, edge, start_vid, end_vid, flow, residual_capacity)
    OR EMPTY SET

Example: | From vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\)

    SELECT * FROM pgr_edmondsKarp(
        'SELECT id,
                source,
                target,
                capacity,
                reverse_capacity
        FROM edge_table'
       , ARRAY[6, 8, 12], ARRAY[1, 3, 11]
    );
     seq | edge | start_vid | end_vid | flow | residual_capacity
    -----+------+-----------+---------+------+-------------------
       1 |    1 |         2 |       1 |   50 |                80
       2 |    3 |         4 |       3 |   80 |                50
       3 |    4 |         5 |       2 |   50 |                 0
       4 |   10 |         5 |      10 |  100 |                30
       5 |    8 |         6 |       5 |  130 |                 0
       6 |    9 |         6 |       9 |   80 |                50
       7 |   11 |         6 |      11 |  130 |                 0
       8 |    7 |         8 |       5 |   20 |                30
       9 |   16 |         9 |       4 |   80 |                 0
      10 |   12 |        10 |      11 |  100 |                 0
    (10 rows)

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

## Result Columns

Column | Type | Description
--- | --- | ---
seq | `INT` | Sequential value starting from 1.
edge | `BIGINT` | Identifier of the edge in the original query(edges_sql).
start_vid | `BIGINT` | Identifier of the first end point vertex of the edge.
end_vid | `BIGINT` | Identifier of the second end point vertex of the edge.
flow | `BIGINT` | Flow through the edge in the direction (`start_vid`, `end_vid`).
residual_capacity | `BIGINT` | Residual capacity of the edge in the direction (`start_vid`, `end_vid`).

## See Also

- Flow - Family of functions, pgr_boykovKolmogorov, pgr_pushRelabel
- https://www.boost.org/libs/graph/doc/edmonds_karp_max_flow.html
- https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

Indices and tables

- Index
- Search Page