pgr_maxFlow

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

  • Version 3.0.0

    • Official function

  • Version 2.4.0

    • New Proposed function

Support

Description

The main characteristics are:

  • The graph is directed .

  • Calculates the maximum flow from the source(s) to the target(s) .

    • 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)\)

Signatures

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 

pgr_maxFlow(Edges SQL, source,  target)
RETURNS BIGINT
Example :

From vertex \(6\) to vertex \(11\) 

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

One to Many 

pgr_maxFlow(Edges SQL, source,  targets)
RETURNS BIGINT
Example :

From vertex \(6\) to vertices \(\{11, 1, 13\}\) 

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 

pgr_maxFlow(Edges SQL, sources,  target)
RETURNS BIGINT
Example :

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

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 

pgr_maxFlow(Edges SQL, sources,  targets)
RETURNS BIGINT
Example :

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

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)

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

Return Columns

Type

Description

BIGINT

Maximum flow possible from the source(s) to the target(s)

See Also

Indices and tables