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.

images/boost-inside.jpeg

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

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

Indices and tables