Navigation :

Table of Contents - pgRouting Manual (3.2) > pgr_edmondsKarp - pgRouting Manual (3.2)

pgr_edmondsKarp - pgRouting Manual (3.2)

Supported versions: Latest ( 3.2 ) 3.1 3.0
Unsupported versions: 2.6 2.5 2.4 2.3

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.2.0
- New proposed function:
  - pgr_edmondsKarp(Combinations)
Version 3.0.0
- Official function
Version 2.5.0
- Renamed from pgr_maxFlowEdmondsKarp
- Proposed function
Version 2.3.0
- New Experimental function

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)
pgr_edmondsKarp(Edges SQL, Combinations SQL) -- Proposed on v3.2
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)


     

Combinations

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

     

Example :: Using a combinations table, equivalent to calculating result from vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\) .

      SELECT * FROM pgr_edmondsKarp(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table',
    'SELECT * FROM ( VALUES (6, 1), (8, 3), (12, 11), (8, 1) ) AS t(source, target)'
);
 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	Description
Edges SQL	`TEXT`	Edges query as described in Inner Queries .
Combinations SQL	`TEXT`	Combinations query as described in Inner Queries .
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 queries

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

Combinations SQL :: an SQL query which should return a set of rows with the following columns:

Column	Type	Default	Description
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.