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.

_images/boost-inside.jpeg

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)